CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.
학습목표
연결 리스트의 정의를 설명할 수 있습니다.
핵심 단어
- 연결 리스트
강의 내용
1. 연결 리스트(linked list)
배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있다.
만약 값이 메모리상의 여러 군데 나뉘어져 있다면 어떻게 해야 연이어서 읽을 수 있을까?
각 값이 다음 값의 메모리 주소를 기억하고 있다면 가능할 것이며 이것이 바로 연결 리스트(linked list)다.
아래 그림과 같이 크기가 3인 연결 리스트는 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장한다.
연결 리스트의 가장 첫 번째 값인 1은 2의 메모리 주소를, 2는 3의 메모리 주소를 함께 저장하고 있고 3은 다음 값이 없기 때문에 NULL or None을 다음 값의 주소로 저장한다.
Python의 연결 리스트(linked list)
- python 의 경우 list 기본 자료형에 linked list 기능이 함께 포함되어 있다.
- linked list의 연결된 엘리먼트들은 노드(node, 마디, 교점) or 버텍스(vertex, 정점, 꼭지점)라고 부른다.
- 연결되는 방향에 따라 3가지 종류가 있다.
Singly linked list (단일 연결 리스트),
Doubly linked list(이중 연결 리스트),
Circular linked list(환형 연결 리스트)
연결 리스트는 아래와 같이 선언할 수 있다.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None생각해보기
연결 리스트를 배열과 비교했을 때 장단점은 무엇이 있을까요?
위 그림과 같이 배열과 연결 리스트는 서로 반대되는 특성을 가지고 있다.
배열: 선언할 때 크기가 고정되고 인덱스를 통해 원하는 곳에 빠른 접근, 검색이 가능하다.
연결 리스트: 크기가 동적이고 데이터의 삽입, 삭제가 간편하다.
따라서 수정/삽입이 많은 상황은 연결 리스트, 값을 검색하는 상황이 많다면 배열을 사용하는 것이 더 좋다.
