Algorithm Guidecomplexity: 삽입 O(1) · 탐색 O(n)

연결 리스트 (Linked List)

각 노드가 값과 다음 노드를 가리키는 포인터로 이어진 구조입니다. 연속된 메모리가 필요 없어 삽입·삭제가 O(1)이지만, 임의 접근은 O(n)으로 순차 탐색해야 합니다.

01연결 리스트 (Linked List)

알고리즘 작동 원리 탐색

연결 리스트 시작. head는 아직 아무것도 가리키지 않습니다(빈 리스트).

push_front(10) · 새 노드 10을 만들고 head가 이를 가리키게 합니다.

push_front(24) · 새 노드 24의 next를 기존 head(10)로 잇고, head를 24로 옮깁니다.

push_front(37) · 같은 방식으로 37을 맨 앞에 매답니다. 포인터만 바꾸면 끝 — O(1).

find(24) · head부터 따라갑니다. 첫 노드 37은 24가 아니므로 next로 이동합니다.

다음 노드 24가 찾는 값과 일치합니다 — 반환합니다.

앞에 삽입은 포인터만 바꿔 O(1)이지만, 특정 값 탐색은 head부터 순서대로 O(n)입니다.

head→∅ null

Live Python

1class Node:

2 def __init__(self, value):

3 self.value = value

4 self.next = None

6class LinkedList:

7 def __init__(self):

8 self.head = None

9 def push_front(self, value):

10 node = Node(value)

11 node.next = self.head

12 self.head = node

13 def find(self, value):

14 cur = self.head

15 while cur:

16 if cur.value == value:

17 return cur

18 cur = cur.next

19 return None

1 / 7

02 쉽게 이해하기

For Everyone

🔑핵심 동작

값과 함께 다음 자리의 주소를 들고 있습니다. 자리가 이어져 있지 않아도 되는 대신, n번째를 보려면 앞에서부터 따라가야 합니다.

💡쉽게 말하면

데이터마다 '다음을 가리키는 화살표'를 들고 연결됩니다.

화살표만 고치면 중간 삽입·삭제가 간단해요(임의 접근은 느림).

📍어디에 쓰나

–음악 재생목록
–사진 슬라이드
–메모리를 띄엄띄엄 써야 할 때

03 파이썬 구현 코드

연결 리스트 (Linked List)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

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

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

    def push_front(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node

    def find(self, value):
        cur = self.head
        while cur:
            if cur.value == value:
                return cur
            cur = cur.next
        return None