링크드 리스트(Linked List)

1. 링크드 리스트(Linked List) 구조

• 연결 리스트라고도 합니다.
• 링크드 리스트는 떨어진 곳에 존재한 데이터를 화살표(포인터)로 연결해서 데이터를 관리하는 구조
• 배열은 연결된 공간에 데이터를 나열한 구조

2. 링크드 리스트 구조와 용어

• 노드(Node) : 데이터를 저장 하는 단위(Data, 포인터) 로 구성되어 있습니다.
• 포인터(Pointer) : 각 노드에서, 다음의 노드와의 연결 정보를 가지고 있는 공간

출처 : https://ko.wikipedia.org/wiki/%EC%97%B0%EA%B2%B0_%EB%A6%AC%EC%8A%A4%ED%8A%B8

3. 링크드 리스트 장점,단점

• 장점

1. 배열의 크기를 미리 지정하지 않아도 된다. (Java는 배열 선언시 크기를 미리 지정해야 하지만, JavaScript는 지정하지 않아도 되기 때문에 JavaScript를 사용한다면 장점은 아니다.)
2. 노드의 추가 및 삭제시 전체 배열의 조정이 필요 없다(Pointer 값만 바꾼다.)

• 단점

1. 특정 위치의 데이터를 검색할 때는 head(첫번째 노드) 에서부터 순차적으로 검색하기 때문에 비효율적이다.
2. 구현이 복잡하다.
3. 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

 

4. 링크드 리스트 구현
링크드 리스트는 구현은 JavaScript로 하도록 하겠습니다.

class Node {
    constructor(data, next=null){
        this.data = data;
        this.next = next;
    }
}

class NodeMng {
    constructor(data){
        this.head = new Node(data);
    }

    desc() {
        let node = this.head;
        while (node) {
            console.log(node.data);
            node = node.next;
        }
    }

    add(data) {
        let node = this.head;
        while (node.next) {
            node = node.next;
        }
        node.next = new Node(data);
    } 
    
    findPrevious(data) { 
        let node = this.head; 
        while(node.next != null && node.next.data !== data) { 
            node = node.next; 
        } 
        return node; 
    }

    
    remove(data){
        let preNode = this.findPrevious(data); 
        preNode.next = preNode.next.next; 
    }

    
}