[자료구조] 연결리스트

배열(파이썬에선 list)과 유사하지만 다른(사촌형제쯤 되는?) 자료구조가 있다.
바로 포인터로 노드를 연결하는 연결 리스트(Linked List)다.
“왜 굳이 평소에 쓰던 배열 대신 연결 리스트를 배워야 하지?” 하는 의문이 들 테니, 이 글에서 배열과의 차이점도 하나씩 비교해 보자.

연결 리스트란?

연결 리스트는 노드(node)라는 작은 단위 객체들이 data와 next 포인터를 가지고, 줄줄이 연결된 형태다.

이 때 메모리 저장 관점에서 보면 배열처럼 메모리에 연속적으로 저장되지 않고,

각 노드는 다음 노드의 주소를 기억할 뿐 흩어져 있는 상태이다.

노드 하나는 (값 Data, 다음 노드 참조 Next) 쌍으로 이루어져 있다.
리스트의 시작 노드를 Head라 부른다.
마지막 노드는 next = None으로 리스트의 끝을 가리킨다.

연결 리스트 구조

아래 그림처럼, 메모리 어딘가에 흩어진 노드들이 next 포인터로 이어진다.

https://www.datacamp.com/tutorial/python-linked-lists

이를 파이썬 코드로 직접 구현해보면 아래와 같다.

class Node:
    def __init__(self, data):
        self.data = data        # 노드가 포함할 실제 정보를 나타내는 값
        self.next = None        # 다음 노드의 주소

class LinkedList:
    def __init__(self):
        self.head = None        # 리스트의 시작점, 처음에는 연결리스트 초기화를 위해 None 지정

연결 리스트의 특징

1. 삽입·삭제에 용이

배열은 중간에 요소를 삽입하거나 삭제할 때, 뒤에 있는 모든 요소를 한 칸씩 뒤로 밀거나 당겨야 한다. 그리고 이 과정에 O(N) 시간이 소요된다.
연결 리스트는 삽입·삭제 대상 노드의 앞뒤 포인터만 재조정하면 되므로 **O(1)**에 처리할 수 있다.

2. 탐색·접근은 불리

배열은 인덱스로 곧바로 원하는 위치에 접근할 수 있으므로 O(1) 시간에 요소를 읽거나 변경할 수 있다.
연결 리스트는 head부터 차례로 순회하며 원하는 노드까지 이동해야 하므로 O(N) 시간이 걸린다.

3. 메모리 배치

일반 배열은 메모리에 데이터를 연속된 블록으로 저장하며, N × element_size 만큼만 차지한다.
연결 리스트는 각 노드가 흩어져서 할당되며, 노드당 데이터(element_size) 외에 다음 노드를 가리키는 포인터(pointer_size)가 추가로 필요하다.

그렇다면 일반적인 배열이 아닌 파이썬 `list`는 어떨까?

대부분 언어에서 배열과 연결 리스트는 메모리 배치부터 완전히 다르다.

파이썬의 list는 일반 배열과 달리 C로 구현된 동적 배열이다.

이 동적 배열은 실제 값을 직접 저장하지 않고, **요소에 대한 참조(PyObject*)**를 연속된 메모리 블록에 담는다.

여기서 중요한 차이가 있다.

파이썬 list는 참조 배열 자체는 연속된 메모리에 저장된다.
연결 리스트는 노드 객체가 흩어져 있고, 각 노드가 next 참조를 하나 더 가진다.

즉, 둘 다 "객체를 직접 복사하지 않고 참조를 다룬다"는 공통점은 있지만, 메모리 특성이 같다고 보긴 어렵다.

오히려 파이썬에서는 연결 리스트가

노드 객체 오버헤드가 더 크고
캐시 친화성도 떨어지기 때문에

실전 성능과 메모리 면에서 더 불리한 경우가 많다.

그래서 파이썬에서 list와 연결 리스트를 비교할 때는 "둘 다 참조를 쓰니 비슷하다"기보다,

동적 배열과 노드 기반 구조가 어떤 비용을 내는지로 보는 편이 더 정확하다.

그래서 언제 연결 리스트를 쓰면 좋은데?

연결 리스트는 아래와 같이 빈번한 삽입·삭제, 크기 예측 불가 상황에서 빛을 발한다.

자주 많은 요소를 삽입하고 삭제해야 할 때

데이터 크기가 예측 불가능하거나 자주 변할 때

반면 특정 위치에 임의 접근이 필요하거나, 대용량 데이터를 연속적으로 순회할 일이 많다면 배열이 더 유리하다.

결론

사실 연결 리스트 자체를 직접 쓰는 일은 알고리즘 문제 풀이를 제외하면 흔하지 않다. 파이썬은 내장 자료구조로 연결 리스트를 직접 제공하지도 않아서, 보통은 직접 구현해야 한다.

그럼에도 연결 리스트를 배우는 이유는 명확하다.

트리(Tree)나 그래프(Graph), 해시 테이블의 체이닝 방식 같은 구조는 모두 노드와 포인터를 이어 붙이는 형태로 동작한다.
포인터와 참조가 어떻게 이어지는지 감을 잡아두면, 더 복잡한 자료구조를 이해할 때 훨씬 수월하다.

그래서 연결 리스트는 실무에서 자주 직접 쓰는 자료구조라기보다, 다음 단계 자료구조를 이해하기 위한 기본 훈련에 가깝다.