연결리스트(Linked List)란? 개념부터 구현까지 완벽 정리
프로그래밍을 공부하다 보면 연결리스트라는 용어를 자주 접하게 됩니다. 배열과 함께 가장 기본이 되는 자료구조인데, 막상 개념을 이해하려고 하면 어디서부터 시작해야 할지 막막하게 느껴지실 수 있습니다. 이 글에서는 연결리스트의 기본 개념부터 종류, 시간복잡도, 그리고 실제 구현 방법까지 체계적으로 정리해 드리겠습니다.
• • •
연결리스트란 무엇인가
연결리스트(Linked List)는 데이터를 저장하는 노드(Node)들이 포인터로 연결되어 있는 선형 자료구조입니다. 각 노드는 실제 데이터를 담는 데이터 필드와 다음 노드의 주소를 가리키는 포인터 필드로 구성됩니다. 배열이 연속된 메모리 공간에 데이터를 저장하는 것과 달리, 연결리스트는 메모리의 여러 위치에 분산되어 저장된 노드들을 논리적으로 연결하는 방식을 사용합니다.
쉽게 비유하자면, 배열은 아파트처럼 연속된 호수에 순서대로 사람들이 사는 것이고, 연결리스트는 각자 다른 위치에 살면서 다음 사람의 주소만 알고 있는 형태라고 생각할 수 있습니다. 첫 번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 부르며, 헤드 노드만 알면 전체 리스트를 순회할 수 있습니다.
• • •
📌 관련 글
연결리스트의 종류
단일 연결리스트 (Singly Linked List)
가장 기본적인 형태의 연결리스트입니다. 각 노드가 다음 노드만 가리키므로 한 방향으로만 탐색이 가능합니다. 구현이 간단하고 메모리 사용량이 적지만, 이전 노드로 돌아가려면 처음부터 다시 탐색해야 하는 단점이 있습니다. 마지막 노드의 포인터는 NULL을 가리켜 리스트의 끝을 표시합니다.
이중 연결리스트 (Doubly Linked List)
각 노드가 이전 노드와 다음 노드 모두를 가리키는 두 개의 포인터를 가집니다. 양방향 탐색이 가능해 특정 노드에서 앞뒤로 자유롭게 이동할 수 있습니다. 단일 연결리스트의 탐색 제한을 해결했지만, 포인터를 하나 더 저장해야 하므로 메모리 사용량이 증가하고 구현이 조금 더 복잡해집니다.
원형 연결리스트 (Circular Linked List)
마지막 노드가 첫 번째 노드를 가리켜 순환 구조를 형성합니다. 리스트의 끝에서 다시 처음으로 돌아갈 수 있어 특정 응용 프로그램에서 유용합니다. 예를 들어 음악 플레이어의 반복 재생 기능이나 라운드 로빈 스케줄링에 활용됩니다.
자료구조에 대한 더 자세한 내용은 위키백과 연결 리스트 문서에서 확인하실 수 있습니다.
• • •
배열과 연결리스트 비교
연결리스트를 제대로 이해하려면 배열과의 차이점을 명확히 알아야 합니다. 두 자료구조는 각각 장단점이 있어 상황에 따라 적절히 선택해야 합니다. 배열은 인덱스를 통한 빠른 접근이 가능하지만 크기가 고정되어 있고, 연결리스트는 동적으로 크기를 조절할 수 있지만 특정 위치 접근이 느립니다.
| 구분 | 배열(Array) | 연결리스트(Linked List) |
|---|---|---|
| 메모리 구조 | 연속적인 메모리 공간 | 분산된 메모리 공간 |
| 크기 변경 | 고정 크기 (변경 어려움) | 동적으로 크기 조절 가능 |
| 데이터 접근 | 인덱스로 O(1) 접근 | 순차 탐색으로 O(n) 접근 |
| 삽입/삭제 | O(n) - 데이터 이동 필요 | O(1) - 포인터만 변경 |
| 메모리 효율 | 데이터만 저장 | 포인터 추가 저장 필요 |
• • •
연결리스트의 시간복잡도
탐색 (Search)
연결리스트에서 특정 데이터를 찾으려면 헤드부터 순차적으로 탐색해야 합니다. 최악의 경우 모든 노드를 확인해야 하므로 시간복잡도는 O(n)입니다. 배열처럼 인덱스로 바로 접근하는 것이 불가능하기 때문에 데이터 조회가 빈번한 경우에는 배열이 더 적합합니다.
삽입과 삭제 (Insert & Delete)
연결리스트의 강점은 삽입과 삭제 연산에 있습니다. 삽입하거나 삭제할 위치의 노드를 이미 알고 있다면, 앞뒤 노드의 포인터만 변경하면 되므로 O(1)의 시간복잡도로 처리됩니다. 다만 해당 위치를 찾기 위한 탐색 시간은 별도로 O(n)이 소요될 수 있습니다. 헤드나 테일에 삽입하는 경우는 항상 O(1)입니다.
공간복잡도
연결리스트는 데이터 외에 포인터를 저장해야 하므로 배열보다 더 많은 메모리를 사용합니다. 단일 연결리스트는 노드당 포인터 하나, 이중 연결리스트는 포인터 두 개가 추가로 필요합니다. 32비트 시스템에서는 포인터가 4바이트, 64비트 시스템에서는 8바이트를 차지합니다.
• • •
연결리스트 구현 예제
Python으로 구현하기
파이썬에서 연결리스트를 구현할 때는 클래스를 활용합니다. 먼저 노드 클래스를 정의하고, 이 노드들을 연결하는 연결리스트 클래스를 만듭니다. 노드 클래스는 데이터를 저장하는 data 속성과 다음 노드를 가리키는 next 속성으로 구성됩니다. 파이썬의 기본 리스트는 사실 배열로 구현되어 있어 연결리스트와는 다르다는 점을 기억해야 합니다.
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def append(self, data): new_node = Node(data) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node
Java로 구현하기
자바에서는 java.util.LinkedList 클래스를 제공하지만, 직접 구현해보면 자료구조의 동작 원리를 더 깊이 이해할 수 있습니다. 자바에서는 포인터 대신 객체 참조를 사용하여 노드를 연결합니다. 제네릭을 활용하면 다양한 타입의 데이터를 저장할 수 있는 범용 연결리스트를 만들 수 있습니다.
프로그래밍 기초를 더 체계적으로 학습하고 싶다면 생활코딩 자료구조 강의를 참고하시기 바랍니다.
• • •
연결리스트의 활용 사례
스택과 큐 구현
연결리스트는 스택(Stack)과 큐(Queue)를 구현하는 데 자주 사용됩니다. 배열로 구현할 때와 달리 크기 제한이 없고, 삽입과 삭제가 효율적이기 때문입니다. 스택의 경우 헤드에서만 삽입과 삭제가 일어나고, 큐의 경우 한쪽에서 삽입, 다른 쪽에서 삭제가 일어납니다.
운영체제에서의 활용
운영체제에서 프로세스 관리나 메모리 할당에 연결리스트가 활용됩니다. 실행 대기 중인 프로세스 목록 관리, 사용 가능한 메모리 블록 추적 등에 연결리스트의 동적 특성이 유용하게 쓰입니다. 파일 시스템에서 큰 파일을 여러 블록에 나누어 저장할 때도 연결리스트 방식을 사용합니다.
다른 자료구조의 기반
연결리스트는 트리(Tree), 그래프(Graph), 해시 테이블의 체이닝 등 복잡한 자료구조를 구현하는 기반이 됩니다. 특히 이진 탐색 트리나 그래프의 인접 리스트 표현에서 연결리스트 개념이 핵심적으로 사용됩니다. 따라서 연결리스트를 확실히 이해하면 다른 자료구조 학습이 훨씬 수월해집니다.
• • •
✅ 꼭 알아두세요
- 연결리스트 선택 기준: 데이터의 삽입/삭제가 빈번하면 연결리스트, 조회가 빈번하면 배열이 적합합니다.
- 메모리 고려: 연결리스트는 포인터 저장을 위한 추가 메모리가 필요하므로 작은 데이터가 많을 때는 오버헤드가 클 수 있습니다.
- 구현 시 주의점: 노드 삽입/삭제 시 포인터 연결 순서를 잘못하면 데이터 손실이 발생할 수 있으니 신중하게 작성해야 합니다.
- 이중 연결리스트 권장: 실무에서는 양방향 탐색이 가능한 이중 연결리스트를 더 많이 사용합니다.
• • •
Q. 연결리스트와 배열 중 어떤 것을 사용해야 하나요?
A. 데이터의 크기가 자주 변하고 삽입/삭제가 빈번하다면 연결리스트가 적합합니다. 반면 데이터 크기가 고정적이고 인덱스를 통한 빠른 접근이 필요하다면 배열을 선택하세요. 두 자료구조의 특성을 이해하고 상황에 맞게 선택하는 것이 중요합니다.
Q. 파이썬의 리스트(list)는 연결리스트인가요?
A. 아닙니다. 파이썬의 list는 내부적으로 동적 배열(Dynamic Array)로 구현되어 있습니다. 인덱스로 O(1) 접근이 가능한 것이 그 증거입니다. 파이썬에서 연결리스트를 사용하려면 직접 구현하거나 collections.deque를 활용할 수 있습니다.
Q. 연결리스트의 단점을 보완하는 방법이 있나요?
A. 탐색 속도를 개선하기 위해 스킵 리스트(Skip List)를 사용하거나, 자주 접근하는 노드를 캐싱하는 방법이 있습니다. 또한 이중 연결리스트를 사용하면 양방향 탐색이 가능해 특정 상황에서 효율성을 높일 수 있습니다.
• • •
📖 함께 읽으면 좋은 글
- 연말정산외주 대행 서비스 완벽 가이드 | 비용, 장점, 선택 기준 총정리
- 한국범용공인인증서 발급 방법 및 비용, 사용처 완벽 가이드 2025
- 소득세계산법 완벽 정리|2025년 세율표와 계산 방법 총정리
마치며
연결리스트는 배열과 함께 가장 기본이 되는 자료구조로, 동적인 데이터 관리가 필요한 다양한 상황에서 활용됩니다. 핵심은 노드와 포인터의 개념을 이해하고, 배열과의 차이점을 명확히 파악하는 것입니다. 직접 코드로 구현해보면서 삽입, 삭제, 탐색 과정을 익히면 다른 고급 자료구조 학습에도 큰 도움이 될 것입니다.