swift Double-LinkedList 구현

https://en.wikipedia.org/wiki/Doubly_linked_list 

Doubly linked list - Wikipedia

 

위키피디아에서 어떤 메소드를 갖고 있어야 하며, 어떤 프로퍼티가 있는지만 확인하고 코드는 내부적으로 직접 구현한 뒤, 코드를 비교해가며, 고쳐봤다.

class Node<T>{
    var data: T
    var prev: Node<T>?
    var next: Node<T>?
    init(_ data: T){//다른 값들을 잇는 행위는 insert 부분에서 하면 된다.
        self.data = data
    }
}

// 맨 앞,뒤 삽입 , 삭제, 해당 노드 이전 삽입, 해당 노드 이후 삽입
class LinkedList<T>{//T의 자료구조를 주면 Node 생성할 때 넣어주면 된당
    var firstNode: Node<T>?//머리
    var lastNode: Node<T>?//꼬리
    var isEmpty: Bool{//계산 속성
        firstNode != nil || lastNode != nil ? false : true
    }
    func insertAfter(_ node: Node<T>,_ newNode: Node<T>) -> Bool{//제대로 삽입 되었는지 확인용도
        //해당하는 노드 다음으로 삽입을 해야 된다.
        //만약 node가 마지막과 같다면 list가 가리키고 있는 마지막 노드도 다른 것으로 교체해줘야 된다.
        newNode.prev = node
        guard let next = node.next else {
            self.lastNode = newNode
            return true
        }
        newNode.next = next
        next.prev = newNode
        node.next = newNode
        return true
    }
    func insertBefore(_ node: Node<T>,_ newNode: Node<T>) -> Bool{//제대로 삽입 되었는지 확인용도
        newNode.next = node
        guard let prev = node.prev else{
            self.firstNode = newNode
            return true
        }
        prev.next = newNode
        newNode.prev = prev
        node.prev = newNode
        return true
    }
    func insertBeginning(_ newNode: Node<T>) -> Bool{//제대로 삽입 되었는지 확인용도
        guard let firstNode = self.firstNode else{
            self.firstNode = newNode
            self.lastNode = newNode
            return true
        }
        insertBefore(firstNode, newNode)
        return true
    }
    func insertEnd(_ newNode: Node<T>) -> Bool{//제대로 삽입 되었는지 확인용도
        guard let lastNode = self.lastNode else{
            self.firstNode = newNode
            self.lastNode = newNode
            return true
        }
        insertAfter(lastNode, newNode)
        return true
    }
    func remove(_ node: Node<T>) -> Void{
        if let prev = node.prev{//이전이 있다면 중간에 낀 아이
            prev.next = node.next // 내가 가리키고 있는 다음 아이를 주고
        }else{
            node.next?.prev = nil
            self.firstNode = node.next
        }
        if let next = node.next{//내가 가리키고 있는 다음이 있는지
            next.prev = node.prev
        }else{//내가 젤 마지막..?
            node.prev?.next = nil
            self.lastNode = node.prev
        }
    }
}

 

약간 스위프트의 문법 스타일로 최대한 적으려고 노력했다.

 

insertBeginning(Node) 젤 앞으로 넣기
insertEnd(Node) 마지막에 넣기
insertBefore(Node, newNode) //Node의 이전으로 넣기
insertAfter(Node, newNode) //Node 이후로 넣기

remove(Node) //Node 삭제가 있으며

isEmpty는 내가 사용하고 싶어서 끼워 넣었다.

 

삽입 삭제는 무조건 O(1) 이다.

 

스위프트 재밌는 듯, little C언어 너낌~