[Swift] 양방향 Linked List 구현해보기

[Swift] 양방향 Linked List 구현해보기

---

정의

리스트는 head, tail로 구분 되어 있으며 각 노드는 prev, next 포인터를 갖고 있다

 

단일 연결 리스트와 다른 점

이전 노드를 나타내는 포인터(prev)가 추가되었고, 리스트 자체의 tail도 있어 역방향 탐색이 절반정도 좋아짐

 

시간 복잡도

 

구현

 

class Node<T> {
    var data: T
    var prev: Node?
    var next: Node?
    
    init(data: T, prev: Node? = nil, next: Node? = nil) {
        self.data = data
        self.prev = prev
        self.next = next
    }
}

class DoublyLinkedList<T: Equatable> {
    private var head: Node<T>?
    private var tail: Node<T>?
    
    init(head: Node<T>? = nil, tail: Node<T>? = nil) {
        self.head = head
        self.tail = tail
    }
    
    var isEmpty: Bool {
        return head == nil
    }
    
    var first: Node<T>? {
        return head
    }
    
    var last: Node<T>? {
        return tail
    }
    
    public func nodeAtIndex(at index: Int) -> Node<T>? {
        if index >= 0 {
            var node = head
            var currentIndex = index
            
            while node != nil {
                if currentIndex == 0 {
                    return node
                }
                currentIndex -= 1
                node = node?.next
            }
        }
        return nil
    }
    
    public func append(data: T) {
        if head == nil || tail == nil {
            head = Node(data: data, prev: nil, next: nil)
            tail = head
            return
        }
        
        let newNode = Node(data: data)
        tail?.next = newNode
        newNode.prev = tail
        tail = newNode
    }
    
    public func insert(data: T, at index: Int) {
        if head == nil || tail == nil {
            head = Node(data: data)
            tail = head
            return
        }
        
        let newNode = Node(data: data)
        if index == 0 {
            newNode.next = head
            head?.prev = newNode
            head = newNode
            if tail == nil {
                tail = newNode
            }
        } else {
            guard let prev = nodeAtIndex(at: index-1) else { return }
            
            let next = prev.next
            newNode.prev = prev
            newNode.next = next
            prev.next = newNode
            next?.prev = newNode
            
            if next == nil {
                tail = newNode
            }
        }
    }
    
    public func removeFirst() {
        guard let headNode = head else { return }
        if head === tail { //heap 영역 값 비교
            tail = nil
        }
        head = headNode.next
        headNode.prev = nil
        
        headNode.next = nil
    }
    
    public func removeLast() {
        guard let tailNode = tail else { return }
        if head === tail {
            head = nil
        }
        
        tail = tailNode.prev
        tail?.next = nil
        
        tailNode.prev = nil
    }
    
    public func printAll() {
        var node = head
        while true {
            if node?.data != nil {
                print("node.data = \(String(describing: node?.data))")
                node = node?.next
            } else {
                break
            }
        }
    }
}