1. 링크드 리스트(Linked List)란
링크드 리스트란 요소들이 비연속적인 메모리공간에 할당된 선형 자료구조이다.
링크드 리스트는 연결 방식에 따라 크게 단일 연결 리스트(Singly Linked List) 와 이중 연결 리스트(Doubly Linked List) 로 나눌 수 있다.
- 단일 연결 리스트 : 다음 노드의 정보만 저장
- 이중 연결 리스트 : 이전 노드와 다음 노드의 정보를 모두 저장
이번에는 먼저 단일 연결 리스트에 대해 알아보자.
단일 연결 리스트는 각 노드가 자신의 다음 노드만 가리키는 구조의 연결 리스트이다.
2. 단일 연결리스트(Singly Linked List)의 구조
단일 연결 리스트는 각 노드(Node)가 데이터를 저장하고, 다음 노드를 가리키는 포인터를 함께 가지는 구조이다.
여기서 노드(Node) 란 리스트의 각 항목을 저장하는 단위라고 볼 수 있다. 하나의 노드는 실제 데이터를 저장하는 부분(Data) 과 다음 노드의 주소값을 저장하는 부분(Next Pointer) 으로 이루어져 있다.
또한 첫 번째 노드는 head node 라고 부르며, 우리는 이 head node부터 시작해서 다음 노드를 따라가며 전체 연결 리스트를 순회할 수 있다.
전체적인 구조는 다음과 같다.
위 그림을 기준으로 보면,
초록색 부분은 실제 데이터 값(Data) 을 의미하고 보라색 부분은 다음 노드의 주소값(포인터) 을 저장하는 부분이다.
예를 들어 첫 번째 노드의 포인터 값인 1000은 다음 노드의 주소를 가리킨다.
따라서 첫 번째 노드에서 다음 노드로 이동할 수 있다. 이와 같은 방식으로 각 노드는 다음 노드의 주소를 저장하며 연결된다. 이 때, 마지막 노드는 더 이상 가리킬 다음 노드가 없기 때문에 None 값을 가진다.
3.링크드 리스트의 동작 원리 정리하기
3.1 데이터 추가
1) head에 추가
head에 노드를 추가할 때는 새로운 노드가 기존 head를 가리키도록 연결한 뒤, head를 새 노드로 변경한다.
즉, 새로운 노드가 리스트의 첫 번째 노드가 되는 방식이다.
2) tail에 추가
tail에 노드를 추가할 때는 마지막 노드까지 순회한 뒤, 마지막 노드가 새 노드를 가리키도록 연결한다.
단일 연결 리스트는 마지막 노드를 바로 알 수 없기 때문에, head부터 시작해서 순차적으로 탐색해야 한다.
3) 특정 위치에(index)에 추가
특정 위치에 노드를 추가할 때는 삽입할 위치의 직전 노드까지 이동한 뒤 연결 구조를 변경한다.
즉, 새 노드가 다음 노드를 가리키도록 연결하고, 이전 노드가 새 노드를 가리키도록 수정한다.
3.2 데이터 삭제
1) head 삭제
head를 삭제할 때는 현재 head의 다음 노드를 새로운 head로 변경한다.
즉, 기존 첫 번째 노드는 리스트에서 제외된다.
2) tail 삭제
tail을 삭제할 때는 마지막 노드의 직전 노드까지 이동한 뒤, next 값을 None으로 변경한다.
3) 특정 value를 가진 노드 삭제
특정 값을 가진 노드를 삭제할 때는 삭제 대상 노드의 이전 노드가 다음 노드를 가리키도록 연결 구조를 변경한다.
3.3 조회
연결 리스트를 조회하면서 각 노드의 value를 특정값과 비교한다
연결 리스트를 조회할 때는 head부터 시작하여 각 노드의 value를 순차적으로 비교한다.
4. 배열(Array) vs 링크드 리스트(Linked List)
4.1 메모리 공간 할당 방식
배열(Array)은 연속된 메모리 공간이 할당된 선형 자료구조이다. 반면, 링크드 리스트는 메모리 공간이 비연속적으로 할당된 선형 자료구조이다.
배열은 데이터가 순서대로 연속된 공간에 저장되지만, 링크드 리스트는 각 데이터가 노드(Node) 단위로 흩어져 저장될 수 있다. 대신 각 노드는 다음 노드의 주소값을 저장하여 연결 구조를 유지한다.
4.2 데이터 접근 속도
배열은 인덱스를 이용해 원하는 데이터에 임의 접근(Random Access) 할 수 있어, 특정 원소에 매우 빠르게 접근할 수 있다. 그래서 데이터의 개수가 아무리 많아도 데이터에 접근하는 속도는 항상 일정하다.
반면, 링크드 리스트는 특정 원소에 바로 접근하는 임의 접근이 불가능하다. 따라서 원하는 데이터를 찾기 위해. 각 노드가 가지고 있는 포인터(pointer)를 따라 앞에서부터 순차적으로 탐색해야 한다. 즉, 특정 원소에 접근하는 속도가 배열보다 느리다는 단점이 있다.
4.3 데이터 추가 및 삭제 방식
배열은 중간에 데이터를 삽입하거나 삭제할 때 기존 데이터들을 이동해야 한다.
따라서 데이터의 이동 횟수가 많아질 수 있다는 단점이 있다.
반면, 링크드 리스트는 데이터를 추가하거나 삭제할 때 연결 구조만 변경하면 되기 때문에 비교적 간단하게 처리할 수 있다.
따라서 중간에 데이터를 자주 추가하거나 삭제해야 하는 상황에서는 링크드 리스트가 유리할 수 있다.
5. 단일 링크드 리스트의 장/단점
5.1 장점
1️⃣ 데이터의 삽입과 삭제가 비교적 간단하다.
배열과 달리 연결 리스트는 데이터를 추가하거나 제거할 때 다음 노드를 가리키는 포인터의 주소만 수정해주면 된다. 그래서 이런 데이터 수정이 자주 일어나는 상황에서 유용하게 사용할 수 있다.
2️⃣ 동적 자료구조
연결리스트는 동적으로 크기가 변하는 자료구조이다.
배열처럼 처음부터 크기를 미리 정해둘 필요가 없고, 실행 중(runtime)에 필요한 만큼 메모리를 할당하거나 해제하면서 크기를 늘리거나 줄일 수 있다. 그래서 데이터 개수가 유동적으로 변하는 상황에서 유용하게 사용할 수 있다.
링크드 리스트는 데이터를 추가하거나 삭제할 때 다른 자료구조보다 더 빠른 편이다.
5.2 단점
1️⃣ 역방향 탐색이 어렵다
단일 연결리스트는 이전 노드를 가리키는 정보가 없기 때문에 뒤로 이동하는 탐색이 불가능하다.
2️⃣ 탐색 속도가 배열보다 느릴 수 있다.
원하는 데이터를 찾기 위해서는 처음(head)부터 노드를 하나씩 순차적으로 따라가야 한다. 그래서 특정 위치의 데이터를 바로 접근할 수 있는 배열에 비해 탐색 속도가 느릴 수 있다.
6. 링크드 리스트의 실제 활용 예시
플레이리스트 관리
단일 연결 리스트는 음악 플레이리스트를 관리하는 기능에 활용될 수 있다.
플레이리스트에서는 각 노래가 하나의 노드(Node) 역할을 하며, 각 노드는 다음에 재생될 노래 정보를 가리키는 방식으로 연결될 수 있다.
작업 관리 시스템
일정 관리 앱이나 To-do 리스트 기능에서 작업 순서를 관리할 때 연결 리스트 구조가 활용될 수 있다.
7. 단일 연결 리스트(Singly Linked List) 구현
# Node 클래스
class Node :
def __init__(self,data=None):
self.data=data
self.next= None # 다음 노드의 주소
class SinglyLinkedList:
def __init__(self):
self.head=None
# 🔵 데이터 추가하기
# ✅ 새로운 노드 가장 앞에 추가하기
def insertAtHead(self,data):
new_node=Node(data)
if self.head is None : # 연결리스트가 비어있으면
self.head=new_node # new_node를 head로 선정한다.
else : # 비어있지 않을 때
new_node.next=self.head
self.head=new_node
# ✅ 새로운 Node 가장 뒤에 추가하기
def insertAtTail(self,data):
new_node=Node(data) # 새로운 노드 생성
if self.head is None : # 만약 head가 비어있으면
self.head = new_node
return
else :
# 전체 리스트순회해보기
current= self.head # head 부터 시작하기 위해 head를 current로 선언
while current.next:
current=current.next
# 마지막 노드에 도착했을 때
current.next = new_node
def insertAtPosition(self,index,value):
new_node=Node(value) # 삽입할 새 노드 생성
if index < 0 :
print("노드를 삽입할 수 없습니다")
return
elif index==0: # index가 0이면 head에 삽입
self.insertAtHead(value)
return
else:
current=self.head
# 삽입할 위치의 직전 노드까지 이동
for _ in range(index - 1):
# 이동 중 current가 None이면 index가 범위를 벗어난 것
if current is None:
print("노드를 삽입할 수 없습니다.")
return
current = current.next
# index가 리스트 길이보다 큰 경우
if current is None:
print("노드를 삽입할 수 없습니다.")
return
# 새 노드가 기존 다음 노드를 가리키도록 연결
new_node.next = current.next
# 현재 노드가 새 노드를 가리키도록 연결
current.next = new_node
## 🟡 데이터 삭제
# ✅ 맨 앞 노드 삭제
def deleteHead(self):
if self.head is None:
return
self.head=self.head.next
# ✅ 맨 뒤 노드 삭제
def deleteTail(self):
if self.head is None: # 빈 리스트
return
if self.head.next is None: # 노드가 1개일 때
self.head = None
return
# 마지막 노드직전까지 순회
current=self.head
while current.next.next:
current=current.next
# 마지막 직전 노드가 None을 가리키도록 변경하여 마지막 노드 삭제
current.next=None
# ✅ 특정 노드값 삭제
def deleteNodeValue(self,value):
# 빈 리스트인지 확인
if self.head is None:
return
# head가 삭제 대상일 때
if self.head.data == value:
self.head = self.head.next
return
current=self.head
while current.next:
if current.next.data == value :
# 삭제할 노드를 건너뛰도록 연결 변경
current.next=current.next.next
return
# 다음 노드로 이동
current=current.next
print("특정 노드값을 가진 노드가 없습니다.")
# ✅ 연결리스트 순회
def traverse(self):
current=self.head
while current :
print(current.data,end='->')
current=current.next
print('None') # 끝에 도달하면 None 출력
# ✅ value값 존재 유무 체크
def search(self,value):
current=self.head
# head부터 시작해서 value와 같은 값을 가진 노드가 있는지 순차 탐색
while current :
if current.data == value :
return f'{value} 존재함'
current=current.next
return f'{value} 존재하지 않음'데이터 추가하기
sl= SinglyLinkedList()
sl.insertAtTail(10)
sl.insertAtTail(20)
sl.insertAtTail(30)
sl.insertAtTail(40)
sl.insertAtHead(-10)
sl.traverse()실행결과
데이터 조회
print('50 존재 유무 :',sl.search(50))
print('20 존재 유무',sl.search(20))
실행결과
데이터 삭제
sl.traverse()
sl.deleteNodeValue(20)
sl.traverse()실행결과
'python' 카테고리의 다른 글
| 자료구조 - 이중 연결 리스트(Doubly Linked List) (0) | 2026.06.03 |
|---|---|
| 자료구조 - 트리 (0) | 2026.06.03 |
| 자료구조 -큐(Queue) (0) | 2026.05.30 |
| 자료구조 - 스택(Stack) (0) | 2026.05.30 |
| 자료구조 - 배열(Array) (0) | 2026.05.29 |