1. 들어가며
연결 리스트(Linked List)는 데이터를 노드(Node) 단위로 저장하고 각 노드가 다음 노드의 참조(reference) 를 통해 서로 연결된 선형 자료구조입니다.
배열처럼 메모리에 연속적으로 저장되지 않으며 메모리의 임의 위치에 존재하는 노드들이 포인터(pointer) 를 통해 논리적으로 연결됩니다.
이 구조는 메모리의 불연속성을 극복하면서 유연하게 데이터를 관리할 수 있게 해줍니다.
2. 연결리스트 내부 구조 이해
각 노드는 일반적으로 다음 두 가지 정보를 가집니다.
- data: 저장할 실제 데이터
- next: 다음 노드의 주소(참조)
class Node {
int data;
Node next; // 다음 노드를 가리킴
Node(int data) {
this.data = data;
this.next = null;
}
}리스트의 시작점은 head 노드가 가리킵니다.
head → [10 | *] → [20 | *] → [30 | null]
head 만 알고 있어도 순차 탐색 가능하지만 역방향 탐색은 불가능 합니다.(이 부분은 뒤의 ‘이중 연결 리스트’에서 해결됩니다.)
3. 종류별 비교
| 단일 연결 리스트 (Singly) | 한 방향(next) | 구현 단순, 메모리 효율 좋음 | 기본 리스트 |
| 이중 연결 리스트 (Doubly) | 양방향(prev, next) | 앞뒤 탐색 가능, 삽입/삭제 유연 | LRU Cache, Deque |
| 원형 연결 리스트 (Circular) | 마지막 노드가 첫 노드 연결 | 순환 구조, 반복 탐색 가능 | 라운드 로빈 스케줄링 |
4. 시간 복잡도 분석
| 접근(access) | O(n) | 임의 인덱스 접근 불가, 순차 탐색 필요 |
| 탐색(search) | O(n) | 모든 노드 순회 |
| 맨 앞 삽입(addFirst) | O(1) | 포인터만 변경 |
| 맨 뒤 삽입(addLast) | O(n) (tail 없을 때) / O(1) (tail 유지 시) | |
| 삭제(remove) | O(n) | 삭제 대상 이전 노드 탐색 필요 |
| 메모리 사용량 | O(n) | 포인터(참조) 추가로 인한 오버헤드 |
접근은 느리지만 구조 변경은 빠르다.
연결 리스트의 핵심은 ‘유연한 변경’입니다.
5. 배열과 다른점
| 메모리 구조 | 연속된 공간 | 불연속, 포인터로 연결 |
| 접근 속도 | O(1) | O(n) |
| 삽입/삭제 | O(n) (이동 필요) | O(1) (참조 변경) |
| 크기 변경 | 불가능(정적) / 복사 필요(동적) | 자유롭게 추가/삭제 |
| 캐시 효율 | 높음 (연속적) | 낮음 (비연속적) |
| 메모리 효율 | 우수 | 포인터로 인한 추가 사용 |
- 배열은 CPU 캐시 친화적 → 빠른 순회
- 연결 리스트는 구조 유연성 ↑, 메모리 효율 ↓
6. 메모리 동작 원리
연결 리스트는 힙(Heap) 메모리에 노드를 동적으로 할당합니다. 새로운 데이터를 추가하면 다음과 같은 과정이 일어납니다.
- JVM(혹은 런타임)이 new 명령으로 메모리를 힙에 확보
- 새 노드를 생성하고 데이터 저장
- 이전 노드의 next 포인터가 새 노드를 가리킴
이 과정은 연속된 메모리를 요구하지 않아 단편화(fragmentation) 가 심한 환경에서도 유연하게 동작합니다.
7. 삽입 / 삭제
삽입 (insert after)
Node newNode = new Node(25);
newNode.next = prev.next;
prev.next = newNode;
기존 노드를 밀어내지 않고 포인터만 교체합니다.
삭제 (delete)
prev.next = prev.next.next;삭제 대상의 참조를 끊으면 GC(가비지 컬렉터)가 자동 해제합니다.(단, C언어 등에서는 free()로 직접 메모리 해제해야 함.)
8. 자바(Java) 예제 구현
public class LinkedList {
private Node head;
private static class Node {
int data;
Node next;
Node(int data) { this.data = data; }
}
public void addFirst(int data) {
Node node = new Node(data);
node.next = head;
head = node;
}
public void addLast(int data) {
Node node = new Node(data);
if (head == null) {
head = node;
return;
}
Node cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
public void remove(int data) {
if (head == null) return;
if (head.data == data) {
head = head.next;
return;
}
Node cur = head;
while (cur.next != null && cur.next.data != data) {
cur = cur.next;
}
if (cur.next != null) cur.next = cur.next.next;
}
public void printList() {
Node cur = head;
while (cur != null) {
System.out.print(cur.data + " -> ");
cur = cur.next;
}
System.out.println("null");
}
}9. 언어별 구현 비교
| C | 포인터 사용 (struct Node*) | 직접 free() 필요 | 저수준 제어 가능 |
| Java | 참조(reference) 기반 | GC가 자동 해제 | 안전하지만 약간 느림 |
| Python | 객체 참조 + 동적 타입 | 자동 관리 | 리스트(list)는 배열 기반 |
| C++ STL | std::list | 자동 관리 | Doubly Linked List 기본 제공 |
10. 시간복잡도 총정리
| 접근(access) | O(n) | O(1) |
| 맨 앞 삽입(addFirst) | O(1) | O(n) |
| 맨 뒤 삽입(addLast) | O(1)* (tail 있을 경우) | O(1) amortized |
| 삭제(remove) | O(n) | O(n) |
| 탐색(search) | O(n) | O(n) |
| 공간복잡도 | O(n) | O(n) |
| 캐시효율 | 낮음 | 높음 |
11. 연결 리스트의 실질적 한계
많은 개발자들이 “삽입/삭제가 빠르다”는 이유만으로 연결 리스트를 선호하지만 현대 CPU 환경에서는 배열 기반 구조가 더 빠른 경우가 많습니다.
그 이유는 다음과 같습니다.
- 배열은 연속 메모리 덕분에 캐시 히트율이 압도적
- 연결 리스트는 각 노드 접근 시 추가 포인터 참조 연산 발생
- 작은 규모에서는 연결 리스트의 “O(1)” 삽입이 실질적으로 더 느릴 수 있음
즉, 연결 리스트의 강점은 “빅오 표기상의 이론적 효율”보다 “구조적 유연성”에 있습니다.
12. 연결리스트를 알아야 하는 이유
연결리스트를 이해하면 데이터가 서로 ‘어떻게 연결되어 흘러가는지’ 보이기 시작합니다.
“배열은 정적인 세상에서 강하고, 연결 리스트는 변화하는 세상에서 강하다.”
13. 요약 및 결론
| 정의 | 데이터와 포인터로 이루어진 노드들의 연결 구조 |
| 장점 | 삽입/삭제 O(1), 유연한 크기 관리 |
| 단점 | 접근 O(n), 캐시 비효율, 메모리 오버헤드 |
| 사용 시점 | 삽입/삭제가 잦고 데이터 크기가 가변적일 때 |
| 피해야 할 시점 | 탐색/조회 위주 로직, 실시간 고성능 시스템 |
정리
연결 리스트는 “메모리의 불연속성을 극복하는 유연한 구조” 배열은 “빠른 접근성과 캐시 효율을 극대화한 구조”
현대 환경에서는 배열 기반 구조(ArrayList) 가 더 자주 쓰이지만 스택, 큐, 그래프, 캐시 같은 “구조적 연결”이 중요한 곳에서는 여전히 필수입니다
'자료구조' 카테고리의 다른 글
| 스택(Stack): 마지막에 쌓은 것을 가장 먼저 꺼내는 구조 (0) | 2025.10.31 |
|---|---|
| 배열 (0) | 2025.10.29 |