연결리스트 (Linked List)

연결리스트란?

Singly Linked List

배열이 메모리의 공간을 연속적으로 할당받은 형태라면, 연결리스트는 연속적이지 않고 빈 공간 어디든 할당받는 형태다. 데이터가 여기저기 산재해있으니 각 데이터는 자신의 다음 데이터가 어디에 있는지 알아야 한다. 그래서 연결리스트의 데이터는 값 뿐만 아니라 다음 데이터의 주소값도 가지고 있다.

 

연결리스트의 한 데이터(데이터와 주소값)을 노드(Node) 라고 부른다. 노드들은 다음 노드의 주소를 가지고 있음으로써 연결된다. 맨 끝의 노드는 자신이 끝이라는 걸 알리기 위해 Null 값을 가진다.

Doubly Linked List

기본적인 연결 리스트는 단방향으로만 연결되어 있어 현재 노드의 이전 노드를 알 수 없다. 이를 개선한 것이 이중 연결리스트 (Doubly Linked List) 이다. 현재 노드가 이전/다음 노드의 주소값을 모두 가지고 있는 형태다.

 

또 맨 끝에 Null 을 두지 않고 첫번째 노드를 가리켜 마치 원형처럼 만든 원형 연결 리스트 (Circular Linked List) 도 있다.

 

연결리스트의 연산

READ

배열은 연속적으로 공간을 차지하고 있어서 인덱스를 이용해 원하는 위치를 바로 읽을 수 있었다. 연결리스트는 첫 노드(Head)의 정보만 알 수 있기에 Head 의 연결고리를 타고 타고 다음 노드를 찾아가는 식으로 읽는다. 최악의 경우 전부 탐색하는 것이므로 O(n) 의 시간복잡도를 가진다.

SEARCH

READ와 같다. Head 의 연결고리를 타고타고 다음 노드를 찾아 값을 비교해 검색하는 방식이라 검색 속도가 느리다. Best는 Head가 가지고 있는 경우고, 최악의 경우는 맨 끝에 있는 것이다. 따라서 O(n) 의 시간복잡도를 가진다.

 

INSERT

추가할 위치의 이전 노드는 추가하는 노드를 가리키게 하고, 추가하는 노드는 다음 노드를 가리키게 하면 된다. 이 경우에도 추가할 위치를 찾아가야 하므로 O(n) 의 시간복잡도를 가진다.

 

DELETE

삭제하는 노드의 이전 노드가 삭제하는 노드의 다음 노드를 가리키게 하면 된다. 삭제한 노드는 연결 고리를 잃었으니 아무런 처리를 하지 않아도 되지만, 메모리를 차지하고 있으니 자동으로 메모리 정리를 하지 않는 언어에서는 할당을 해제해줘야 한다. 이 경우에도 위치를 찾아가야 하므로 O(n) 의 시간복잡도를 가진다.

정리

연결리스트는 배열과 달리 미리 공간을 할당받지 않고 불연속적인 공간에 저장한다. 빈 공간을 관리하지 않아도 되고, 길이를 신경쓸 필요가 없으니 확장하기도 용이하다. 추가/삭제는 같은 시간복잡도를 가지지만, 데이터를 전부 하나하나 이동시키는 작업을 하지 않아도 되니 배열보다 쉽게 구현할 수 있다.

 

그러나 읽고 검색하는 데는 Head 부터 하나하나 거슬러 올라가야 하기 때문에 속도가 느리다. 게다가 이전/다음 노드의 주소값까지 가지고 있어야 하니 메모리 공간을 배열보다 더 차지한다. 배열보다 확장이 용이하기 때문에 확장의 용이성이 중요한 경우에 사용하면 좋다. 특히 이후 언급되는 👉 트리라는 자료구조를 표현하기 가장 적당해 주로 사용된다.