단일연결리스트

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

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

node 란

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();

출처: https://hokeydokey.tistory.com/49