[자료 구조] 연결 리스트(Linked list)

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료 구조이다.
데이터를 담고 있는 노드들이 서로 연결되어 있는데, 노드의 포인터가 다음이나 이전 노드와의 연결을 담당하게 된다.
첫 번째 노드를 헤드(head), 마지막 노드를 테일(Tail)이라고 한다.

성능

• 어느 위치에 있는 노드이든지 추가/제거에 O(1)의 시간복잡도를 가진다.
• 특정 위치 데이터 탐색에 O(n)의 시간복잡도를 가진다.

장점

• 노드의 포인터만 변경하기만 하면 되기 때문에 데이터 추가, 삽입, 제거에 유리하다.
• 이중 연결 리스트, 원형 연결 리스트는 특정 인덱스 탐색 시 리스트 길이의 1/2보다 클 경우는 tail 에서부터 prev를 조회, 반대의 경우는 head 부터 next를 조회하여 탐색할 수 있다.
• 원형 연결 리스트는 head에서 tail까지의 시간 복잡도가 O(1)이다.(원래는 O(n))

단점

• 데이터를 탐섹하기 위해서는 처음부터 끝까지 선형 탐색을 해야하기 때문에, 탐색에 불리하다.
• 다음 노드 또는 이전 노드를를 가르키는 필드가 존재하기 때문에 데이터 이외에도 메모리가 더 필요하다.
• 원형 연결 리스트는 무한 루프에 빠질 수 있는 위험이 있다.

종류

• 단일 연결 리스트(singly linked list)
• 이중 연결 리스트(doubly linked list)
• 원형 연결 리스트(circular linked list)

노드의 소멸

해당 객체를 참조하는 객체가 존재하지 않을 경우 가비지 콜렉터에 의해서 메모리에서 자동으로 해제됨.

언어에 따라서 메모리를 직접 해제 해줘야하는 경우도 있음.

Code

• Github에서 단일 연결 리스트 코드 보기
• Github에서 이중 연결 리스트 코드 보기
• Github에서 원형 연결 리스트 코드 보기

Usage

• Python collections 모듈의 deque
• 웹 브라우저의 history