[Javascript] 자료구조 - Linked List

 

 

 

1. Linked List란?

Linked List란 선형의 자료구조인데, 데이터 요소들을 순서대로 저장하는데 사용된다. 각 요소들은 데이터와 다음 요소를 가리키는 포인터로 이루어져있다. 다음 요소의 정보가 있기 때문에 이 포인터 정보를 통해서 연결되어있는 연결 리스트인 것이다. 그렇기 때문에 메모리에 연속적으로 저장이 되지 않아도 된다. 

 

2. Linked List가 사용되는 사례

Linked List는 다양한 분야에서 사용이 되는데 데이터 요소를 순차적으로 저장하여 효율적인 삽입 및 삭제를 가능하게 하기 때문에 스택과 큐와 같은 추상 자료형을 구현할 때도 활용되며, 후입선출과 선입선출 데이터 구조를 각각 지원한다. 또한 동적 메모리 할당을 위한 메모리 관리에 사용되며, 그래프 및 트리 알고리즘에서는 인접 리스트로 활용된다. 운영 체제에서는 프로세스 관리에 활용되며, 데이터베이스 관리 시스템에서는 인덱스 구조나 연결된 레코드를 관리하는 데 사용된다.

 

3. Javascript로 구현한 Linked List

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

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

    // 링크드 리스트 끝에 노드 추가
    append(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 링크드 리스트 출력
    display() {
        let current = this.head;
        let result = "";
        while (current) {
            result += current.data + " -> ";
            current = current.next;
        }
        result += "null";
        console.log(result);
    }
}

// 예제 사용
const linkedList = new LinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.display(); // 출력: 1 -> 2 -> 3 -> null