[Swift] 연결 리스트(Linked List)는 지하철. (feat. 설국열차)

연결 리스트는 데이터를 가지고 있는 노드들을 포인터로 선형적으로 연결해 사용하는 자료 구조입니다.

노드에는 데이터를 위한 속성(value)와 다음 노드의 주소(pointer)가 있어야 합니다.

 

무슨 말인지 잘 모르겠다면..

 

이 글의 제목처럼 연결 리스트는 지하철.을 생각하면 쉽습니다!

(설국 열차는 뒤에서 설명드리겠습니다.😎)

 

 

지하철은 여러 객실들이 연결된 형태입니다.

객실에는 승객(데이터)가 타고 있고, 각 객실들을 연결하기 위해서는 연결선(엣지, 링크)가 필요합니다.

이미지 출처: https://blog.hyundai-rotem.co.kr/515

 

다시 한번, 지하철을 머리 속에 떠올리며 연결 리스트 정의에 대해 생각해보시죠.

연결리스트는 데이터를 갖고 있는 노드(= 지하철 객실)들을 포인터(= 지하철 연결선)으로 연결해 사용하는 선형적 자료 구조입니다.

 

연결 리스트에서는 객실을 노드(node)라고 부르고, 객실을 연결하는 연결선을 엣지(edge)또는 링크(link)라고 부른다는 것 빼고는 비슷한 형태의 구조를 띄는 것입니다.

 

이제 조금은 연결 리스트가 머리 속에서 연상이 되시나요 ?! 🤓

---

Singly Liked List는 설국 열차, Doubly Liked List는 지하철.

그렇다면 왜 이번 포스팅에서 '설국열차'라는 용어를 사용하게 되었는지 살펴보겠습니다. 

 

연결 리스트는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List), 

원형 연결 리스트(Circular Linked List)와 같이 다양한 종류가 있습니다.

• 단일 연결 리스트(Singly Linked List): 각 노드의 링크가 다음 노드만을 가리킵니다.
• 이중 연결 리스트(Doubly Linked List): 각 노드의 링크가 앞의 노드와 뒤의 노드를 가리킵니다.
• 원형 리스트(Circularly Liked List): 처음 노드와 마지막 노드를 연결하여 선형 구조가 아닌 원형 구조를 만듭니다.

설국열차는 이중 연결 리스트와 단일 연결 리스트를 비교하기 위한 비유로 사용되었습니다.

 

(+ 영화 '설국열차'를 모르시는 분들을 위해 간략히 설명드리자면, 설국열차는 여러 객실로 이루어진 기차로, 

각 객실을 이용할 수 있는 계급이 존재하며 꼬리 칸에 있는 최하위 계층은 상부 칸으로 갈 수 없는 열차입니다.)

 

 

이중 연결 리스트를 떠올릴 때는 지하철을 연상하면 되고, 단일 연결 리스트는 설국열차를 연상하면 됩니다.

 

설국열차는 높은 계층들이 사용하는 머리 칸에서는 하위 계층이 사는 꼬리 칸으로 갈 수 있지만, 

꼬리 칸에서는 머리 칸으로 갈 수 없습니다. 

 

마찬가지로 단일 연결 리스트도 헤드 노드에서 테일 노드 방향으로만 갈 수 있고 그 반대는 불가능합니다.

(연결 리스트의 첫 노드를 헤드(Head)노드, 마지막 노드를 테일(Tail)노드라고 부릅니다.)

 

 

그러나 반대로 양방향 연결 리스트를 지하철로 비유한 이유는, 

지하철을 이용한 경험이 있는 분이라면 알겠지만, 해당 칸에서는 앞으로도 갈 수 있고 뒤로도 갈 수 있습니다. 

 

마찬가지로 양방향 연결 리스트는 해당 노드의 앞 노드와 뒤 노드로 접근할 수 있습니다.

---

Array와 Liked List 차이

이쯤 되어서 한 가지 궁금증이 생길 수 있습니다. (아니면 그만...😅)

 

배열(Array)과 연결 리스트(Linked List)의 차이는 무엇일까요? 🧐

 

이전에 자료구조에 관한 포스팅에서 다뤘던 내용을 다시 살펴보면, 

스택(Stack)과 큐(Queue)는 배열을 사용하여 데이터를 저장합니다. 

 

배열을 사용하면 데이터가 메모리 상에 연속적으로 저장되기 때문에, 

인덱스를 통해 O(1) 시간에 원하는 데이터에 접근할 수 있습니다. 

 

그러나 배열에서 맨 앞의 데이터를 삭제하는 경우, 

해당 인덱스의 데이터 공간이 비게 되므로 뒤에 위치한 데이터를 모두 한 칸씩 앞으로 이동시켜야 합니다. (오버 헤드)

이로 인해 O(n)의 시간 복잡도를 가지게 됩니다.

 

(그래서 배열을 이용하여 큐(Queue)를 구현할 때 실제로 배열의 데이터를 삭제하는 것이 아니라,

첫 데이터의 인덱스를 계속해서 조절하여 오버헤드를 피했습니다. 이해가 어렵다면 참고 해주세요.)

 

 

반면, 연결 리스트는 각 노드가 다음 노드의 주소(링크, 엣지)를 가지고 있습니다. 

 

이 구조는 메모리 상에 데이터(Node)가 흩어져 있는 구조입니다. 
따라서 배열과 달리 인덱스를 통해 데이터를 탐색할 수 없으며, 노드에 저장된 다른 노드의 주소를 따라가야 합니다. 

 

따라서 맨 앞의 데이터를 삭제해도 오버헤드가 발생하지 않아 O(1)의 시간 복잡도를 가집니다. 

그러나 인덱스를 사용하여 빠르게 데이터에 접근할 수 없기 때문에 데이터를 탐색하는 데 시간이 오래 걸릴 수 있습니다. 각 노드를 순차적으로 따라가야 하므로 시간 복잡도는 O(n)이 됩니다.

 

요약하자면, 

배열은 데이터가 연속적으로 저장되어 있어 인덱스를 통한 빠른 접근이 가능하지만, 

삭제 시에는 오버헤드가 발생하여 시간이 오래 걸릴 수 있습니다. 

 

반면에 연결 리스트는 데이터가 흩어져 있어 인덱스를 활용하지 못하며, 

삭제 시에는 해당 데이터를 갖는 노드만 제거하면 되기 때문에 빠르게 처리할 수 있습니다. 

 

메모리 저장에 관련하여 더 알고 싶다면 아래 글을 참고해주세요.📝

<Linked List>

---

Singly Liked List와 Doubly Liked List 차이

너무 길어질까봐 생략하려고 했는데, 저의 만족도를 높이고 싶어 추가해보겠습니다.😅 

 

양방향 연결 리스트와 단일 연결 리스트의 차이를 간단하게 생각해봅시다.

 

양방향 연결 리스트는 각 노드가 이전 노드의 엣지를 함께 갖고 있기 때문에, 

단일 연결 리스트보다 더 빠른 시간에 탐색을 할 수 있습니다. 

 

예를 들어 100개의 노드가 저장된 연결 리스트인데 

단일 연결 리스트의 경우 99번째 노드를 찾기 위해서는 첫 번째 노드부터 99번의 탐색을 해야하지만, 

양방향의 경우는 뒤에서부터인 100번째 노드부터 탐색을 하여 단 2번만에 99번째 노드를 찾을 수 있게 됩니다.

 

위의 예시만 보면 무조건 양방향 연결 리스트가 더 좋아보이지만, 양방향 연결 리스트는 단점이 있습니다.

각 노드가 앞의 노드의 링크만 저장하는 것이 아닌 이전 노드의 링크도 저장해야 하기 때문에,

그만큼 메모리 소모가 더 크기 때문에 공간 복잡도가 상대적으로 좋지 않습니다.

 

따라서 연결 리스트를 사용해야 하는 상황에서는 문제 상황에 맞게 단일 연결과 양방향 중 더 알맞은 자료구조를 선택할 수 있어야 합니다.

---

Swift로 Doubly Liked List 구현

이제 직접 연결 리스트를 구현해보겠습니다.

양방향 연결 리스트를 원형으로 연결된 원형 리스트로 작성하겠습니다.

 

이때, 기준 노드 역할을 하는 dummy 노드를 사용하여 메서드들을 쉽게 구현하겠습니다. 

(dummy node의 dat는 nil로 지정하고, dummy node가 연결 리스트의 head 노드로 사용합니다.)

 

양방향 연결 리스트를 작성하는 것을 익힌다면, 단일 연결 리스트는 비교적 쉽게 구현할 수 있을 것입니다!

(단일 연결 리스트에서는 헤드 노드를 더미로 사용할 필요 없습니다!)

 

Node 생성  

// Doubly Linked List Node
class DoublyLinkedListNode<T: Equatable>: Equatable {
    static func == (lhs: DoublyLinkedListNode<T>, rhs: DoublyLinkedListNode<T>) -> Bool {
        return lhs === rhs
    }
    
    let data: T?
    var next: DoublyLinkedListNode?
    weak var previous: DoublyLinkedListNode?
    
    init(data: T?) {
        self.data = data
        self.next = self
        self.previous = self
    }
}

 

(나중에 재사용을 위해 제네릭으로 선언해주었지만, 코테 문제에 따라 약간씩 달라지는 것들이 있어서 어떤 식으로 구현하는지만 보면 될 거 같아요!)

 

단일 연결 리스트와는 달리 양방향 연결 리스트 노드는 이전 노드의 링크도 저장해야하기 때문에

next와 previous 프로퍼티를 선언해줍니다.

 

제네릭으로 선언해줬기 때문에 나중에 비교를 위해 Equatable 프로토콜을 채택해줍니다.

비교는 참조하고 있는 인스턴스가 같은지를 확인해주기 위해 '===' 를 사용해줍니다.

<참고>

---

연결 리스트 구조체 생성  

struct DoublyLinkedList<T: Equatable> {
    typealias Node = DoublyLinkedListNode<T>
    
    private var head = Node(data: nil)  // head를 dummy 노드로 생성
    
    public var isEmpty: Bool {
        return head.next?.data == nil
    }
    
    public var first: Node? {
        return head.next
    }
}

 

필요한 메서드들을 구현하기 전, 간단하게 필요한 프로퍼티들을 선언해 보겠습니다.

(코드 구현부가 길어지는 것을 막기 위해 typealias 문법을 사용하였습니다.)

 

연결 리스트가 비어있는지 확인을 위한 isEmpty와 첫 노드를 리턴해주는 first 프로퍼티를 구현해주었습니다.

head 노드의 경우 앞에서 설명했던 것처럼 nil을 같는 더미 노드로 생성을 해주었습니다.

---

⭐️splice 메서드: 잘라낸 후 이동하기 연산 O(1)

코드 작성 시 가장 중요한 구현부입니다.

 

양방향 연결 리스트에서 필요한 메서드의 구현을 쉽게 해주기 위해 splice 연산을 사용해줍니다.

 

splice(a, b, x) 연산은 양방향 연결 리스트에서 노드 a와 노드 b사이에 노드들을 잘라내서 노드 x 뒤에  붙이는 연산을 뜻합니다.

이 연산을 사용하기 위해서는 필수적인 조건 3가지가 있습니다.

• 조건 1: a 노드 다음에 b 노드가 존재합니다. (바로 옆이 아니어도 상관없음)
• 조건 2: a 노드와 b 노드 사이에 head(더미) 노드가 존재하지 않습니다.
• 조건 3: a 노드와 b 노드 사이에 x 노드가 존재하지 않습니다.

func splice(a: Node, b: Node, x: Node) {
    
    guard let aPrevious = a.previous, let bNext = b.next, let xNext = x.next else { return }
    
    // [a..b] 구간을 잘라내기
    aPrevious.next = bNext
    bNext.previous = aPrevious
    
    // [a..b]를 x 다음에 삽입하기
    x.next = a
    a.previous = x
    b.next = xNext
    xNext.previous = b
}

---

moveAfter, moveBefore: splice를 이용하여 이동 함수 정의  O(1)

moveAfter(a: Node, x: Node)는 노드 a를 x 다음으로 이동시키는 메서드이며, splice 메서드를 호출하여 상수 시간이 걸립니다. 

 

마찬가지로, moveBefore(a: Node, x: Node)는 노드 a를 x 이전으로 이동시키는 메서드이며, splice 메서드를 사용하여 상수 시간이 걸립니다.

// moveAfter 메서드
func moveAfter(a: Node, x: Node) { // 노드 a를 x 다음으로 이동
    self.splice(a: a, b: a, x: x)
}

// moveBefore 메서드
func moveBefore(a: Node, x: Node) { // 노드 a를 x 이전으로 이동
    guard let xPrevious = x.previous else { return }
    
    self.splice(a: a, b: a, x: xPrevious)
}

---

insertAfter, insertBefore: splice를 이용하여 삽입 함수 정의  O(1)

insertAfter(data: T, x: Node)는 data 값을 갖는 새 노드를 만들어 노드 x 뒤에 삽입하는 메서드이며, moveAfter 메서드를 사용하여 상수간이 걸립니다. 

 

마찬가지로, insertBefore(data: T, x: Node)는  data 값을 갖는 새 노드를 만들어 노드 x 앞에 삽입하는 메서드이며, moveBefore 메서드를 사용하여 상수시간이 걸립니다.

// insertAfter 메서드
func insertAfter(data: T, x: Node) {
    moveAfter(a: Node(data: data), x: x)
}

// insertBefore 메서드
func insertBefore(data: T, x: Node) {
    moveBefore(a: Node(data: data), x: x)
}

---

append, appendFirst: splice를 이용하여 삽입 함수 정의  O(1)

append(data: T)는 data 값을 갖는 새 노드를 만들어 제일 뒤에 삽입하는 메서드이며, insertBefore 메서드를 사용하여 상수 시간이 걸립니다. 

 

마찬가지로, appendFirst(data: T)는  data 값을 갖는 새 노드를 만들어 제일 앞에 삽입하는 메서드이며, insertAfter 메서드를 사용하여 상수 시간이 걸립니다.

 

두 메서드는 head 노드의 앞, 뒤로 새로운 노드를 추가하는 노드로 헤드 노드를 참조하여 기능을 구현해주면 됩니다.

// append 메서드
func append(data: T) {
    insertBefore(data: data, x: head)
    
    // insertBefore(data: data, x: head)과 같은 기능
    // guard let headPrev = head.previous else { return }
    // let newNode = Node(data: data)
    // self.splice(a: newNode, b: newNode, x: headPrev)
}

// appendFirst 메서드
func appendFirst(data: T) {
    insertAfter(data: data, x: head)
    
    // insertAfter(data: data, x: head)과 같은 기능
    // let newNode = Node(data: data)
    // self.splice(a: newNode, b: newNode, x: head)
}

---

remove:  삭제 함수 O(1)

remove(x: Node)는 x 노드를 삭제하는 메서드이며, x의 이전 및 다음 노드들에 대한 참조를 갱신하므로 상수 시간이 걸립니다. (단, x는 head 노드가 아니어야 합니다.)

// remove 메서드
func remove(x: Node) -> Node? {
    if x == head {
        return nil
    }
    
    x.next?.previous = x.previous
    x.previous?.next = x.next
    return x
}

---

search:  탐색 함수 O(n)

search(data: T)는 x 노드를 탐색하는 메서드이며, 리스트를 순회하여 데이터를 찾아가므로 최악의 경우 리스트의 길이에 비례하는 선형 시간 소요됩니다.

// search 메서드
func search(data: T) -> Node? {
    var node = head.next
    while node != head {
        if node?.data == data  {
            return node
        }
        node = node?.next
    }
    return nil
}

---

printList:  출력 함수 O(n)

printList()는 모든 노드의 데이터를 출력하는 메서드이며, 리스트를 순회하여 각 노드의 데이터를 출력하므로 최악의 경우 리스트의 길이에 비례하는 선형 시간 소요됩니다.

 

이 메서드는 굳이 작성하지 않아도 되며, 잘 구현이 되었는지 확인하는 메서드입니다.

// printList 메서드
func printList() {
    var current = head.next
    
    while let data = current?.data {
        print("\(data) -> ", terminator: "")
        current = current?.next
    }
    print("nil")
}

 

---

전체 코드

// Node 선언
class DoublyLinkedListNode<T: Equatable>: Equatable {
    static func == (lhs: DoublyLinkedListNode<T>, rhs: DoublyLinkedListNode<T>) -> Bool {
        return lhs === rhs
    }
    
    let data: T?
    var next: DoublyLinkedListNode?
    weak var previous: DoublyLinkedListNode?
    
    init(data: T?) {
        self.data = data
        self.next = self
        self.previous = self
    }
}

// 자료 구조 선언
struct DoublyLinkedList<T: Equatable> {
    
    typealias Node = DoublyLinkedListNode<T>
    
    private var head = Node(data: nil)
    public var isEmpty: Bool {
        return head.next?.data == nil
    }
    
    public var first: Node? {
        return head.next
    }
    
    // splice 메서드의 시간 복잡도: O(1)
    func splice(a: Node, b: Node, x: Node) {

        guard let aPrevious = a.previous, let bNext = b.next, let xNext = x.next else { return }

        aPrevious.next = bNext
        bNext.previous = aPrevious
        
        x.next = a
        a.previous = x
        b.next = xNext
        xNext.previous = b
    }
    
    // append 메서드의 시간 복잡도: O(1)
    func append(data: T) {
        insertBefore(data: data, x: head)
    }
    
    // appendFirst 메서드의 시간 복잡도: O(1)
    func appendFirst(data: T) {
        insertAfter(data: data, x: head)
    }
    
    // insertAfter 메서드의 시간 복잡도: O(1)
    func insertAfter(data: T, x: Node) {
        moveAfter(a: Node(data: data), x: x)
    }
    
    // insertBefore 메서드의 시간 복잡도: O(1)
    func insertBefore(data: T, x: Node) {
        moveBefore(a: Node(data: data), x: x)
    }

    // moveAfter 메서드의 시간 복잡도: O(1)
    func moveAfter(a: Node, x: Node) {
        self.splice(a: a, b: a, x: x)
    }
    
    // moveBefore 메서드의 시간 복잡도: O(1)
    func moveBefore(a: Node, x: Node) {
        guard let xPrevious = x.previous else { return }
        
        self.splice(a: a, b: a, x: xPrevious)
    }
    
    // search 메서드의 시간 복잡도: O(n)
    func search(data: T) -> Node? {
        var node = head.next
        while node != head {
            if node?.data == data  {
                return node
            }
            node = node?.next
        }
        return nil
    }
    
    // remove 메서드의 시간 복잡도: O(1)
    func remove(x: Node) -> Node? {
        if x == head {
            return nil
        }
        
        x.next?.previous = x.previous
        x.previous?.next = x.next
        return x
    }
    
    // printList 메서드의 시간 복잡도: O(n)
    func printList() {
        var current = head.next
        while let data = current?.data {
            print("\(data) -> ", terminator: "")
            current = current?.next
        }
        print("nil")
    }
}

---

마무리

생각보다 기록하고자 하는 내용들이 많아져 글이 꽤 길어진 것 같네요. 😅 

그래도 이렇게 모든 내용을 다뤄서 그런지 제 머리 속에도 더 잘 기억되는 것 같습니다. 

(이 글을 읽는 분들도 그랬으면 좋겠습니다!) 

 

모든 자료 구조에 대한 피드를 올리고 싶지만, 

이것저것 하고 싶은 것들이 너무 많아 계속해서 후순위가 되다가 이제서야 연결 리스트에 관해 작성을 해보았습니다. 

앞으로 기록할 자료구조들이 많지만 빠른 시일 내에 다 작성해보겠습니다! 

 

마지막으로 코딩 테스트 문제를 풀면서 알게된 사실인데 

연결 리스트는 텍스트 에디터에서 많이 사용되는 자료구조라고 합니다. 

 

에디터의 커서를 계속해서 저장하고 있다면 연결 리스트의 단점인 탐색 과정이 필요가 없어지고, 

빠른 시간에 자신이 원하는 글자(커서)를 삭제 또는 삽입을 진행할 수 있기 때문입니다. 

 

이상으로 연결 리스트 포스팅을 마치겠습니다!!

 

잘못된 내용이나 궁금하신 점이 있다면 댓글 남겨주세요. 🤓

읽어주셔서 감사합니다.

---

📝 참고 자료

한국외대 신찬수 교수님의 Data Structures with Python 강의

위키 백과: 연결 리스트

https://jeong9216.tistory.com/401

https://opentutorials.org/module/1335/8821