[javascript] 이중연결리스트

자바스크립트 이외에 언어에서 연결리스트가 가지는 이점은 배열처럼 고정된 크기를 가지는게 아니라 동적으로 크기를 조정 할 수 있는 것이 장점이다. 그렇다면 단순연결리스트와 원형연결리스트 보다 이중연결리스트가 가지는 이점은 무엇일까 ? 

 

이중연결리스트란 ? 

 

 

기존에 만들었던 연결리스트들은 모두 한 방향으로 이루어져 있다. 그런데 이중연결리스트는 L link 와 R link를 가지고 있어 해당 노드에서 전, 후 노드에 접근 하는 것이 가능케 된다. 이로인해서 헤드가 마지막에 연결되어있는 노드를  O(1) 의 복잡도를 가지고 찾을 수 있다.

 

 

멤버변수

 

class nodeType{
    constructor(item){
        this.data = item;
        this.lLink = null;
        this.rLink = null;
    }

 

 

이중연결리스트의 메서드

처음 head 에 아무 것도 없을때는 새로운 노드를 head와 연결 시켜 주기만 하면 된다. 

 

또한 insertLastNode와 deleteLastNode에서 큰 변화가 있는데 마지막 노드를 찾기 위해 반복문으로 p 변수를 옮겼던 것이 없어지고 head의 rLink를 통하여 마지막 노드를 빠르게 찾을 수 있다.

 

 insertFirstNode(item){
        let newNode = new nodeType(item);
        if(this.rLink == null || this.lLink == null){
            this.rLink = newNode;
            this.lLink = newNode;
            newNode.rLink = this;
            newNode.lLink = this;
        }else{
            newNode.rLink = this.rLink;
            newNode.lLink = this; 
            this.rLink.lLink = newNode;
            this.rLink = newNode;
        }
    }

    deleteFirstNode(){
        if(this.link == null) return null;
        this.rLink = this.rLink.rLink;
        this.rLink.lLink = this;
    }

    insertLastNode(item){
        let newNode = new nodeType(item);
        if(this.lLink == null){
            this.lLink = newNode;
            newNode.rLink = this;
            newNode.lLink = this;
            this.rLink = newNode;
        }else{
            this.lLink.rLink = newNode;
            newNode.lLink = this.lLink;
            newNode.rLink = this;
            this.lLink = newNode;
        }        
    }

    deleteLastNode(){
        if(this.lLink == null) return null;
        this.lLink = this.lLink.lLink;
        this.lLink.lLink = this; 
    }

    print(){
        let string = `${this.data} | `;
        // for(let p = this.link; p != this; p=p.link){
        // }
        let p = this.rLink;
        while(p != this){
            string += `${p.data} | `;
            p= p.rLink;
        }
        string += p.data;
        console.log(string)
    }

 

 

전체 

 

//linked list

class nodeType{
    constructor(item){
        this.data = item;
        this.lLink = null;
        this.rLink = null;
    }

    insertFirstNode(item){
        let newNode = new nodeType(item);
        if(this.rLink == null || this.lLink == null){
            this.rLink = newNode;
            this.lLink = newNode;
            newNode.rLink = this;
            newNode.lLink = this;
        }else{
            newNode.rLink = this.rLink;
            newNode.lLink = this; 
            this.rLink.lLink = newNode;
            this.rLink = newNode;
        }
    }

    deleteFirstNode(){
        if(this.link == null) return null;
        this.rLink = this.rLink.rLink;
        this.rLink.lLink = this;
    }

    insertLastNode(item){
        let newNode = new nodeType(item);
        if(this.lLink == null){
            this.lLink = newNode;
            newNode.rLink = this;
            newNode.lLink = this;
            this.rLink = newNode;
        }else{
            this.lLink.rLink = newNode;
            newNode.lLink = this.lLink;
            newNode.rLink = this;
            this.lLink = newNode;
        }        
    }

    deleteLastNode(){
        if(this.lLink == null) return null;
        this.lLink = this.lLink.lLink;
        this.lLink.lLink = this; 
    }

    print(){
        let string = `${this.data} | `;
        // for(let p = this.link; p != this; p=p.link){
        // }
        let p = this.rLink;
        while(p != this){
            string += `${p.data} | `;
            p= p.rLink;
        }
        string += p.data;
        console.log(string)
    }
}

let circleList = new nodeType("head");

circleList.insertFirstNode("1"); // head | 1 | head 
circleList.insertFirstNode("2"); // head | 1 | 2 | head 
circleList.insertFirstNode("3"); // head | 1 | 2 | 3  head 
circleList.insertLastNode("4"); // head | 1 | 2 | 3 | 4 head 
circleList.insertLastNode("5"); // head | 1 | 2 | 3 | 4 | 5 | head 
circleList.insertLastNode("6"); // head | 1 | 2 | 3 | 4 | 5 | 6 |head 


circleList.print();

 

 

// 혹시라도 거꾸로 출력하는 print메서드를 만들고 싶으면rLink 를 lLink 로 바꾸면 된다.