자바스크립트 자료구조 이중 연결 리스트(Doubly Linked List)

연결 리스트의 변형된 형태인 이중 연결 리스트(Doubliy Linked List)는 다음 노드의 포인터만 가지고 있는 단일 연결 리스트와 달리

다음 노드와 이전 노드, 2개의 연결 포인터를 가지고 있다.

이중 연결 리스트에서는 처음에서 끝, 끝에서 처음, 양방향으로 리스트 순회가 가능하다.

어떤 노드의 이전, 이후 노드를 찾아갈 수 있기 때문이다.

---

이중 연결 리스트는 단일 연결리스트와 구현 방법이 비슷하며, 달라진 메서드는 

append, removeAt, insert다.

 

노드(Node)

function Node(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
}

이전 노드를 가리키는 prev 프로퍼티가 새로 생겼다.

 

이중 연결 리스트 만들기

function DoublyLinkedList() {
    this._length = 0;
    this._head = null;
    this._tail = null;
}

_tail 프로퍼티는 꼬리로써, 리스트에서 항상 마지막 데이터를 가리킨다.

 

이중 연결 리스트 끝에 데이터 삽입 append 메서드

DoublyLinkedList.prototype.append = function(data) {
    var node = new Node(data);
    var curr;

    if( this._head == null ) {

        this._head = node;

    } else {
        curr = this._head;

        while( curr.next ) {
            curr = curr.next;
        }

        curr.next = node;
        node.prev = next;
    }

    this._length ++;
};

단일 연결 리스트와 방법은 비슷하다. 차이점은 _tail 프로퍼티가 항상 끝에 삽입된 데이터를 가리킨다는 것이다.

 

이중 연결 리스트에서의 데이터 삭제

데이터 위치를 기준으로 삭제하는 removeAt 메서드

DoublyLinkedList.prototype.removeAt = function(pos) {
    if( pos > -1 && pos < this._length ) {
        var curr = this._head;
        var prev, index = 0;

        if( pos === 0 ) {
            this._head = curr.next;

            if( this._length === 1 ) {
                this._tail = null;
            } else {
                this._head.prev = null;
            }

        } else if( pos === this._length-1 ) {

            curr = this._tail;
            this._tail = curr.prev;
            this._tail.next = null;

        }
        else {

            while( index++ < pos ) {
                prev = curr;
                curr = curr.next;
            }

            prev.next = curr.next;
            curr.next.prev = prev;
            
        }

        this._length --;

        curr.next = null;
        curr.prev = null;

        return curr.data;
    }

    return null;
};

 

임의의 위치에 데이터 삽입 insert 메서드

LinkedList.prototype.insert = function(pos, data) {
    if( pos >= 0 && pos <= this._length ) {
        var node = new Node(data),
            curr = this._head,
            prev,
            index = 0;

        if( pos === 0 ) {

            if( !this._head ) {
                this._head = node;
                this._tail = node;
            } else {
                node.next = curr;
                curr.prev = node;
                head = node;
            }


        } else if ( pos === this._length) {

            curr = this._tail;
            curr.next = node;
            node.prev = curr;
            this._tail = node;

        }else {

            while( index++ < pos ) {
                prev = curr;
                curr = curr.next;
            }

            node.next = curr;
            prev.next = node;
            curr.prev = node;
            node.prev = prev;
        }

        this._length ++;

        return true;
    }

    return false;
};

 

removeAt, insert 메서드에서 단일 연결 리스트와 차이점은 _prev 프로퍼티가 생겼다는 점이다.

또한 첫 번째 위치, 마지막 위치, 중간 위치등 조건이 3가지가 된다.

---

 

by 소년코딩

추천은 글쓴이에게 큰 도움이 됩니다.

악플보다 무서운 무플, 댓글은 블로그 운영에 큰 힘이됩니다.