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

1. 연결 리스트란?

• 연결 리스트: 여러 노드가 모여 만들어진 자료구조.
• 단일 연결 리스트: 연결 방향이 단방향으로 고정된 구조. (마치 일방통행 도로처럼)
• 노드: 데이터(data)와 다른 노드의 참조(next)를 포함.

2. 단일 연결 리스트의 구조

• 단일 연결 리스트의 노드는 다음과 같은 구조를 가집니다:
  • data: 저장할 값.
  • next: 다음 노드의 위치를 가리킴.
• 리스트의 끝에서는 next가 null로 설정됩니다.

구조 예시

[data1, next1] -> [data2, next2] -> [data3, null]

3. 단일 연결 리스트의 노드 생성

3.1 새로운 노드 생성

새로운 노드는 다음과 같이 생성할 수 있습니다:

node1 = Node(3)

혹은 데이터를 나중에 추가하는 방식으로 생성할 수도 있습니다:

node1 = Node()
node1.data = 3

3.2 노드 연결

1. 새로운 노드를 생성합니다:

   node2 = Node(5)

2. 기존 노드와 새 노드를 연결합니다:

   node1.next = node2

3.3 연결된 노드의 접근

node1.next는 node2를 가리킵니다. 따라서 다음과 같이 출력할 수 있습니다:

print(node2.data)         # 5
print(node1.next.data)    # 5

3.4 노드 연결 해제

노드 간 연결을 끊으려면 node1.next에 null을 설정합니다:

node1.next = None

4. 시작점과 종료점

4.1 시작점 (Head)

• head: 리스트의 첫 번째 노드를 가리키는 참조.
• 탐색을 시작하려면 반드시 head를 알아야 합니다.

4.2 종료점 (Tail)

• tail: 리스트의 마지막 노드를 가리키는 참조.
• 탐색 중 종료 지점을 쉽게 확인할 수 있습니다.

5. 단일 연결 리스트의 성능

6. 단일 연결 리스트의 특징 요약

1. 삽입/삭제: O(1)로 효율적.
2. 탐색: O(N)으로 리스트 길이에 비례.
3. 방향성: 단방향으로만 이동 가능 (뒤로 돌아갈 수 없음).

단일 연결 리스트는 배열과 비슷하지만, 삽입과 삭제가 더 효율적입니다. 이 자료구조를 이해하면 더 복잡한 연결 리스트 구조(예: 이중 연결 리스트)도 쉽게 학습할 수 있습니다!

단일 연결 리스트: 삽입 / 삭제 / 탐색

1. 개요

• 단일 연결 리스트(Singly Linked List)에서도 배열처럼 삽입, 삭제, 탐색 연산이 필요합니다.
• 연결 리스트는 삽입과 삭제에 최적화된 자료구조로, 동작 방식을 이해하는 것이 중요합니다.

2. 삽입 (Insertion)

2.1 Tail 뒤에 삽입

• tail의 next가 새로운 노드를 가리키게 설정.
• 새로운 노드를 추가한 뒤, tail을 갱신.

코드

def insert_end(num):
    new_node = Node(num)      # Step 1. 노드 만들기
    SLL.tail.next = new_node  # Step 2. Tail의 next에 새 노드 연결
    SLL.tail = new_node       # Step 3. Tail 업데이트

2.2 Head 앞에 삽입

• 새 노드의 next를 기존 head로 연결.
• head를 새 노드로 갱신.

코드

def insert_front(num):
    new_node = Node(num)      # Step 1. 노드 만들기
    new_node.next = SLL.head  # Step 2. 새 노드의 next를 기존 head로 설정
    SLL.head = new_node       # Step 3. Head 업데이트

2.3 Head 바로 뒤에 삽입

• 기존 head의 연결을 유지하며 새로운 노드를 삽입.

과정

1. 새로운 노드를 생성.
2. 새 노드의 next를 head.next로 설정.
3. head.next를 새 노드로 변경.

코드

def insert_after_head(num):
    new_node = Node(num)            # Step 1. 노드 만들기
    new_node.next = SLL.head.next   # Step 2. 새 노드의 next를 기존 head.next로 설정
    SLL.head.next = new_node        # Step 3. Head의 next를 새 노드로 설정

3. 삭제 (Deletion)

3.1 Tail 삭제

• Tail 바로 전 노드의 next를 null로 설정.
• tail을 이전 노드로 이동.

코드

def delete_tail():
    current = SLL.head
    while current.next != SLL.tail:  # Tail 이전 노드 찾기
        current = current.next
    current.next = None              # Tail 이전 노드의 next를 null로 설정
    SLL.tail = current               # Tail 업데이트

3.2 Head 삭제

• head를 head.next로 이동하여 첫 번째 노드를 삭제.

코드

def delete_head():
    SLL.head = SLL.head.next  # Head를 다음 노드로 이동

4. 탐색 (Search)

탐색의 원리

• 연결 리스트에서 탐색은 head에서 시작하여 tail에 도달하기 전까지 next를 따라가며 진행.
• head와 tail을 명확히 관리해야 탐색이 원활하게 진행됨.

코드

def search(value):
    current = SLL.head
    while current is not None:       # Tail에 도달할 때까지 탐색
        if current.data == value:    # 값이 일치하면 반환
            return True
        current = current.next
    return False                     # 값이 없으면 False 반환

5. 정리

• 단일 연결 리스트에서 삽입과 삭제는 연결만 조정하면 되므로 **O(1)**로 효율적.
• 탐색은 head부터 tail까지 순차적으로 진행해야 하므로 **O(N)**의 시간이 소요.
• 삽입/삭제/탐색 연산은 아래와 같은 시간 복잡도를 가집니다:

단일 연결 리스트의 삽입과 삭제는 매우 효율적이지만, 탐색은 리스트 길이에 비례하므로 선형 시간이 소요됩니다.