[자료구조] Linked list - 1

Linked List는 데이터를 순서대로 저장하는 자료구조입니다. 각 데이터 요소는 노드(Node)라고 불리는 객체로 표현됩니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터(링크)로 구성됩니다. 링크드 리스트는 노드들이 서로 물리적으로 연속되어 있지 않아도 되며, 각 노드는 독립적으로 존재하면서 다음 노드로의 연결 정보를 가지고 있습니다.

 

js로 표현한 연결 리스트(단일 연결 리스트)

const list = {
    head: {
        value: 6
        next: {
            value: 10                                             
            next: {
                value: 12
                next: {
                    value: 3
                    next: null	
                    }
                }
            }
        }
    }
};

장점: 연결 리스트는 요소 추가 및 삭제가 간편하며, 배열에 비해 메모리 사용이 유연합니다.

단점: 연결 리스트는 요소를 찾을 때 순차 접근해야 하므로 탐색 속도가 느리며, 각 노드가 포인터를 가지고 있어 더 많은 메모리를 사용합니다.

(포인터란 : 프로그래밍 언어에서 다른 변수, 혹은 그 변수의 메모리 공간주소를 가리키는 변수)

https://www.freecodecamp.org/korean/news/implementing-a-linked-list-in-javascript/

 

 

 

 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;
        while (current) {
            console.log(current.data);
            current = current.next;
        }
    }
}

// 연결 리스트 생성 및 사용
const linkedList = new LinkedList();
linkedList.append(10);
linkedList.append(20);
linkedList.append(30);

linkedList.display(); // 연결 리스트 출력: 10, 20, 30

 

연결 리스트의 유형

- Singly Linked Lists (단일 연결 리스트) : 각 노드는 하나의 포인트만 가진다

- Doubly Linked Lists (이중 연결 리스트) : 각 노드는 두개의 포인터를 가짐, 다음 노드 이전 노드를 가르킴

- Circular Linked List (원형 연결 리스트) : 마지막 노드의 포인터가 첫 노드 또는 특정 노드를 가르키고 있는 루프 형태