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

1. 연결 리스트란?

연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 즉, 어떤 데이터(node)를 저장할 때 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식이라고 생각하면 된다.

예를 들어 한 반에 있는 학생들의 자료를 저장한다면 학생 하나하나의 신상명세 자료를 노드로 만들고, 1번 학생의 신상명세 자료에 2번 학생의 신상명세 자료가 어디 있는지 표시를 해놓는 방식이다.

2. 연결 리스트의 성질

• 단일 연결 리스트 (Singly Linked List)

각 node가 다음 node의 주소를 가지고 있는 구조의 연결 리스트이다. Head 노드를 참조하는 주소를 잃어버릴 경우 데이터 전체를 못 쓰게 되는 단점이 있다. 또한 다음 노드를 참조하는 주소 중 하나가 잘못되는 경우에도 해당 노드부터 뒤쪽 자료들을 유실한다. 따라서 안정적인 자료구조는 아니다.

• 이중 연결 리스트 (Doubly Linked List)

각 node가 자신의 이전 node와 다음 node의 주소를 둘 다 가지고 있는 구조의 연결 리스트이다. 관리해야 할 참조가 두 개나 있기 때문에 삽입과 정렬의 경우 작업량이 많고 자료구조의 크기가 더 커진다. 대신 삭제의 경우 단일 연결 리스트에 비해 간단하다.

• 원형 연결 리스트 (Circular Linked List)

단일 연결 리스트에서 마지막 원소가 null 대신 처음 원소를 가리키는 구조의 연결 리스트이다.

• 캐시 적중률(Cache hit rate)이 낮다.

메모리 상에 데이터들이 연속해 있지 않아 캐시 적중률이 낮다.

3. 연결 리스트의 연산

• 임의의 위치에 있는 원소 확인/변경 - \(O(N)\)

임의의 위치에 있는 원소를 확인하기 위해서는 그 위치에 도달할 때까지 첫 번째부터 순차적으로 방문을 해야 한다.

• 임의의 위치에 원소를 추가/제거하는 과정 - \(O(1)\)

특정 위치에 원소를 추가하거나 제거할 때는 해당 위치의 원소가 가리키는 주소값과 이전 원소가 가리키는 주소값만 변경해 주면 되기 때문에 \(O(1)\)의 시간 복잡도를 갖는다. 대신, 추가하고 싶은 원소의 주소값을 알아야 한다. 주소를 준 것이 아니라, 몇 번째 원소 뒤에 데이터를 추가 혹은 제거하라는 명령 같은 경우에는 해당 원소까지 찾아가야 하기 때문에 추가적인 시간이 걸려 \(O(1)\)의 시간 복잡도를 갖지 않는다.

4. 연결 리스트의 사용

연산에서 보았듯이, 임의의 위치에 있는 원소를 확인하거나 변경할 때 배열보다 많은 시간 복잡도를 갖는데 이 연결 리스트를 어떤 경우에 사용해야 할까?

탐색/정렬을 자주 하면 배열을, 추가/삭제가 많으면 연결리스트를 사용하는 것이 유리하다. 예를 들어 커서를 옮기고 글자를 지우는 것과 같이 연산들이 다양하게 주어진 후 최종 결과를 출력하라는 문제가 있을 때 우리는 커서가 가리키는 위치에 문자를 추가하거나 삭제하는 명령을 계속 수행해야 한다. 배열의 경우 임의의 위치에 글자를 추가하는 연산이 비효율적인데 (뒤의 원소를 다 밀어야 함) 연결 리스트에서는 \(O(1)\)에 처리할 수 있어 연결 리스트로 구현할 경우에 더 효율적이다.