lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

pythonIntroStep4Chapter3Title

pythonIntroStep4Chapter1Title

pythonIntroStep4Chapter2Title

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def print_list(self):
        cur_node = self.head
        while cur_node:
            print(cur_node.data)
            cur_node = cur_node.next

# 단일 연결 리스트 사용 예시
linked_list = SinglyLinkedList()
linked_list.append("A")
linked_list.append("B")
linked_list.append("C")

linked_list.print_list()  # A, B, C 순서대로 출력

# 데이터를 노드로 연결해 구성하는 '연결 리스트(Linked List)'

연결 리스트(Linked List)는 데이터 요소들이 노드(Node)라는 단위로 구성되어 서로 연결되어 있는 구조입니다.

각 노드는 데이터와 포인터(Pointer)로 구성되어 있으며, 포인터는 다음 노드를 가리킵니다.

<br />

## 연결 리스트의 구조와 특성

- `노드(Node)`: 연결 리스트의 각 요소를 노드라고 합니다. 각 노드는 데이터와 하나 또는 두 개의 '포인터'(Pointer)를 포함합니다. 포인터는 다음 노드(때로는 이전 노드)를 가리킵니다.

- `헤드(Head)`: 연결 리스트의 첫 번째 노드를 가리키는 포인터입니다.

- `테일(Tail)`: 연결 리스트의 마지막 노드를 가리키는 포인터입니다.

```python title="파이썬 연결 리스트 구현 예시"
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)
        self.tail = self.head

    def append(self, data):
        node = Node(data)
        self.tail.next = node
        self.tail = node

    def print_all(self):
        node = self.head
        while node is not None:
            print(node.data)
            node = node.next

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.print_all() # 5 12
```

<br />

## 연결 리스트 종류

- `단일 연결 리스트(Singly Linked List)`: 각 노드가 다음 노드만을 가리키는 가장 단순한 형태의 연결 리스트입니다.

- `이중 연결 리스트(Doubly Linked List)`: 각 노드가 이전 노드와 다음 노드를 모두 가리키는 구조로, 양방향 탐색이 가능합니다.

- `원형 연결 리스트(Circular Linked List)`: 마지막 노드가 첫 번째 노드를 가리키는 형태로, 순환 구조를 갖습니다.

<br />

## 연결 리스트와 배열의 비교

- `메모리 할당`: 배열은 고정 크기의 연속적인 메모리 공간을 사용하는 반면, 연결 리스트는 필요에 따라 동적으로 메모리를 할당합니다.

- `삽입/삭제 연산`: 배열에서는 삽입과 삭제가 비효율적일 수 있으나, 연결 리스트에서는 상대적으로 간단하고 빠릅니다.

- `임의 접근`: 배열은 인덱스를 통한 임의 접근이 가능하지만, 연결 리스트는 순차적 접근만 가능합니다.