Doubly Linked List

 

더블리 링크드 리스트

 

class Node<T>: Equatable {
    
    var value: T
    var next: Node<T>?
    var prev: Node<T>?
    
    init(_ value: T, prev: Node<T>? = nil, next: Node<T>? = nil) {
        self.value = value
        self.prev = prev
        self.next = next
    }
    
    static func ==(lhs: Node, rhs: Node) -> Bool {
        return lhs.next == rhs.next
    }
}

class DoublyLinkedList<T> {
    
    var head: Node<T>? = nil
    var tail: Node<T>? = nil
    
    var isEmpty: Bool {
        head == nil
    }
    
    var count: Int {
        var currentNode = head
        var count = 0
        
        while currentNode != nil {
            count += 1
            currentNode = currentNode?.next
        }
        
        return count
    }
    
    init() {
        head = nil
        tail = head
    }
    
    subscript(index: Int) -> Node<T>? {
        node(at: index)
    }
    
    func removeAll() {
        head = nil
        tail = nil
    }
    
    func node(at index: Int) -> Node<T>? {
        
        if isEmpty { return nil }
        
        if index >= 0 {
            var currentNode = head
            var currentIndex = 0
            while currentNode != nil && currentIndex < index {
                currentNode = currentNode?.next
                currentIndex += 1
            }
            
            return currentNode
        }
        
        return nil
    }
    
    func push(_ value: T) {
        
        if isEmpty {
            head = Node(value)
            tail = head
        } else {
            let newNode = Node(value, next: head)
            head?.prev = newNode
            head = newNode
        }
    }
    
    func append(_ value: T) {
        
        let newNode = Node(value)
        
        if let tail = tail {
            newNode.prev = tail
            tail.next = newNode
        } else {
            head = newNode
        }
        
        tail = newNode
    }
    
    func insert(after index: Int, value: T) -> Bool {
        
        if let node = node(at: index) {
            
            if node == tail {
                append(value)
                return true
            }
            
            let newNode = Node(value, prev: node, next: node.next)
            if let oldNextNode = node.next {
                node.next = newNode
                oldNextNode.prev = newNode
                return true
            }
        }
        
        return false
    }
    
    func removeFirst() -> T? {
        
        defer {
            head = head?.next
            head?.prev = nil
            if isEmpty {
                tail = nil
            }
        }
        
        return head?.value
    }
    
    func removeLast() -> T? {
        guard var tailNode = tail, var headNode = head else { return nil }
        
        defer {
            if tailNode == headNode {
                tail = nil
                head = nil
            } else if let prev = tailNode.prev {
                tail = prev
                tail?.next = nil
            }
        }
        
        return tailNode.value
    }
    
    func remove(at index: Int) -> T? {
        
        if let node = self.node(at: index) {
            
            if node == head {
                return removeFirst()
            }
            
            if node == tail {
                return removeLast()
            }
            
            defer {
                let prev = node.prev
                let next = node.next
                prev?.next = node.next
                next?.prev = node.prev
            }
            
            return node.value
        }
        
        return nil
    }
}