[2025-2주차] 연결리스트 복습

팔랑이·2025년 11월 2일

자료구조/알고리즘

목록 보기

14/19

오늘의 주제

연결 리스트 (Linked List)

단일/이중 연결 리스트 구현

노드 삽입/삭제 연산

순환 연결 리스트(Circular Linked List)

리스트 뒤집기 문제(Reverse Linked List)

연결 리스트란?

연결 리스트는 배열과 달리 메모리 공간이 연속적이지 않아도 되는 자료구조이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어진다.
배열과의 핵심 차이점은 다음과 같다.

중간 삽입/삭제가 O(1)로 가능
임의 접근(Random Access)이 불가능하여 탐색은 O(n)
메모리 재할당 없이 유연한 확장이 가능

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

가장 기본적인 형태로, 각 노드는 다음 노드를 가리키는 포인터 하나만 가진다.

head 포인터에서 시작해 순차적으로만 이동 가능
삽입·삭제는 특정 노드를 알고 있을 때 O(1)
탐색은 O(n)

swift가 더 잘 읽히는 지경에 이르러서,,, 읽는건 swift로ㅎ

// MARK: - Node
class Node<T> {
    var value: T
    var next: Node?
    
    init(value: T, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

// MARK: - LinkedList
class LinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?
    private(set) var count: Int = 0
    
    var isEmpty: Bool {
        return head == nil
    }
    
    var first: T? {
        return head?.value
    }
    
    var last: T? {
        return tail?.value
    }
    
    // MARK: - Append (맨 뒤에 추가)
    func append(_ value: T) {
        let newNode = Node(value: value)
        
        if let tail = tail {
            tail.next = newNode
        } else {
            head = newNode
        }
        
        tail = newNode
        count += 1
    }
    
    // MARK: - Insert (특정 인덱스에 삽입)
    func insert(_ value: T, at index: Int) {
        guard index >= 0 && index <= count else {
            print("Index out of bounds")
            return
        }
        
        // 맨 앞에 삽입
        if index == 0 {
            let newNode = Node(value: value, next: head)
            head = newNode
            if tail == nil {
                tail = head
            }
            count += 1
            return
        }
        
        // 중간/맨 뒤에 삽입
        var current = head
        for _ in 0..<index - 1 {
            current = current?.next
        }
        
        let newNode = Node(value: value, next: current?.next)
        current?.next = newNode
        
        if newNode.next == nil {
            tail = newNode
        }
        
        count += 1
    }
    
    // MARK: - Remove (특정 인덱스 삭제)
    @discardableResult
    func remove(at index: Int) -> T? {
        guard index >= 0 && index < count else {
            print("Index out of bounds")
            return nil
        }
        
        // 맨 앞 삭제
        if index == 0 {
            let value = head?.value
            head = head?.next
            if head == nil {
                tail = nil
            }
            count -= 1
            return value
        }
        
        // 중간/맨 뒤 삭제
        var current = head
        for _ in 0..<index - 1 {
            current = current?.next
        }
        
        let value = current?.next?.value
        current?.next = current?.next?.next
        
        if current?.next == nil {
            tail = current
        }
        
        count -= 1
        return value
    }
    
    // MARK: - RemoveAll (전체 삭제)
    func removeAll() {
        head = nil
        tail = nil
        count = 0
    }
    
    // MARK: - Node at index (특정 인덱스의 노드 가져오기)
    func node(at index: Int) -> Node<T>? {
        guard index >= 0 && index < count else {
            return nil
        }
        
        var current = head
        for _ in 0..<index {
            current = current?.next
        }
        return current
    }
    
    // MARK: - Value at index (특정 인덱스의 값 가져오기)
    func value(at index: Int) -> T? {
        return node(at: index)?.value
    }
}

노드의 위치는 리스트의 상태가 아니라 “사용 상태”이기 때문에 클래스 안에 넣지 않는다고 한다. 따라서 전통적인 연결 리스트에서는 move_next() 같은 메서드도 없고, 밖에서 관리한다고 함.

@discardableResult
: 일반적으로 반환값이 있는 메서드를 호출할 때, 반환값을 사용하지 않으면 오류를 내는데, 이 attribute를 사용하면 반환값 사용하지 않아도 오류를 내지 않음!

2. 이중 연결 리스트(Doubly Linked List)

각 노드가 prev와 next 포인터를 모두 가지는 구조다.
양방향 순회가 가능해져 구현해야 하는 기능은 늘어나지만, 조작이 훨씬 유연해진다.

앞/뒤 방향 모두 이동 가능
삭제 시 이전 노드를 찾을 필요가 없다
메모리 사용량은 단일보다 조금 더 큼

Python의 collections.deque가 내부적으로 이중 연결 리스트 기반이다.

왜 Linked List에서 head와 tail을 따로 관리할까?
연결 리스트에서는 노드들이 메모리상에 흩어져 있기 때문에, 리스트의 시작점과 끝점을 명확히 알고 있어야 효율적인 조작이 가능하다.
head
리스트의 입구 역할으로, 연결 리스트는 임의 접근(random access)이 불가능하기 때문에 head가 없으면 리스트 자체에 접근할 수 없다.
모든 순회는 head에서 시작한다.
tail
리스트의 출구 역할으로, tail을 관리하지 않으면 맨 끝 노드를 찾기 위해 매번 head부터 끝까지 O(n)으로 순회해야 한다.
tail 포인터를 따로 두면 뒤쪽 삽입·삭제를 O(1) 로 처리할 수 있어 성능이 크게 좋아진다.