singly linked list란 무엇이며, 언제 사용하나요?

Question

Accepted Answer

**singly linked list(단일 연결 리스트)**는 **노드(node)**들의 사슬로, 각 노드는 값과 **다음** 노드를 가리키는 포인터를 갖습니다. array와 달리 노드들은 연속되어 있지 않으며, 메모리 어디에나 존재할 수 있고 참조로 연결됩니다.

## 구조

```text
head
  |
  v
[10|*]--->[20|*]--->[30|null]
 val next   val next  val next
```

## 예시

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

# head에 삽입 -> O(1)
def push_front(head, val):
    node = Node(val)
    node.next = head     # 새 노드가 기존 head를 가리키도록 함
    return node          # 새 head

# 검색 -> O(n): 사슬을 따라 걸어가야 함
def find(head, target):
    cur = head
    while cur:
        if cur.val == target:
            return cur
        cur = cur.next
    return None
```

## 복잡도

| 연산 | 시간 |
|---|---|
| head에서 insert/delete | O(1) |
| index로 접근 | O(n) |
| 검색 | O(n) |

## 트레이드오프

- **강점:** 앞에서의 삽입/삭제가 O(1); 재할당 없이 커짐; 낭비되는 용량 없음.
- **약점:** 임의 접근 불가; 모든 노드가 포인터 오버헤드를 가짐; 캐시 지역성이 나쁨(메모리가 흩어져 있음).

## 왜 중요한가

linked list는 양 끝에서 자주 추가하거나 제거하고 중간을 거의 인덱싱하지 않을 때 빛을 발합니다. 예를 들어 stack, queue, 인접 리스트의 근간으로 쓰입니다.

여기서의 포인터 조작을 이해하는 것은 tree, graph, 그리고 많은 면접 문제의 기초가 됩니다.