[javascript] 원형연결리스트 만들기

지난번 만들어 보았던 단순연결리스트는 마지막 node 가 null을 가리키고 있는 형태를 하고 있는데 오늘 만들어볼 원형 연결리스트는 마지막 노드가 항상 Head 노드를 가리키고 있어 노드의 링크를 타고 다시 처음으로 갈 수 있다는 이점이 있다. 

 

// 아직 원형연결리스트가 단순연결리스트보다 더 좋은 이점을 찾지를 못 찾겠다. 루프를 만들어 내부에 뭐가 있는지 순차적으로 감시하기에는 좋을 듯 하다.  

 

원형연결리스트

원형연결리스트

 

필요한 멤버 변수

 

처음 만들어지는 head는 data로 head가 들어간다. 

constructor(item){
        this.data = item;
        this.link = null;
    }

 

필요한 메서드

insertFirstNode(item) // node를 생성하고 head바로 앞에 넣는다. 

insertLastNode(item) // node를 생성하고 list 마지막에 넣는다.

deleteLastNode() // head전 노드를 삭제한다. 

deleteFirstNode() //head 바로 앞 노드를 삭제한다.

print() // 원형연결리스트를 출력한다. 

 

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

    deleteFirstNode(){
        if(this.link == null) return null;
        const remove = this.link;
        this.link = remove.link;
    }

    insertLastNode(item){
        let newNode = new nodeType(item);
        let p = this;
        if(this.link == null){
            this.link = newNode;
            newNode.link = this;
        }else{
            while(p.link != this){
                p = p.link;
            }
            p.link = newNode;
            newNode.link = this;
        }        
    }

    deleteLastNode(){
        if(this.link == null) return null;

        let p = this;
        while(p.link.link != this){
            p = p.link;
        }
        p.link = this;
    }

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

 

 

전체

 

//linked list

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

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

    deleteFirstNode(){
        if(this.link == null) return null;
        const remove = this.link;
        this.link = remove.link;
    }

    insertLastNode(item){
        let newNode = new nodeType(item);
        let p = this;
        if(this.link == null){
            this.link = newNode;
            newNode.link = this;
        }else{
            while(p.link != this){
                p = p.link;
            }
            p.link = newNode;
            newNode.link = this;
        }        
    }

    deleteLastNode(){
        if(this.link == null) return null;

        let p = this;
        while(p.link.link != this){
            p = p.link;
        }
        p.link = this;
    }

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

let circleList = new nodeType("head");

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

circleList.print();

 

지난 번 만들어 놓았던 단순연결리스트와 크게 달라지지는 않아서 이거 만드는데 얼마 걸리지 않았다.