이중 연결 리스트 with Javascript

연결 리스트(Linkd List)를 확장하여 양방향으로 링크가 구성되는 이중 연결 리스트를 만들 수 있다. 단일 연결 리스트의 노드가 next 포인터만을 가졌다면 이중 연결 리스트의 노드는 prev와 next 두 개의 포인터를 갖는다.

 

 

Doubly Linked List

 

class LinkedListNode{
    constructor(data){
        this.data = data
        this.prev = null
        this.next = null
    } 
}

그리고 DoublyLinkedList 클래스 자체도 head와 더불어 tail을 추가 멤버로 가진다.

class DoublyLinkedList{
    constructor(){
        this.head = null
        this.tail = null
        this.size = 0
    }

    isEmpty(){
        return this.size == 0
    }
}

삽입

addFront(value){
    //if list is empty
    if(this.isEmpty()){
        this.head = new LinkedListNode(value)
        this.tail = this.head
    }
    else{
        let tmp = new LinkedListNode(value)
        tmp.next = this.head
        this.head.prev = tmp
        this.head = tmp
    }
    this.size++
}

addBack(value){
    //if list is empty
    if(this.isEmpty()){
        this.tail = new LinkedListNode(value)
        this.head = this.tail
    }
    else{
        let tmp = new LinkedListNode(value)
        tmp.prev = this.tail
        this.tail.next = tmp
        this.tail = tmp
    }
    this.size++
}

이중 연결 리스트에서 요소의 삽입은 양방향으로 가능하다. head를 갱신하는 addFront() 방식과 tail을 갱신하는 addBack() 모두 사용할 수 있으므로 적재적소에 활용할 수 있다는 장점이 있다. 빈 리스트에 최초 삽입할 경우에는 head와 tail 모두 새로운 노드로 갱신해준다. head를 갱신할 때는 기존 헤드를 새 노드의 next로 삼고, 기존 헤드의 prev 포인터를 새 노드로 삼는다. 반대로 테일을 갱신하다면 기존 테일을 새 노드의 prev로 삼고, 기존 테일의 next를 새 노드로 삼아준다.

삭제

removeHead(){
    if(this.isEmpty()) return null

    let data = this.head.data

    //if head(=tail) is target
    if(this.head == this.tail){
        this.head = null
        this.tail = null
    }
    else{
        this.head = this.head.next
        this.head.prev = null
    }
    this.size--
    return data
}

removeTail(){
    if(this.isEmpty()) return null

    let data = this.tail.data

    //if head(=tail) is target
    if(this.head == this.tail){
        this.head = null
        this.tail = null
    }
    else{
        this.tail = this.tail.prev
        this.tail.next = null
    }
    this.size--
    return data
}

removeByValue(value){
    let current = this.head //Using tail instead of head also works.

    //if head is target
    if(current.data == value){
        this.head = current.next
        this.size--
    }
    else{
        let prev = current
        while(current.next){
            if(current.data == value){
                prev.next = current.next
                current = current.next
                break
            }
            prev = current
            current = current.next
        }

        if(current.data == value)
            prev.next = null
        this.size--
    }
}

삭제 역시 head를 없애거나, tail을 없애거나 양방향 접근이 가능하다. 단일 연결 리스트에서처럼 순차 탐색에 의해 원하는 값을 제거할 수도 있는데, 이 역시 head로부터 next 방향으로 탐색하든 tail로부터 prev 방향으로 탐색하든 무방하다. removeByValue() 메소드의 동작원리는 연결 리스트(Linkd List)를 참고하자.

검색

findStartingHead(value){
    let current = this.head
    while(current.next){
        if(current.data == value) return true
        current = current.next
    }
    return false
}

findStartingTail(value){
    let current = this.tail
    while(current.prev){
        if(current.data == value) return true
        current = current.prev
    }
    return false
}

마찬가지로 양방향이다! 로직 자체는 단일 연결리스트에서의 검색과 완전히 동일하다. 다만 양방향 검색은 생각보다 더 큰 의미를 갖는데, 이중 연결 리스트에서는 단 하나의 노드로부터 전체 리스트에 대한 완전 탐색이 진행될 수 있다는 점이다. 단일 연결 리스트에서는 단방향으로만(next 방향으로만) 탐색이 가능하므로 주어진 노드 앞쪽(prev 방향) 정보는 알 길이 없었다. 즉 head에 전적으로 의존할 수 밖에 없는 구조였다. 반면 이중 연결 리스트는 그 어떤 노드가 주어지더라도 양방향 탐색을 통해 완전 탐색을 해낼 수 있다.

 

전체 소스(테스트 코드)

class LinkedListNode{
    constructor(data){
        this.data = data
        this.prev = null
        this.next = null
    } 
}

class DoublyLinkedList{
    constructor(){
        this.head = null
        this.tail = null
        this.size = 0
    }

    isEmpty(){
        return this.size == 0
    }

    addFront(value){
        //if list is empty
        if(this.isEmpty()){
            this.head = new LinkedListNode(value)
            this.tail = this.head
        }
        else{
            let tmp = new LinkedListNode(value)
            tmp.next = this.head
            this.head.prev = tmp
            this.head = tmp
        }
        this.size++
    }

    addBack(value){
        //if list is empty
        if(this.isEmpty()){
            this.tail = new LinkedListNode(value)
            this.head = this.tail
        }
        else{
            let tmp = new LinkedListNode(value)
            tmp.prev = this.tail
            this.tail.next = tmp
            this.tail = tmp
        }
        this.size++
    }

    removeHead(){
        if(this.isEmpty()) return null

        let data = this.head.data

        //if head(=tail) is target
        if(this.head == this.tail){
            this.head = null
            this.tail = null
        }
        else{
            this.head = this.head.next
            this.head.prev = null
        }
        this.size--
        return data
    }

    removeTail(){
        if(this.isEmpty()) return null

        let data = this.tail.data

        //if head(=tail) is target
        if(this.head == this.tail){
            this.head = null
            this.tail = null
        }
        else{
            this.tail = this.tail.prev
            this.tail.next = null
        }
        this.size--
        return data
    }
    
    removeByValue(value){
        let current = this.head //Using tail instead of head also works.

        //if head is target
        if(current.data == value){
            this.head = current.next
            this.size--
        }
        else{
            let prev = current
            while(current.next){
                if(current.data == value){
                    prev.next = current.next
                    current = current.next
                    break
                }
                prev = current
                current = current.next
            }

            if(current.data == value)
                prev.next = null
            this.size--
        }
    }

    findStartingHead(value){
        let current = this.head
        while(current.next){
            if(current.data == value) return true
            current = current.next
        }
        return false
    }

    findStartingTail(value){
        let current = this.tail
        while(current.prev){
            if(current.data == value) return true
            current = current.prev
        }
        return false
    }
    print(){
        let result = ""
        let current = this.head
        while(current.next){
            result += `${current.data} -> `
            current = current.next
        }
        result += current.data
        console.log(result)
    }
}

(function test(){
    let ll = new DoublyLinkedList()
    for(let i =1; i<=5; i++) ll.addFront(i)
    ll.print() //5->4->3->2->1
    ll.removeHead() 
    ll.print() //4->3->2->1
    ll.removeTail()
    ll.print() //4->3->2
    ll.removeByValue(3) 
    ll.print() //4->2
    ll.addBack(1)
    ll.print() //4->2->1
})()

 

테스트 결과

 

---

정리

기본적으로 이중 연결리스트는 단일 연결리스트에 비해 포인터 역할의 변수 하나를 더 사용할 뿐이다. 따라서 공간복잡도 면에서 다소 손해를 보겠지만 시간복잡도는 단일 리스트와 다를 바가 없다. 메모리를 더 많이 사용한다는 오버헤드가 있지만 양방향 탐색이 가져다주는 이점이 더 크다고 볼 수 있다. 따라서 대부분의 Linked List는 Doubly Linked List로 구현된다고 한다.

시간복잡도	삽입	값에 의한 삭제	헤드/테일 삭제	검색
Doubly Linked List	O(1)	O(n)	O(1)	O(n)