[정글 베이직 18] — 연결 리스트 (Linked List)

📋 문제 소개

문제 설명

단순 연결 리스트(Linked List)를 구현한다. 노드는 값(data)과 다음 노드를 가리키는 포인터(next)를 가진다.

INPUT

연결 리스트에 추가할 값들 (append 메서드 호출)

OUTPUT

연결 리스트의 모든 값 (리스트 형태로 반환)

예제

입력

ll.append(1); ll.append(2); ll.append(3)

출력

[1, 2, 3]

💡 힌트

Node 클래스: data와 next 포인터. LinkedList 클래스: head 포인터. append()로 끝에 추가.

① 문제 이해

항목	내용
문제	단순 연결 리스트를 구현한다 (append, print_list).
구조	Node(data, next) + LinkedList(head)
예제	1→2→3 append 후 [1,2,3] 반환

② 핵심 아이디어

각 노드가 다음 노드를 가리키는 포인터를 갖는다. 배열과 달리 삽입/삭제가 O(1)이지만 인덱스 접근이 O(n)이다.

# 구조
Node: [data | next →]  →  [data | next →]  →  [data | None]
LinkedList: head → 첫 번째 Node

# append
if head is None:
    head = new_node
else:
    current = head
    while current.next is not None:
        current = current.next
    current.next = new_node

③ 코드 분석

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None       # ① 다음 노드 포인터 (초기값 None)

class LinkedList:
    def __init__(self):
        self.head = None       # ② 첫 노드 (빈 리스트 = None)

    def append(self, data):
        new_node = Node(data)
        if self.head is None:  # ③ 빈 리스트
            self.head = new_node
            return
        current = self.head
        while current.next is not None:  # ④ 마지막 노드 탐색
            current = current.next
        current.next = new_node          # ⑤ 마지막에 연결

    def print_list(self):
        values, current = [], self.head
        while current is not None:       # ⑥ None 만날 때까지 순회
            values.append(current.data)
            current = current.next
        return values

번호	코드	의미
①	self.next = None	아무것도 가리키지 않음 = 리스트의 끝
③	is None	빈 리스트 처리 — 이 없으면 head.next 접근 시 AttributeError
④	current.next is not None	next가 None인 노드 = 마지막 노드
⑤	current.next = new_node	마지막 노드의 포인터를 새 노드로 연결

④ 자주 하는 실수

⚠️ == None 대신 is None 사용

None 비교는 == None 보다 is None 이 파이썬 스타일이다. is 는 객체 동일성(identity)을 비교한다.

⚠️ append가 O(n)인 이유

끝에 추가하려면 head부터 끝까지 순회해야 한다. tail 포인터를 따로 유지하면 O(1)로 개선 가능하다.

💡 배열(리스트) vs 연결 리스트: 배열은 인덱스 접근 O(1), 중간 삽입/삭제 O(n). 연결 리스트는 인덱스 접근 O(n), 포인터만 알면 삽입/삭제 O(1). 무엇이 더 빈번한 연산인지에 따라 선택한다.

⑤ 시간복잡도

연산	시간	이유
append	O(n)	마지막 노드까지 순회 필요
print_list	O(n)	전체 노드 순회
인덱스 접근	O(n)	head부터 순서대로 찾아야 함

⑥ 핵심 정리

• Node는 data와 next 두 개만 갖는다. 단순하다.
• None 비교: is None, is not None — == None 쓰지 말자.
• append 최적화: tail 포인터 추가 → O(n) → O(1).
• 연결 리스트는 다음 자료구조(트리, 그래프)의 기반이다. 포인터 개념을 확실히 잡아두자.