[Python] 알고리즘 개념6 - 연결 리스트 (Linked List)

 

🚀 1. 연결 리스트란?

**연결 리스트(Linked List)**는 데이터를 저장하는 노드들이 연결된 형태의 자료구조입니다.
배열과 달리 연속된 메모리 공간이 아니라, 각 데이터(노드)가 다음 데이터(노드)의 위치를 기억하는 방식으로 구성됩니다. 즉, 각 노드는 자신과 연결된 다음 노드를 가리키는 포인터를 포함합니다.
 
💡 연결 리스트의 특징

• 데이터가 연속된 메모리 공간에 위치하지 않아도 됨 → 삽입/삭제가 유리
• 각 노드가 다음 노드를 가리키는 포인터(링크)를 포함
• 중간에 데이터를 추가하거나 삭제하는 것이 빠름(O(1)~O(n))
• 특정 위치의 데이터를 찾는 속도는 느림(O(n))

➡ 연결 리스트는 삽입/삭제가 자주 발생하는 경우에 유용하며, 인덱스를 통해 직접 접근이 필요한 경우에는 배열이 더 적합합니다.

---

 

🚀 2. 배열(Array) vs 연결 리스트(Linked List)

 
비교 항목 배열 (Array) 연결 리스트 (Linked List)

메모리 구조	연속된 메모리	분산된 메모리 (노드끼리 연결)
접근 속도	O(1) (인덱스로 접근 가능)	O(n) (순차 탐색 필요)
삽입/삭제 속도	O(n) (중간 삽입/삭제 시 이동 필요)	O(1) (포인터만 변경)
크기 조정	고정 크기 또는 동적 증가	크기 조정 자유로움

💡 배열은 특정 위치의 데이터를 빠르게 가져올 수 있지만, 중간에 삽입/삭제가 느립니다. 💡 연결 리스트는 삽입/삭제가 쉽지만, 특정 데이터를 찾는 속도가 느립니다.
 
➡ 데이터를 자주 추가/삭제할 경우 연결 리스트가 유리하고, 빠른 조회가 필요하면 배열이 더 적합합니다.

---

 

 

🚀 3. 연결 리스트의 구조

연결 리스트는 일련의 노드(Node)들이 연결된 형태의 자료구조입니다. 각 노드는 데이터를 포함하며, 다음 노드를 가리키는 포인터를 가지고 있습니다.

 

✅ 연결 리스트의 기본 개념

1. 노드(Node): 연결 리스트를 구성하는 기본 단위이며, 데이터를 저장하고 다음 노드를 가리키는 포인터를 포함합니다.
2. 헤드(Head): 연결 리스트의 첫 번째 노드를 가리킵니다.
3. 포인터(Pointer): 각 노드가 다음 노드를 가리키는 참조 값입니다.
4. 마지막 노드(End Node): 마지막 노드의 포인터는 None이며, 리스트의 끝을 나타냅니다.

 
➡ 연결 리스트는 배열과 달리 연속된 메모리 공간을 사용하지 않고, 동적으로 크기를 조절할 수 있는 유연한 구조입니다.

 

✅ 연결 리스트의 구조 이해

연결 리스트의 노드는 다음과 같은 형태로 구성됩니다:

[ 데이터 | 다음 노드 주소 ] → [ 데이터 | 다음 노드 주소 ] → [ 데이터 | None ]

➡ 각 노드는 다음 노드를 가리키며, 마지막 노드의 포인터는 None이 됩니다.
연결 리스트는 노드(Node)들의 모임으로 구성됩니다.
 
📌 노드는 다음과 같은 요소를 가집니다:

1. 데이터(Data): 저장할 값
2. 포인터(Next): 다음 노드를 가리키는 참조

➡ 각 노드는 다음 노드를 가리키며, 마지막 노드의 포인터는 None이 됩니다.

 

✅ 단일 연결 리스트 (Singly Linked List)

단일 연결 리스트는 각 노드가 다음 노드만 가리키는 방식으로 연결됩니다.

class Node:
    def __init__(self, data):
        self.data = data  # 데이터 저장
        self.next = None  # 다음 노드를 가리키는 포인터

class LinkedList:
    def __init__(self):
        self.head = None  # 리스트의 첫 번째 노드

➡ 노드는 next 포인터를 통해 다음 노드를 참조합니다.

---

 

 

🚀 4. 연결 리스트의 주요 연산

연결 리스트는 데이터를 효율적으로 추가하거나 삭제할 수 있도록 설계된 자료구조입니다. 연결 리스트의 연산은 주로 삽입(Insertion), 삭제(Deletion), 탐색(Searching), 업데이트(Updating) 로 나뉩니다.
➡ 삽입과 삭제 연산이 배열보다 빠르지만, 탐색 속도가 상대적으로 느리다는 점을 고려해야 합니다.

 

 

✅ 1) 삽입 (Insertion)

연결 리스트에서 새로운 노드를 삽입하는 위치에 따라 연산이 달라집니다.
1. 처음(head)에 삽입 (O(1)) → 빠르게 삽입 가능

def insert_at_head(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

2. 중간 삽입 (O(n)) → 특정 위치를 찾는 과정이 필요

def insert_after(self, prev_node, data):
    if not prev_node:
        print("이전 노드가 없습니다.")
        return
    new_node = Node(data)
    new_node.next = prev_node.next
    prev_node.next = new_node

3. 끝에 삽입 (O(n)) → 마지막 노드를 찾는 과정이 필요

def append(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node
        return
    last = self.head
    while last.next:
        last = last.next
    last.next = new_node

➡ 처음 삽입은 O(1)로 빠르지만, 중간 및 끝 삽입은 O(n) 시간이 소요될 수 있습니다.

---

 

 

✅ 2) 삭제 (Deletion)

연결 리스트에서 노드를 삭제하는 방법
1. 처음(head) 삭제 (O(1)) → 가장 빠름

def delete_head(self):
    if not self.head:
        return
    self.head = self.head.next

2. 특정 노드 삭제 (O(n)) → 해당 노드를 찾는 과정이 필요

def delete_node(self, key):
    temp = self.head
    if temp and temp.data == key:
        self.head = temp.next
        return
    prev = None
    while temp and temp.data != key:
        prev = temp
        temp = temp.next
    if temp is None:
        return
    prev.next = temp.next

➡ 처음 삭제는 O(1)로 빠르지만, 특정 노드를 찾는 삭제는 O(n) 시간이 걸릴 수 있습니다.

---

 

 

🚀 5. 이중 연결 리스트 (Doubly Linked List)

이중 연결 리스트는 각 노드가 이전 노드(prev)와 다음 노드(next)를 모두 가리키는 방식으로 구성됩니다.
 
📌 이중 연결 리스트의 특징

1. 각 노드는 이전(prev)과 다음(next) 두 개의 포인터를 가짐 → 양방향 탐색 가능
2. 노드 삭제 시 이전 노드를 직접 참조할 수 있어 효율적
3. 단일 연결 리스트보다 메모리 사용량이 증가

➡ 이중 연결 리스트는 단방향 리스트보다 효율적인 탐색이 가능하지만, 추가적인 메모리 공간이 필요합니다.

 

✅ 이중 연결 리스트 구조

[ prev | 데이터 | next ] ⇄ [ prev | 데이터 | next ] ⇄ [ prev | 데이터 | None ]

 
💡 단방향 리스트와의 차이점:

• 단일 연결 리스트: 한 방향으로만 이동 가능 (next만 사용)
• 이중 연결 리스트: 양방향 이동 가능 (prev와 next 사용) → 탐색 및 삭제 연산이 더 빠름

➡ 이중 연결 리스트는 삽입/삭제 연산이 많거나 양방향 탐색이 필요한 경우 유용합니다.
 
이중 연결 리스트는 각 노드가 이전 노드(prev)와 다음 노드(next)를 모두 가리키는 방식으로 구성됩니다.

class DNode:
    def __init__(self, data):
        self.data = data
        self.prev = None  # 이전 노드
        self.next = None  # 다음 노드

 
💡 이중 연결 리스트의 장점

• 이전 노드로 이동 가능 (O(1))
• 양방향 탐색 가능
• 삽입/삭제가 단일 연결 리스트보다 효율적

➡ 하지만, 추가적인 메모리 공간(prev 포인터)이 필요하여 단일 연결 리스트보다 메모리를 더 차지합니다.

---

 

 

✅ 마무리 정리

• **연결 리스트(Linked List)**는 동적으로 크기를 조절할 수 있으며, 삽입/삭제가 빠른 자료구조입니다.
• **단일 연결 리스트(Singly Linked List)**는 한 방향으로 연결되며, **이중 연결 리스트(Doubly Linked List)**는 양방향으로 연결됩니다.
• 배열(Array)과 연결 리스트(Linked List)의 장단점을 비교하여 문제 상황에 맞게 선택하는 것이 중요합니다.