HW)
파이썬으로 데이터 처리를 위해 관련 내용을 접하게 될 때마다 '자료 구조'를 이해하는 것이 정말 중요함을 다시 인식하게 된다. 이전에 스택(Stack)과 큐(Queue)에 대해서 알아봤듯이, 이번에는 (단일)연결리스트, (Single) Linked List, 와 양방향 연결리스트, Double Linked List, 에 대해서 이해해보자.
우선, 기본 구조인 '노드(node)'를 먼저 알아보자.
> 노드는 데이터를 저장하는 가장 기본적인 구조 단위로, 각 노드는 자신의 주소와 인접한 노드의 주소 정보를 저장하고 있다.
- 각 노드(Node)에서 저장된 이전(prev) 노드의 주소와 다음(next) 노드의 주소를 가리켜 Link (or Pointer) 라고 하며, 이 메모리 주소들이 노드들 사이에 어떤 관계로 엮여있는 지에 따라서 두 가지로, 즉 단일 연결 리스트(Single Linked List)와 양방향 연결리스트(Double Linked List)로 분류할 수 있다. 편의상, 두 가지 연결리스트들을 각각 SLL과 DLL로 부르도록 하겠다.
연결리스트를 이해하기 위해서 여러 노드들이 마치 chain 처럼 일렬로 나열된 구조를 아래 그림처럼 간단히 표현해보았다.
[그림] Node와 두 가지 연결리스트(SLL, DLL)의 개념과 차이점을 간단히 표현한 도식
또한, 아래 표와 같이 Node, SLL, DLL의 특징들을 비교하여 정리해보자.
| 구분 | Node | SLL | DLL |
| 개념 | 데이터(정보요소)와 링크(주소)로 구성된 기본 구조 | 각 노드가 데이터와 다음(next) 노드의 주소를 저장하는 구조 | 각 노드가 이전(prev)과 다음(next) 노드의 주소를 모두 저장하는 구조 |
| 구성 | 데이터 + 연결 정보(link 주소) (여러 노드가 서로 연결되어 하나의 Linked List를 형성한다.) |
노드들의 한쪽 방향 chain 식 연결 > 단일 방향(한쪽 방향)으로 진행하는 것 |
노드들의 양방향 chain 식 연결 > 양쪽 방향으로 진행 or 역행하는 것 |
| 연결 | 각 노드에 있는 다른 노드의 link 주소를 통해 연결시킬 수 있다. | 처음 노드(Head) 부터 시작하는 단일방향으로 순차적 탐색 (next 주소만 연결) | 처음 노드(Head), 또는 마지막 노드(Tail) 부터 시작하는 양방향으로 탐색 (next 주소끼리 연결, prev 주소끼리 연결) |
| 변화 | 노드는 서로 연결된 노드들의 사이에 삽입되거나, 제거될 수 있다. | 노드 사이의 next 주소 연결이 끊어졌을 때, 각 노드에 prev주소 정보가 없으로 Head부터 다시 시작해야함. (비효율적) | 각 노드마다 prev주소와 next주소를 모두 가지고 있기 때문에, 주소 연결이 끊어졌어도 다시 연결시킬 수 있음. (효율적) |
| 메모리 사용 | 최소치. 데이터, 링크 정보(pointer) 저장. |
적음. 단일방향 배열로써, 노드들이 메모리에 연속적으로 저장되지 않아서 메모리 공간을 보다 유연하게 사용 가능. |
많음. 양방향 배열로써, 각 노드가 이전(prev) 노드에 대한 pointer를 추가로 저장하므로, SLL에 비해서 더 많은 메모리를 사용. |
| 주 사용 예시 | - | 스택(Stack), 큐(Queue) | 양방향 탐색이 필요한 구조 (Undo 등) |
그러면...
위 Node, SLL, DLL의 개념과 차이점으로부터 파이썬으로 간단한 예로 구현해보자.
우선, Chain 식 배열(Linked List)에서 node는 아래와 같이 표현할 수 있다.
class Node:
def __init__(self, data):
self.data = data # 노드가 저장할 데이터
self.next = None # 다음 노드를 가리킴 (없으면 None)
==========================
SLL에 잘 부합하는 경우로, '채팅 메시지 관리'가 있다. 한번 출력되거나 특히 오래된 메시지는 수정이 거의 이루어지지 않으며, 채팅이 순차적으로 진행되기 때문에 next link 만으로도 표현할 수 있다.
# =============================================
# [Linked List]
# [연결 리스트] -> 예제) 채팅 메시지 관리
# 각 메시지가 순서대로 연결된 구조 (한 방향)
# =============================================
# 한 개의 채팅 메시지를 저장하는 '노드(node)' 클래스
class ChatNode:
def __init__(self, message):
self.message = message # 실제 채팅 내용
self.next = None # 다음 메시지를 가리키는 화살표 (처음엔 없음)
# 채팅방(연결 리스트) 클래스
class ChatLinkedList:
def __init__(self):
self.head = None # 첫 번째 메시지(노드)의 시작점
def add_message(self, message):
# 새로운 채팅 메시지를 맨 뒤에 추가
new_node = ChatNode(message)
# 아직 메시지가 없다면, 새 노드가 첫 번째 메시지(head)
if not self.head:
self.head = new_node
return
# 메시지가 이미 있다면, 마지막 노드까지 이동
cur = self.head # current
while cur.next:
cur = cur.next
# 마지막 노드의 next가 새 메시지를 가리키도록 연결
cur.next = new_node
def show_chat(self):
# 전체 채팅 내역 출력
cur = self.head
print(">> 채팅 내역:")
if not cur:
print("(아직 메시지가 없습니다.)")
return
while cur:
print(" ", cur.message)
cur = cur.next
# 실행 예시 =============================================
chat = ChatLinkedList()
n = int(input(">> 채팅 메시지 개수를 입력하세요: "))
for i in range(n):
msg = input(f"{i+1}번째 메시지 입력: ")
chat.add_message(msg)
# 채팅 내역 출력 :
chat.show_chat()
SLL의 출력을 이렇게 해보았다.
채팅 메시지를(ex, 서로 다른 인사말) 총 개수 4개로 한정하였고, 각 메세지는 각 노드마다 data에 A, B, C, D로 구분하여 저장되어 있다. 단일 방향 배열(next link)에 따라서,각 노드들의 출력값(채팅 메세지)이 순차적으로(A → B → C → D)로 출력되게 하였다.
'''
>> 채팅 메시지 개수를 입력하세요: 4
1번째 메시지 입력: A : 안녕하세요.
2번째 메시지 입력: B : 만나서 반갑습니다.
3번째 메시지 입력: C : 처음 뵙겠습니다.
4번째 메시지 입력: D : 앞으로 잘 부탁드립니다.
>> 채팅 내역:
A : 안녕하세요.
B : 만나서 반갑습니다.
C : 처음 뵙겠습니다.
D : 앞으로 잘 부탁드립니다.
'''
==========================
다음으로, DLL에 잘 부합하는 경우로, '음악 재생 목록 관리'가 있다. 현재 재생 중인 음악에서 이전 음악 또는 다음 음악을 선택하는 것이 곧 양방향 선택으로 진행되기 때문에, next link에 prev link를 합하여 표현할 수 있다.
# =============================================
# Double Linked List
# [이중 연결 리스트] - 예제) 음악 재생 목록 관리
# 각 노드가 앞뒤(prev, next)를 모두 알고 있음
# 이전 곡 / 다음 곡 이동이 가능
# =============================================
# 한 곡 정보를 담는 노드 클래스
class SongNode:
def __init__(self, title):
self.title = title # 노래 제목
self.prev = None # 이전 곡
self.next = None # 다음 곡
# 음악 재생 목록 클래스
class Playlist:
def __init__(self):
self.head = None # 첫 곡
self.tail = None # 마지막 곡
self.current = None # 현재 재생 중인 곡
def add_song(self, title):
# 새 노래를 재생 목록 끝에 추가
new_song = SongNode(title)
# 첫 곡이라면 head, tail, current 모두 새 노드로 지정
if not self.head:
self.head = self.tail = self.current = new_song
return
# 마지막 곡 뒤에 새 노래를 연결
self.tail.next = new_song
new_song.prev = self.tail
self.tail = new_song
def next_song(self):
# 다음 곡으로 이동
if self.current and self.current.next:
self.current = self.current.next
else:
print("!!다음 곡이 없습니다.!!")
self.show_current()
def prev_song(self):
# 이전 곡으로 이동
if self.current and self.current.prev:
self.current = self.current.prev
else:
print("!!이전 곡이 없습니다.!!")
self.show_current()
def show_current(self):
# 현재 재생 중인 곡을 보여줌
if self.current:
print(f"현재 재생 중: {self.current.title}")
else:
print("!!재생할 곡이 없습니다.!!")
# 실행 예시 =============================================
playlist = Playlist()
n = int(input("재생 목록에 추가할 곡 개수: "))
for i in range(n):
title = input(f"{i+1}번째 곡 제목 입력: ")
playlist.add_song(title)
print("!!첫 곡 재생 시작!!")
playlist.show_current()
# 간단한 명령으로 이동 가능 :
while True:
cmd = input("\n명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): ")
if cmd == 'n': # next
playlist.next_song()
elif cmd == 'p': # prev
playlist.prev_song()
elif cmd == 'q': # quit
print("!!재생 종료!!")
break
else:
print("올바른 명령어를 입력하세요 (n/p/q)")
DLL의 출력을 순방향(next)과 역방향(prev)을 섞어서 해보았다.
음악 곡을(ex, 서로 다른 음악 제목) 총 개수 4개로 한정하였고, 각 음악 제목은 각 노드마다 data에 A, B, C, D로 구분하여 저장되어 있다.
먼저 첫 곡 A에서(Head node) 시작하여 이전 곡을 선택했을 때(prev link), '!!이전 곡이 없습니다.!!' 이 출력되도록 하였다.
다음, 순방향으로(A → B → C) next link에 따라서 출력되다가, 역방향으로(C → B → A) prev link에 따라서 역행하는 것을 표현하였고, 다시 순방향으로(A → B → C → D) 마지막까지(Tail node) 진행하여 출력되게 하였다. 마무리로 D에서 진행하면(next link) '!!다음 곡이 없습니다.!!' 가 출력되고, 종료(quit)를 하여 '!!재생 종료!!'가 출력되도록 하였다.
'''
재생 목록에 추가할 곡 개수: 4
1번째 곡 제목 입력: A : 여전히 아름다운지
2번째 곡 제목 입력: B : 좋은 사람
3번째 곡 제목 입력: C : 소박했던, 행복했던
4번째 곡 제목 입력: D : 뜨거운 안녕
!!첫 곡 재생 시작!!
현재 재생 중: A : 여전히 아름다운지
# 첫번째(Head) 곡 A 에서 뒤로가기(prev)============
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): p
!!이전 곡이 없습니다.!!
현재 재생 중: A : 여전히 아름다운지
# 곡 A -> B -> C 순서대로 진행하기(next)===========
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): n
현재 재생 중: B : 좋은 사람
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): n
현재 재생 중: C : 소박했던, 행복했던
# 곡 C -> B -> A 역순으로 되돌리기(prev)============
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): p
현재 재생 중: B : 좋은 사람
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): p
현재 재생 중: A : 여전히 아름다운지
# 다시 곡 A -> B -> C -> D 순서대로 진행하기(next)===
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): n
현재 재생 중: B : 좋은 사람
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): n
현재 재생 중: C : 소박했던, 행복했던
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): n
현재 재생 중: D : 뜨거운 안녕
# 마지막 곡 D 다음(next)에는 곡이 없다.==============
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): n
!!다음 곡이 없습니다.!!
현재 재생 중: D : 뜨거운 안녕
명령어 입력 (n: 다음곡, p: 이전곡, q: 종료): q
!!재생 종료!!
'''
이와 같이, Node, SLL, DLL의 개념과 두 가지 연결리스트의 구동 방식에 대한 차이를 파이썬 코드를 활용하여 표현해보았다. 앞으로 코드 실력이 좋아질 수 록, 수 많이 접하게될 데이터를 이와 같이 처리하게 될 것이다. 결국 분석을 위해 데이터를 효율적으로 다루려면, Stack, Queue 뿐만 아니라 SLL, DLL 또한 그 개념과 차이점을 잘 이해하는 것이 매우 중요하다는 사실을 알게 되었다.
필자는 ChartGPT5 에게 파이썬 초보자(or 입문자)의 관점에서 각 코드가 어떤 기능을 하고 왜 그렇게 씌였는지 최대한 이해하고자 적극적으로 활용하고 있다. 체계적이고 분명한 질문을 할 수 록 빠른 코드 습득에 큰 도움이 되고 있다. 다만, Node의 삽입과 제거에 따른 SLL, DLL에 발생할 변화와 노드들 사이의 재연결을 코드에 반영하지 못한 것이 아쉽다. 코드 솔루션을 맹종하지 않으면서, 하루 빨리 부족함을 극복하고자 매진하고자 한다. 좋은 예제들이 많을 것이다. 모방하면서도 자신만의 생각을 꾸준히 메모해두자!!!
즐거운 파이썬~ 즐 파이씽~~
[주의] 내용에 오류가 있을 수 있습니다.
'[Code] Study & Practice' 카테고리의 다른 글
| [Python] 자료 구조4 - 이진 트리(Binary Tree)의 개념, 구조, 규칙 (0) | 2025.11.01 |
|---|---|
| [Python] 자료 구조3 - Hash table의 개념과 index 충돌 해결 방식 비교 (0) | 2025.10.30 |
| [Python] 자료 구조1 - 스택(Stack)과 큐(Queue)의 개념과 차이점 (0) | 2025.10.27 |
| [Python] 메모리(RAM)와 변수(Variable)의 개념. (0) | 2025.10.22 |
| [Python] 2진수의 소수점 연산 불일치와 연산 허용 오차 범위. (0) | 2025.10.21 |