[javascript] 단순 연결리스트 만들기 linked-list

javascript의 배열은 array-list라는 것의 형태를 띄고 있어 배열의 크기 존재하지 않는다. 그런데 c 같은 언어들은 배열의 크기가 존재하기에 한 배열을 유한하게 밖에 사용 할 수 없다. 그래서 개발자들은 노드리스트라는 개념을 만들어 각각의 구조체들로 서로를 연결하는 것을 만들었다. 

 

연결리스트에는 단순 연결리스트, 이중연결리스트,  원형연결리스트가 있으며 이 연결리스트들을 이용하여 스택, 큐, 트리등 다양한 자료구조를 만들 수 있다. 

 

node 란 

 

linked-list

 

node란 data필드와 link필드를 가지고 있는 일종의 구조체로 link를 통해서는 다음 연결된 노드에 접근 할 수 있다. 

 

simple linked-list는 처음 노드를 header라고 하며 마지막 노드의 link는 항상 null이다.

 

연결리스트 프로퍼티 

 

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

 

생성자 인자로 받아온 받아온 값을 data프로퍼티에 넣는다. 

 

 

연결리스트 메서드

원래는 header노드 앞쪽 부분에만 node를 추가하는 메서드만 만들려고 했으나 노드 끝 부분에 node를 추가/삭제 하는 메서드 만들기가 어려운 것도 아니고 그냥 만들었다. 

 

insertFirstNode() // header 노드앞에 새로운 노드를 만들어 연결하고 기존 노드와 연결한다. 

 

insertLastNode() // linked-list 끝에 노드를 추가한다. 

 

deleteFirstNode() // header 노드 앞 노드를 삭제하고 끊어진 부분을 연결한다. 

 

deleteLastNode() // linked-list 끝에 노드를 삭제한다. 

 

insertFirstNode(item){
        let newNode = new nodeType(item);
        if(this.link == null){
            this.link = newNode;
        }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;
        while(p.link != null){
            p = p.link; //p가 마지막 노드를 가리키게 된다. 
        }
        p.link = newNode;
    }

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

        let p = this;
        while(p.link.link != null){
            p = p.link; //p가 마지막 노드 전을 가리키게 된다.
        }
        p.link = null;
    }

    print(){
        let string = "";
        for(let p = this; p != null; p=p.link){
            string += `${p.data} | `;
        }
        string += `NULL`;
        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;
        }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;
        while(p.link != null){
            p = p.link;
        }
        p.link = newNode;
    }

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

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

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



let head = new nodeType("head");
head.insertFirstNode(1); // head | 1 | null
head.insertFirstNode(2); // head | 2 | 1 | null
head.insertFirstNode(3); // head | 3 | 2 | 1 | null
head.insertFirstNode(4); // head | 4 | 3 | 2 | 1 | null
head.insertFirstNode(5); // head | 5 | 4 | 3 | 2 | 1 | null
head.insertFirstNode(6); // head | 6 | 5 | 4 | 3 | 2 | 1 | null
head.insertFirstNode(7); // head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null
head.insertFirstNode(8); // head | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null
head.insertLastNode(0); //  head | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | null
head.deleteFirstNode(); //  head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | null
head.deleteLastNode();  //  head | 7 | 6 | 5 | 4 | 3 | 2 | 1 | null

head.print();