[Data Structure] 링크드리스트

Data Structure

[Data Structure] 링크드리스트

WebDevLee 2024. 5. 18. 01:27

링크드리스트(linked_list) 자료구조에 대해 정리하였습니다.

< 종류별 링크드 리스트 >

[ 단일 링크드 리스트 (Singly Linked List) ]

각 노드는 데이터와 다음 노드를 가리키는 하나의 포인터를 포함합니다.
마지막 노드의 포인터는 null을 가리키며 리스트의 끝을 나타냅니다.

Node1 -> Node2 -> Node3 -> null

[ 이중 링크드 리스트 (Doubly Linked List) ]

각 노드는 데이터를 포함하며, 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터를 가지고 있습니다.
양방향 탐색이 가능하다는 장점이 있습니다.

null <- Node1 <-> Node2 <-> Node3 -> null

[ 원형 링크드 리스트 (Circular Linked List) ]

마지막 노드가 첫 번째 노드를 가리키도록 연결되어 있습니다.
단일 및 이중 링크드 리스트 형태로 구현될 수 있습니다.

Node1 -> Node2 -> Node3 -> Node1 (단일 원형 링크드 리스트)
null <- Node1 <-> Node2 <-> Node3 <-> Node1 (이중 원형 링크드 리스트)

< 장/단점 >

[ 장점 ]

동적 크기를 가지며, 크기를 사전에 정의할 필요가 없습니다.
삽입과 삭제가 배열에 비해 효율적입니다. (특히 리스트의 시작 부분에서)

[ 단점 ]

임의 접근이 불가능하여 특정 위치의 노드를 찾기 위해서는 처음부터 순차적으로 탐색해야 합니다.
각 노드가 추가적인 포인터를 저장하기 때문에 배열보다 메모리 오버헤드가 발생합니다.

< 주요 연산 >

삽입 (Insertion)
- 리스트의 시작 부분, 중간, 끝 부분에 노드를 삽입합니다.
- 시작 부분 삽입의 경우: 새 노드의 다음 포인터를 현재 첫 번째 노드를 가리키도록 설정하고, 헤드를 새 노드로 변경합니다.
- 중간 삽입의 경우: 삽입 위치의 이전 노드와 다음 노드를 각각 새 노드와 연결합니다.
삭제 (Deletion)
- 특정 위치에 있는 노드를 삭제합니다.
- 시작 부분 삭제의 경우: 헤드를 현재 첫 번째 노드의 다음 노드로 변경합니다.
- 중간 삭제의 경우: 삭제할 노드의 이전 노드의 포인터를 삭제할 노드의 다음 노드를 가리키도록 변경합니다.
탐색 (Search)
- 특정 값을 가지는 노드를 찾기 위해 리스트를 순차적으로 탐색합니다.
출력 (Display)
- 리스트에 있는 모든 노드를 순차적으로 출력합니다.
반전 (Reverse)
- 리스트를 반전시킵니다. prev, current, next 포인터를 사용하여 리스트의 노드들을 뒤집습니다.

< 구현 : 단일 링크드 리스트 >

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

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

    // 시작 부분 삽입
    insertAtBeginning(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    // 중간 삽입
    insertAtPosition(data, position) {
        if (position === 0) {
            this.insertAtBeginning(data);
            return;
        }
        const newNode = new Node(data);
        let current = this.head;
        let previous = null;
        let index = 0;

        while (index < position && current !== null) {
            previous = current;
            current = current.next;
            index++;
        }

        if (current === null) {
            console.log("Position out of bounds");
            return;
        }

        newNode.next = current;
        previous.next = newNode;
    }

    // 끝 부분 삽입
    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;
    }

    // 시작 부분 삭제
    deleteAtBeginning() {
        if (this.head) {
            this.head = this.head.next;
        }
    }

    // 중간 삭제
    deleteAtPosition(position) {
        if (position === 0) {
            this.deleteAtBeginning();
            return;
        }
        let current = this.head;
        let previous = null;
        let index = 0;

        while (index < position && current !== null) {
            previous = current;
            current = current.next;
            index++;
        }

        if (current === null) {
            console.log("Position out of bounds");
            return;
        }

        previous.next = current.next;
    }

    // 끝 부분 삭제
    deleteAtEnd() {
        if (!this.head) {
            return;
        }
        if (!this.head.next) {
            this.head = null;
            return;
        }
        let current = this.head;
        while (current.next && current.next.next) {
            current = current.next;
        }
        current.next = null;
    }

    // 탐색
    search(data) {
        let current = this.head;
        while (current) {
            if (current.data === data) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 출력
    display() {
        let current = this.head;
        let listString = '';
        while (current) {
            listString += current.data + ' -> ';
            current = current.next;
        }
        listString += 'null';
        console.log(listString);
    }

    // 반전
    reverse() {
        let prev = null;
        let current = this.head;
        let next = null;
        while (current) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        this.head = prev;
    }
}

// 사용 예제
const sll = new SinglyLinkedList();
sll.append(1);
sll.append(2);