Today I Learn: Swift에서의 연결 리스트

연결 리스트(Linked List)는 노드(Node)라는 개별 요소들이 연결되어 있는 자료 구조이다 Swift는 기본 라이브러리로 Linked List가 포함되지 않으므로 직접 구현해야 한다

 

1. 연결 리스트(Linked List)의 기본 개념

연결 리스트는 여러 개의 노드로 이루어져 있으며, 각 노드는 데이터와 다음 노드를 가리키는 포인터(참조)를 포함한다

• 단일 연결 리스트(Singly Linked List)
• 각 노드는 데이터와 다음 노드를 가리키는 참조(next)만 포함
• 이중 연결 리스트(Doubly Linked List)
• 각 노드는 데이터, 이전 노드를 가리키는 previous 참조, 다음 노드를 가리키는 next 참조를 포함
• 원형 연결 리스트(Circular Linked List)
• 마지막 노드의 next가 첫 번째 노드를 가리키는 구조

 

2. Swift에서 단일 연결 리스트 구현

2-1. Node 클래스 구현

class Node<T> {
    var value: T
    var next: Node<T>?

    init(value: T, next: Node<T>? = nil) {
        self.value = value
        self.next = next
    }
}

• 데이터 타입이 국한되지 않도록 제네릭<T> 타입으로 선언
• value: 데이터
• next: 다음 노드

→ 단일 연결 리스트에서는 마지막 노드의 next 값은 nil이므로 옵셔널로 선언한다

 

2-2. Linked List 클래스 구현

class LinkedList<T> { }

 

2-3. 첫 번째 노드를 가리킬 head 프로퍼티 추가

class LinkedList<T> {
    private var head: Node<T>?
}

• 연결 리스트는 첫 번째 노드부터 순차적으로 접근해야 한다
• 따라서 연결 리스트는 항상 첫 번째 노드를 가지고 있어야 하며, 그 노드가 바로 head이다

 

2-4. Linked List가 비어있는 지 확인하는 연산 프로퍼티

class LinkedList<T> {
    private var head: Node<T>?

    var isEmpty: Bool {
        return head == nil
    }
}

 

• isEmpty: head가 nil 이면 첫 번째 노드가 없으므로 비어있는 것

 

2-5. 마지막 위치에 노드 삽입

    // 마지막 위치에 삽입
    func append(value: T) {
        let newNode = Node(value: value) // 노드 초기화
        guard let head = head else {
            self.head = newNode
            return
        }

        var current = head
        while let nextNode = current.next {
            current = nextNode
        }
        current.next = newNode
    }

• let newNode = Node(value: value) : 노드 초기화
• guard let head = head else {} : 첫 번째 값(head)가 비어있으면 추가한 노드를 첫 번째 값으로 설정
• while let nextNode = current.next {} : 마지막 노드까지 탐색
• current.next = newNode : 마지막 노드의 다음 노드로 새로 들어오는 노드를 추가

 

2-6. 특정 노드 삭제

   // 특정 값 삭제
    func remove(value: T) {
        guard let head = head else { return }

        if head.value == value {
            self.head = head.next
            return
        }

        var prev: Node<T>? = head
        var current: Node<T>? = head.next

        while let node = current {
            if node.value == value {
                prev?.next = node.next
                return
            }
            prev = node
            current = node.next
        }
    }

• guard let head = head else { return } : 첫 번째 노드가 없으면 빈 리스트이므로 리턴
• if head.value == value { } : 첫 번째 노드가 삭제하려는 노드와 같으면 head를 nil
• 특정 노드 삭제를 위해서 이전 노드의 next를 특정 노드의 next로 넣어줘야 하므로 prev 선언
• while let node = current { } : 모든 노드를 반복하여 해당 노드를 찾음
  • if node.value == value { } : 특정 노드를 찾으면 이전 노드의 next를 특정 노드의 next로 바꿔줌

 

3. 배열(Array)과 연결 리스트(Linked List)의 차이점

 

비교 항목	Array	Linked List
메모리 구조	연속된 메모리 공간에 저장됨	노드들이 임의의 메모리 위치에 저장됨
접근 속도	O(1) (인덱스로 즉시 접근 가능)	O(n) (헤드부터 차례로 탐색해야 함)
삽입/삭제 속도	O(n) (중간 삽입/삭제 시 전체 요소를 이동)	O(1) (앞쪽 추가/삭제) 또는 O(n) (중간/끝 삽입/삭제)
메모리 사용량	요소만 저장 (고정된 크기의 메모리)	데이터 + 포인터(참조) 저장 (추가적인 메모리 필요)
데이터 크기 변경	크기 변경 시 새로운 메모리 할당이 필요함	동적으로 크기 조정 가능

 

4. 배열(Array)과 연결 리스트(Linked List)의 선택 기준

• 빠른 검색이 필요하면? → Array가 적합(인덱스로 O(1) 접근 가능)
• 자주 삽입 / 삭제 해야 한다면? → Linked List가 적합 (중간 삽입 / 삭제가 O(1) 또는 O(n)으로 더 효율적)
• 메모리 효율이 중요한 경우 → Array가 더 적합 (포인터 저장 공간이 필요 없음)
• 데이터 크기가 동적으로 변하는 경우 → Linked List가 더 유리 (동적 크기 조정 가능)