[자료구조 with JS] 연결 리스트(Linked List) (1) 개념과 클래스

 

연결 리스트(Linked List)

 연결 리스트는 순서가 있는 데이터의 집합으로, 여러 노드들이 들어있다. 각 노드는 정보를 담고 있으며 다른 노드를 가리킨다. 배열은 크기가 고정되어 있는 만면, 연결 리스트는 실행 시간에 메모리를 할당, 해제할 수 있다. 즉, 동적 자료 구조이다.

연결 리스트

연결 리스트의 특징

1. 연결 리스트 내부의 노드의 순서는 항상 유지된다.

2. 모든 연결 리스트에는 두 개의 특수한 노드가 있다: 맨 처음 노드인 head, 맨 마지막 노드인 tail이다.

3. tail 노드를 알아볼 수 있는 방법: 다음 노드에 대한 참조가 없다.

4. 모든 노드에는 두 개의 부분이 있다. 데이터 파트와 다음 노드에 대한 참조 파트이다.

5. 어떠한 타입의 자바스크립트 데이터든 노드에 할당할 수 있다.

 

 

노드와 연결 리스트 클래스

class Node{
    constructor(data, next = null){
        this.data = data;
        //이 노드 다음에 오는 노드가 next에 할당된다.
        this.next = next;
    }
}

class LinkedList{
    constructor() {
        this.head = null;
    }
}

 

반응형

 

연결 리스트 클래스의 메서드

LinkedList.size()

연결 리스트의 크기를 return 한다.

class LinkedList{
    //...
    size(){
        let counter = 0;
        let node = this.head;

        while(node) {
            counter++
    	    node = node.next;
        }

        return counter;
    }
}

 

LinkedList.clear()

연결 리스트의 노드들을 전부 삭제한다. 연결 리스트의 field는 head밖에 없기 때문에 head를 삭제하면 그 외 모든 노드들도 삭제된다.

clear() {
    this.head = null;
}

 

 

다음 글:

[자료구조 with JS] 연결 리스트(Linked List) (2) 삽입, 검색, 삭제

[자료구조 with JS] 연결 리스트(Linked List) (3) 반복문과 알고리즘

 

 

참고: ⟨자바스크립트로 하는 자료구조와 알고리즘(배세민 저)⟩, The Coding Interview Bootcamp: Algorithms + Data Structures (Udemy Course)