링크드 리스트(Linked List)란 무엇인가
링크드 리스트는 선형 자료구조로서, 각 노드가 다음 노드를 가리키는 형태를 가지고 있다. 서로 꼬리를 물고 있다고 생각할 수 있다. 각 노드는 동적으로 할당되므로, 노드들 사이의 주소 값은 연속적이지 않다.
링크드 리스트의 구조
- 노드(Node) : 링크드 리스트를 구성하는 가장 작은 단위 독립된 객체. 노드라는 객체 안에는 데이터를 담는 공간과 다음 주소를 담는 공간, 두가지 종류의 공간(컴포넌트)만 존재한다.
- 데이터(Data) : 자료구조에 저장하고자 하는 실제 값
- 넥스트 포인터(Next Pointer) : 다음 노드가 메모리의 어느 주소에 있는지 가리키는 참조값
- 헤드(Head) : 리스트의 시작점. 가장 첫 번째 노드를 가리킨다. Head를 잃어버리면 리스트 전체를 잃어버리게 된다.
링크드 리스트의 동작 원리
1. 데이터 탐색
배열처럼 인덱싱으로 데이터에 접근할 수 없다. 무조건 Head (첫 번째 노드)부터 시작해서 원하는 값이 나올 때까지 Next를 타고 하나씩 접근해야한다. (이를 '순차 접근'이라고 한다)
2. 데이터 추가 (삽입)
- 새 노드를 생성하고 데이터를 담는다.
- 새 노드의 Next가 삽입할 위치의 다음 노드를 가리키게 한다.
- 삽입할 위치 이전 노드의 Next가 새 노드를 가리키게 업데이트 한다.
3. 데이터 삭제
- 삭제할 노드의 이전 노드를 찾는다.
- 이전 노드의 Next를 삭제할 노드의 '다음 노드'로 직접 연결한다.
- 연결이 끊어진 노드는 메모리에서 자동으로 정리된다. (Garbage Collection)
배열(Array)과 링크드 리스트 비교
| 특징 | 배열 (Array) | 링크드 리스트 (Linked List) |
| 메모리 할당 | 선언 시점에 연속된 공간을 통째로 잡음 (정적) | 필요할 때마다 동적으로 노드를 생성함 (동적) |
| 데이터 접근 (조회) | 인덱스로 즉시 접근 가능 (O(1)) | Head부터 순서대로 찾아가야 함 (O(N)) |
| 삽입 / 삭제 | 데이터를 밀고 당겨야 해서 느림 (O(N)) | 포인터만 바꾸면 되므로 빠름 (O(1)) 단, 위치 찾는 시간 제외 |
| 메모리 효율 | 빈 공간이 남을 수 있어 낭비 가능성 있음 | 다음 노드 주소 (Pointer)를 저장하는 오버헤드 발생 |
배열에 비해 링크드 리스트의 장점
- 동적 메모리 할당 : 링크드 리스트는 실행 중에도 데이터 크기를 유연하게 조정할 수 있어, 미리 데이터 크기를 알 필요가 없다.
- 삽입/삭제 용이 : 중간에 있는 요소를 삽입하거나 삭제할 때, 링크드 리스트는 포인터만 조정하면 되므로 상대적으로 간편하다.
- 메모리 효율 : 링크드 리스트는 불필요한 메모리를 미리 할당하지 않아 메모리 사용 효율성이 높다.
- 데이터 타입의 다양성 : 링크드 리스트는 다양한 타입의 데이터를 한 리스트 안에서 저장할 수 있어, 유연성이 높다.
배열에 비해 링크드 리스트의 단점
- 메모리 사용 비효율 : 각 노드는 데이터와 함께 다음 노드를 가리키는 포인터도 저장해야해서 추가적인 메모리를 필요로 한다.
- 코드 복잡성 : 링크드 리스트를 사용하면 삽입과 삭제를 위해 추가적인 코드가 필요하므로 배열에 비해 코드가 복잡해질 수 있다.
- 시간 복잡도 : 특정 요소를 찾는데 있어서 배열에 비해 시간이 더 걸릴 수 있다.
링크드 리스트의 장, 단점
장점
- 동적 크기 조절 : 데이터가 몇 개 들어올지 미리 몰라도 된다. 실행 중에 마음대로 늘리고 줄일 수 있다.
- 빠른 삽입 / 삭제 : 빈번하게 데이터가 추가되고 삭제되는 환경에서 성능이 뛰어나다.
단점
- 느린 접근 속도 : 데이터가 100만개 있다면 100만 번째 데이터를 찾기 위해 앞의 99만 9999개를 다 거쳐가야 한다.
- 메모리 추가 소비 : 데이터 외에 '다음 주소'를 저장할 공간이 추가로 필요하다.
실제 사용 사례
- 웹 브라우저의 '뒤로가기' / '앞으로 가기' : 방문한 페이지들을 링크로 연결하여 관리한다.
- 음악 플레이어의 재생 목록 : 노래들이 순서대로 연결되어 있고, 중간에 곡을 추가하거나 삭제하기 편하다.
- 운영체제의 메모리 관리 : 동적 메모리 할당 시 빈 메모리 블록들을 관리 (Free List)하기 위해 사용된다.
- 다른 자료구조의 구현 : 큐(Queue), 스택(Stack) 등의 추상 자료구조를 내부적으로 구현할 때 활용된다.
- 텍스트 에디터의 'Ctrl + Z' (Undo) : 사용자의 행동 이력을 링크 형태로 관리한다.
링크드 리스트(Singly Linked List) 구현
Node 클래스 구현
class Node:
def __init__(self, data):
self.data = data # 저장할 데이터
self.next = None # 다음 노드를 가리키는 포인터LinkedList 클래스 구현
class LinkedList:
def __init__(self):
self.head = None # 시작 노드삽입, 삭제, 조회 기능 구현
데이터 삽입
def insert(self, target_data=None, new_data=None):
"""삽입
target_data=None : 맨 뒤 추가
target_data 지정 : 해당 노드 뒤 삽입
"""
new_node = Node(new_data)
if self.head is None: # 빈 리스트라면 target과 상관없이 새 노드가 Head
self.head = new_node
return True
if target_data is None: # 맨 뒤에 데이터를 추가하고자 하는 경우
current = self.head
while current.next: # 맨 마지막 노드가 나올 때까지 진행
current = current.next
current.next = new_node # 마지막 노드 뒤에 새 노드 연결
return True
current = self.head
while current: # 원하는 데이터 뒤에 새로운 데이터 추가
if current.data == target_data:
new_node.next = current.next
current.next = new_node
return True
current = current.next
print(f"[삽입 실패] '{target_data}'를 찾지 못했습니다.")
return False
데이터 삭제
def delete(self, data):
"""삭제"""
if self.head is None:
print("[삭제 실패] 리스트가 비어있습니다.")
return False
if self.head.data == data: # 삭제할 데이터가 첫 번째 노드인 경우
self.head = self.head.next # Head를 다음 노드로 변경
return True
current = self.head
while current.next: # 삭제할 데이터가 첫 번째가 아닌 경우
if current.next.data == data:
current.next = current.next.next # 노드를 다다음 노드로 건너뛰어준다.
return True
current = current.next
print(f"[삭제 실패] '{data}'를 찾지 못했습니다.")
return False
데이터 조회
def search(self, data):
"""데이터 조회"""
current = self.head
index = 0
while current: # 원하는 데이터의 인덱스 검색
if current.data == data:
return index
current = current.next
index += 1
return -1 # 데이터가 없다면 -1 값 반환더블 링크드 리스트 (Doubly Linked List)
단일 링크드 리스트(Singly Linked List)는 뒤로만 갈 수 있고, 앞으로는 돌아가지 못한다는 단점이 있다. 이를 해결하고자 양방향으로 모두 진행 가능한 리스트가 더블 링크드 리스트이다.
더블 링크드 리스트의 구조
- 헤드 (Head) : 가장 앞의 노드
- 이전 포인터 (Prev Pointer) : 내 바로 앞 노드가 메모리 어디에 있는지 가리킨다. (첫 번째 노드의 prev는 None)
- 데이터 (Data) : 저장하고자 하는 실제 값.
- 다음 포인터 (Next Pointer) : 내 바로 뒤 노드가 메모리 어디에 있는지 가리킨다. (마지막 노드의 next는 None)
- 테일 (Tail) : 가장 마지막 노드
더블 링크드 리스트의 장,단점
장점 : 양방향 탐색 가능
- 양방향 탐색 가능 : 앞 방향뿐만 아니라 뒤 방향으로도 탐색(역추적)이 가능하다. 특정 노드에서 이전 노드로 바로 접근할 수 있어 유연하다.
단점 : 관리 비용의 증가
- 메모리 사용량 증가 : 노드마다 주소를 저장할 공간 (prev)이 하나씩 더 추가되어 메모리 사용량이 많아진다.
- 구현 및 관리 복잡성 : 데이터를 삽입하거나 삭제할 때, 앞뒤 포인터를 모두 끊고 다시 연결해 주어야 하므로, 조건문 처리가 까다롭고 코드가 복잡해진다.
'자료구조, 알고리즘' 카테고리의 다른 글
| 공간 복잡도 (0) | 2026.06.07 |
|---|---|
| 시간 복잡도 (0) | 2026.06.07 |
| 해시 테이블 (Hash Table) (0) | 2026.06.05 |
| 트리(Tree) (0) | 2026.06.03 |
| 자료구조의 개념과 동작 원리 (0) | 2026.05.31 |