배열에서는 보통 중간에 항목을 끼워 넣을 때 뒤쪽 항목을 옮겨야 하지만, 연결 리스트는 각 항목이 다음 항목을 가리켜 순서를 만든다. 데이터를 담는 칸을 ‘노드’, 다음 칸의 위치를 가리키는 정보를 ‘링크’라고 한다. 노드들이 메모리의 이웃한 자리에 놓일 필요는 없다. 이미 위치를 찾았다면 링크를 고쳐 삽입할 수 있지만, 원하는 값을 찾으려면 앞에서부터 연결을 따라가야 한다.[1]

1. 노드와 연결 구조

단일 연결 리스트의 노드는 데이터와 다음 노드를 가리키는 링크를 가진다. 마지막 노드의 링크는 더 이어지는 노드가 없음을 나타내는 널(null) 참조다. 헤드가 널이면 빈 리스트로 표현할 수 있다. 구현은 빈 리스트를 별도 센티널 노드로 나타내기도 하므로, 널 규칙은 자료구조의 보편적 정의라기보다 흔한 구현 관례다.[1] 연결 리스트는 자료구조 중 하나이며, 링크는 메모리 주소나 객체 참조를 저장하고 노드의 데이터 자체와 구분된다.

2. 유형과 순회 방식

단일 연결 리스트의 노드는 다음 노드로 가는 링크 하나를 둔다. 앞에서 뒤로 순회하기 간단하고 참조 공간을 적게 쓰지만, 이전 노드로 바로 돌아갈 수는 없다. 이중 연결 리스트는 다음 노드와 이전 노드를 가리키는 링크를 모두 두므로 양방향 순회와 특정 노드에서의 삭제 처리가 편리해지는 대신, 참조 공간이 더 들고 링크 갱신 규칙도 늘어난다.[1][2]

원형 연결 리스트는 끝 노드가 헤드 쪽을 가리키게 하여 순환 순회를 표현한다. 원형 구조에서는 널 도달을 종료 조건으로 쓰지 않으므로, 시작 노드로 돌아왔는지 또는 정해진 횟수만큼 순회했는지 확인해야 한다. 이 구조는 순환적으로 항목을 처리하는 상황에 맞게 사용할 수 있지만, 종료 조건을 잘못 설정하면 무한 순회가 생길 수 있다.[1]

3. 탐색과 연산 비용

헤드만 주어진 단일 연결 리스트에서 인덱스나 값으로 노드를 찾으려면 앞에서부터 링크를 따라가야 하므로 최악의 경우 노드 수 n에 비례하는 O(n) 시간이 든다. 이 구조는 배열처럼 인덱스로 임의 위치에 O(1) 접근하지 못한다. 정렬 리스트에 이진 탐색을 적용하더라도 중간 위치로 가는 링크 순회가 필요해 전체 순회 횟수는 선형이며, 비교 횟수가 로그 수준이라는 사실만으로 전체 실행 시간이 O(log n)이 되지는 않는다.[1]

삽입·삭제는 대상 위치를 이미 가리키는 노드 참조가 있을 때 링크 몇 개를 바꾸는 O(1) 작업으로 처리할 수 있다. 그러나 값이나 인덱스를 기준으로 그 위치를 먼저 찾아야 하면 탐색 시간이 추가되어 전체 연산은 O(n)이 될 수 있다. 단일 연결 리스트에서 노드를 삭제하려면 일반적으로 삭제 대상의 이전 노드가 필요하므로 대상 노드 참조만으로 충분하지 않을 수 있다. 이중 연결 리스트는 이전 링크를 통해 이 제약을 줄인다. 끝에 추가하는 비용도 꼬리 포인터를 유지하는지에 따라 달라진다. 따라서 “연결 리스트의 삽입과 삭제는 빠르다”는 표현은 위치를 이미 알고 있고 관련 링크를 확보했다는 조건을 밝혀야 정확하다.[1][2] 이 구분은 시간-복잡도를 비교할 때도 중요하다.

4. 배열과의 선택 기준

배열은 인덱스로 요소에 직접 접근하기 쉽고, 요소가 연속된 메모리에 저장되는 구현에서는 순회 중 메모리 지역성의 이점도 얻을 수 있다. 연결 리스트는 노드별 참조를 저장하고 링크를 따라가야 하므로 인덱스 접근과 순회에 불리할 수 있다. 반대로 리스트 중간에서 위치를 이미 확보한 경우 배열처럼 뒤 요소를 연달아 옮기지 않고 링크를 고쳐 삽입·삭제할 수 있다. 실제 선택은 접근 패턴, 위치 탐색 비용, 메모리 사용과 구현의 부가 비용을 함께 고려해야 한다.[2]

Java의 LinkedList는 이중 연결 리스트로 구현되며 List와 Deque 인터페이스를 구현한다. Oracle API 설명은 인덱스 기반 연산이 지정 인덱스와 가까운 앞 또는 뒤에서 리스트를 순회한다고 명시한다. 그러므로 이 클래스가 목록이나 덱 연산을 제공한다는 사실이 임의 인덱스 접근을 상수 시간으로 만든다는 뜻은 아니다. 이는 자료구조의 일반적 특성과 특정 라이브러리 구현을 구분해 읽어야 하는 사례다.[2]

5. 활용과 구현 시 주의점

연결 리스트는 스택이나 큐처럼 양 끝 또는 한쪽 끝에서 반복적으로 삽입·삭제하는 추상 자료형의 구현에 사용할 수 있다. NIST 사전은 큐와 스택, 희소 행렬 등의 구현 사례를 든다. 그래프 표현에서도 정점마다 이웃 목록을 두는 방식에 연결 구조를 활용할 수 있지만, 구체 구현은 동적 배열 등 다른 저장 방식을 쓸 수도 있으므로 인접 목록과 연결 리스트를 동일한 것으로 단정해서는 안 된다.[1]

연결 리스트를 구현할 때는 빈 리스트, 첫 노드와 마지막 노드 변경, 노드가 하나뿐인 경우, 순회 중 삭제를 별도로 다뤄야 한다. 링크 하나를 잘못 갱신하면 일부 노드에 도달하지 못하거나 순환이 의도치 않게 생길 수 있다. 메모리를 직접 관리하는 언어에서는 제거된 노드의 수명과 해제를 관리해야 하고, 참조 관리 언어에서도 불필요한 참조가 남으면 객체가 회수되지 않을 수 있다. 이런 경계 조건은 자료구조의 성능 특성만큼 구현 정확성에 영향을 준다.[2]

6. 관련 문서

7. 인용 및 각주

[1] Paul E. Black, NIST Dictionary of Algorithms and Data Structures, “linked list”, Xxlinux.nist.gov(새 탭에서 열림)

[2] Oracle, Java Platform Standard Edition 8 API, “Class LinkedList<E>”, Ddocs.oracle.com(새 탭에서 열림)