[Swift] weak를 활용한 Linked List

링크드 리스트

링크드 리스트는 실제 개발에서도 자주 사용되는 자료구조로,

이전에도 포스팅을 작성한 적이 있습니다.

[자료구조] Linked List(링크드 리스트) with Swift

 

오늘은 약한참조 키워드인 weak를 활용해 코드를 최적화한 양방향 링크드 리스트에 대해 포스팅하려고 합니다.

 

LinkedListNode

class LinkedListNode<T> {
    var value: T
    var next: LinkedListNode?
    weak var previous: LinkedListNode?
    
    init(value: T) {
        self.value = value
    }
}

Node 클래스입니다.

struct가 아닌 class로 구현한 이유는 노드 객체가 각자 구분되어야 하기 때문입니다.

class는 AnyClass가 Identifable 프로토콜을 채택하고 있어서 따로 작업을 안 해줘도 객체 구분이 가능합니다.

 

아무튼 여기서 중요한 건,

previous의 참조가 강한 참조가 아닌 약한 참조라는 것입니다.

노드를 연결할 때, 

previous를 weak로 선언함으로서 양방향으로 노드를 연결해도 Reference Count(이하 RC)는 1이 됩니다.

이는 링크드 리스트가

Node1 <-> Node2 <-> Node3

모양으로 연결되어 있을 때,

Node1만 해제시켜도 Node2가 함께 해제되고, 연쇄적으로 Node3도 함께 해제시킬 수 있습니다.

이 원리를 이용한 removeAll 메서드는 아래에서 소개할게요.

 

DoublyLinkedList

기본 프로퍼티

struct DoublyLinkedList<T> {
    typealias Node = LinkedListNode<T>
    
    private var head: Node?
    private var tail: Node?
    var count: Int = 0
    
    var isEmpty: Bool {
        return (head == nil)
    }
    
    var first: Node? {
        return head
    }
    
    var last: Node? {
        return tail
    }

    ...

}

DoublyLinkedList가 가지는 프로퍼티입니다.

head와 tail을 이용해 앞뒤 양방향으로 접근할 수 있습니다.

count, isEmpty, first, last는 프로퍼티 이름 그대로의 역할을 수행합니다.

 

노드 얻기 - node, subscript

func node(at index: Int) -> Node? {
    guard index >= 0, index < count else {
        fatalError("범위 밖의 index")
    }

    if index == 0 {
        return head
    } else if index == count - 1 {
        return tail
    } else {
        var node: Node? = nil

        if index < count / 2 {
            node = head!.next
            for _ in 1..<index {
                node = node!.next
            }
        } else {
            node = tail!.previous
            for _ in (index + 2)..<count {
                node = node!.previous
            }
        }

        return node
    }
}

node 메서드는 index 위치의 노드를 얻는 메서드입니다.

해당 index에 노드가 없을 수도 있으므로 옵셔널 반환 타입을 가집니다.

 

여기서 확인해야할 점은 index 체크인데요.

index가 범위를 벗어난 경우 fatalError를 발생시킵니다.

링크드 리스트를 라이브러리로 개발할 때의 관점으로 코드를 작성한건데요.

 

범위를 벗어나는 index를 얻는 조작은 개발자의 실수이거나 무지로 인한 조작으로, 100% 잘못된 결과를 발생합니다.

이때는 nil을 발생시키는 것보다 실수를 바로잡으라는 의미에서 런타임 에러를 발생시키는 게 나을 수 있습니다.

Swift Foundation의 Array도 범위를 벗어나면 런타임 에러를 발생시키는 것도 같은 이유입니다.

 

subscript(index: Int) -> T? {
    return node(at: index)?.value
}

[ ]를 이용해 노드 원소를 얻을 수 있도록 subscript를 정의해주었습니다.

node의 value를 가져오는 것이므로 node(at:) 메서드를 활용하여 구현합니다.

 

노드 추가 - append, insert

mutating func append(_ value: T) {
    let newNode = Node(value: value)

    if let prevTail = tail {
        //이미 노드가 있던 경우 맨 뒤에 삽입
        prevTail.next = newNode
        newNode.previous = prevTail
        tail = newNode
    } else {
        //노드가 비어있던 경우
        head = newNode
        tail = newNode
    }

    count += 1
}

append 메서드는 노드를 리스트의 맨 뒤에 추가하는 메서드입니다.

 

리스트에 이미 노드가 있으면,

맨 뒤 노드를 가리키는 tail 뒤에 새로운 노드를 추가하고, 새로운 노드를 tail로 만듭니다.

 

노드가 비어 있으면,

head와 tail을 새로운 노드로 만듭니다.

 

마지막으로 노드를 추가했으니 count를 1 증가시킵니다.

 

mutating func insert(_ value: T, at index: Int) -> Bool {
    let newNode = Node(value: value)

    if index == 0 {
        newNode.next = head
        head?.previous = newNode
        head = newNode

        count += 1
    } else if index == count - 1 {
        append(value)
    } else {
        guard let prevNode = node(at: index - 1) else {
            return false
        }
        let nextNode = prevNode.next

        prevNode.next = newNode
        newNode.previous = prevNode

        newNode.next = nextNode
        nextNode?.previous = newNode

        count += 1
    }

    return true
}

insert 메서드는 index 파라미터 위치에 노드를 삽입하는 메서드입니다.

 

insert 메서드는 insert 성공 여부를 나타내는 Bool 타입을 반환합니다.

append와 달리 실패할 가능성이 있기 때문에 이를 표현한 것입니다.

반환값이 없다면 insert에 실패했을 때, 이 메서드를 사용하는 개발자가 아무것도 눈치채지 못할 수 있습니다.

그런 슬픈 경우를 방지하기 위해 반환값을 선언합니다.

 

index가 0인 경우, count - 1인 경우는

각각 맨 앞, 맨 뒤에 노드를 넣는 경우이므로 if문으로 분기해서 처리합니다.

맨 앞에 넣는 경우에는 head를, 맨 뒤에 넣는 경우에는 tail을 새로운 노드로 변경해줘야 합니다.

 

이외의 경우는 리스트 중간에 노드를 삽입하는 경우입니다.

index 위치에 새로운 노드를 넣고, 기존 노드는 뒤로 미는 작업이 필요합니다.

새로운 노드를 기준으로 앞, 뒤 노드를 가져온 뒤에 새로운 노드와 연결해줍니다.

 

노드 추가를 성공했다면 count를 1 증가시키고, true를 반환시키는 작업을 마무리로 insert는 끝이 납니다.

 

노드 삭제 - remove, removeAll

mutating func remove(_ index: Int) -> T? {
    guard let removeNode = node(at: index) else {
        return nil
    }

    return remove(node: removeNode)
}

mutating func remove(node: Node) -> T {
    let nextNode = node.next
    let prevNode = node.previous

    if let prevNode = prevNode {
        prevNode.next = nextNode
    } else {
        head = nextNode
    }

    if nextNode == nil {
        tail = prevNode
    }
    nextNode?.previous = prevNode

    node.next = nil
    node.previous = nil

    return node.value
}

노드 삭제를 담당하는 메서드들입니다.

파라미터를 구분해서 오버로딩 해주었습니다.

 

index를 파라미터로 받는 remove 메서드는 해당 index에 노드가 존재할 때만 remove(node:)를 이용해 삭제합니다.

이때도 메서드를 사용하는 개발자를 위해 삭제된 원소를 반환해줍니다. (Array의 popLast() 처럼요)

 

node를 입력 받아서 해당 노드를 삭제하는 메서드는,

삭제할 노드를 기준으로 앞뒤 노드를 서로 연결 시키면 됩니다.

그리고 자신의 next와 previous를 끊고, 삭제된 node의 value를 반환합니다.

 

head 또는 tail을 삭제하는 특수한 경우에는 head와 tail을 변경해주는 것도 잊지 말아야 합니다.

 

mutating func removeAll() {
    head = nil
    tail = nil
}

드디어 removeAll 메서드입니다.

이 메서드 때문에 포스팅을 쓰기로 결정한건데 순서를 너무 뒤에 배치를 했네요 ㅎㅎ;

 

remove 메서드에 비해 아주 심플합니다.

head와 tail을 nil로 변경하는 것만으로도 연결된 모든 노드 객체를 메모리 누수 없이 해제할 수 있습니다.

왜냐하면 previous가 weak 참조로 선언되었기 때문입니다.

Head -> Node1 -> Node2 -> Node3 .... -> Node8 -> (Node9, Tail)

 

이라고 할 때,

Head를 nil로 변경하면 Node1의 RC는 0으로 변하면서 해제됩니다.

Node1이 해제되면서 연쇄적으로 Node1의 next인 Node2가 해제됩니다.

 

Node1과 Node2는 next와 previous에 의해 양방향으로 연결되어 있지만,

previous는 weak 참조이므로 Node의 RC를 증가시키지 않습니다.

따라서 Node2는 Node1의 next 참조에 의해 RC가 1인 상태였는데,

Node1이 해제가 되니 Node2의 RC가 0이 되고 함께 해제가 되는 것입니다.

 

같은 원리로 Node3부터 Node8까지 모두 해제가 되고 Node9와 Tail만 남게 됩니다.

Node9는 tail 객체가 참조하고 있었기 때문에 유일하게 RC가 2였습니다.

그래서 tail까지 nil로 바꿔줘야 Node9까지 해제가 되서,

결국에는 모든 노드가 해제되게 됩니다.

 

링크드 리스트 출력

extension DoublyLinkedList: CustomStringConvertible {
    var description: String {
        var str = "["
        var cur = head
        
        while let node = cur {
            str += "\(node.value)"
            
            cur = node.next
            if cur != nil {
                str += ", "
            }
        }
        
        return str + "]"
    }
}

CustomStringConvertible 프로토콜을 준수하면 print()의 출력을 커스텀할 수 있습니다.

 

테스트

var doublyLinkedList = DoublyLinkedList<Int>()
print(doublyLinkedList)

doublyLinkedList.append(1)
doublyLinkedList.append(2)
doublyLinkedList.append(3)
print(doublyLinkedList) //[1, 2, 3]

print(doublyLinkedList[0]) //Optional(1)
print(doublyLinkedList[1]) //Optional(2)
print(doublyLinkedList[2]) //Optional(3)
//print(doublyLinkedList[3]) //Fatal error: 범위 밖의 index

doublyLinkedList.remove(1)
print(doublyLinkedList) //[1, 3]

doublyLinkedList.insert(4, at: 1)
print(doublyLinkedList) //[1, 4, 3]

doublyLinkedList.removeAll()
print(doublyLinkedList) //[]

 

마무리

처음 removeAll 코드를 보고 weak 특성을 아주 잘 살린 구현 방법이라고 느꼈습니다.

지금까지는 next와 previous 모두 강한 참조로 두고 리스트를 순회하면서 하나하나 연결을 끊어줬었는데요.

weak 특성을 이용하니 단 두 줄로 removeAll이 구현되었기 때문입니다.

이런 최적화 방법을 떠올릴 수 있는 창의력을 키워야할 거 같습니다 ㅠㅠ

 

감사합니다!

 

전체 코드

https://github.com/jeongju9216/SwiftPractice/blob/main/DoublyLinkedList.playground/Contents.swift

 

참고

https://velog.io/@fenta0917/06.LinkedList

https://github.com/kodecocodes/swift-algorithm-club/tree/master/Linked%20List

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.