연결 리스트 (Linked List)

자료구조: 연결 리스트

연결 리스트(Linked List)는 노드(Node)라는 개별 요소들이 순차적으로 연결된 형태의 자료구조입니다. 각 노드는 데이터와 다음 노드에 대한 참조(포인터)를 가지고 있습니다. 연결 리스트는 배열과 달리 요소들이 메모리 상에 연속적으로 배치되지 않으며, 동적으로 크기가 조정될 수 있습니다.

연결 리스트의 종류

1. 단일 연결 리스트(Singly Linked List):
   • 각 노드는 하나의 데이터와 다음 노드를 가리키는 하나의 포인터를 가집니다.
   • 마지막 노드는 다음 노드에 대한 포인터가 null입니다.
2. 이중 연결 리스트(Doubly Linked List):
   • 각 노드는 데이터와 두 개의 포인터(이전 노드와 다음 노드)를 가집니다.
   • 양방향으로 순회가 가능합니다.
3. 원형 연결 리스트(Circular Linked List):
   • 마지막 노드의 다음 노드가 첫 번째 노드를 가리키는 구조입니다.
   • 단일 또는 이중 연결 리스트 형태로 구현될 수 있습니다.

연결 리스트의 특징

• 동적 크기 조정: 노드를 추가하거나 제거함에 따라 리스트의 크기가 동적으로 조정됩니다.
• 비연속적 메모리 배치: 노드들이 메모리 상에 비연속적으로 배치됩니다.
• 삽입 및 삭제의 효율성: 중간에 노드를 삽입하거나 삭제하는 연산이 배열보다 효율적입니다.

연결 리스트의 장단점

장점:

• 크기가 동적으로 조정되므로 메모리 효율적 사용이 가능합니다.
• 중간에 요소를 삽입하거나 삭제하는 작업이 배열보다 효율적입니다(포인터 조작만으로 가능).

단점:

• 인덱스를 통한 접근 속도가 느립니다(O(n)).
• 추가적인 포인터 저장 공간이 필요합니다.

연결 리스트와 배열의 비교

• 접근 속도: 배열은 인덱스를 통한 빠른 접근이 가능 > 연결 리스트는 순차적으로 접근
• 삽입 및 삭제: 연결 리스트는 중간에 요소를 삽입하거나 삭제할 때 효율적 > 배열은 모든 요소를 이동시켜야 하기 때문에 비효율적입니다.
• 메모리 사용: 배열은 고정된 크기를 가지며, 크기를 변경하기 어렵지만, 연결 리스트는 필요에 따라 크기를 조정할 수 있습니다.

	배열	연결리스트
크기	고정	동적
주소	연속	불연속
데이터 참조	O(1)	O(n)
삽입과 삭제	O(n) -  기존 모든 데이터 이동 필요	O(n) - 삽입하려는 노드까지 계속 타고 가야 함

 

자바스크립트 예시

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

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

    // 리스트의 끝에 노드를 추가합니다.
    append(value) {
        const newNode = new Node(value);
        if (this.head === null) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next !== null) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }

    // 특정 인덱스에 노드를 추가합니다.
    insertAt(value, index) {
        if (index < 0 || index > this.size) {
            return console.log("Invalid index");
        }
        const newNode = new Node(value);
        let current = this.head;
        let previous;
        if (index === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            for (let i = 0; i < index; i++) {
                previous = current;
                current = current.next;
            }
            newNode.next = current;
            previous.next = newNode;
        }
        this.size++;
    }

    // 특정 인덱스의 노드를 제거합니다.
    removeAt(index) {
        if (index < 0 || index >= this.size) {
            return console.log("Invalid index");
        }
        let current = this.head;
        let previous;
        if (index === 0) {
            this.head = current.next;
        } else {
            for (let i = 0; i < index; i++) {
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.size--;
        return current.value;
    }

    // 특정 값을 가진 노드를 제거합니다.
    remove(value) {
        let current = this.head;
        let previous = null;

        while (current !== null) {
            if (current.value === value) {
                if (previous === null) {
                    this.head = current.next;
                } else {
                    previous.next = current.next;
                }
                this.size--;
                return current.value;
            }
            previous = current;
            current = current.next;
        }
        return null;
    }

    // 리스트에서 특정 값을 찾습니다.
    indexOf(value) {
        let current = this.head;
        let index = 0;

        while (current !== null) {
            if (current.value === value) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    // 리스트가 비어 있는지 확인합니다.
    isEmpty() {
        return this.size === 0;
    }

    // 리스트의 크기를 반환합니다.
    sizeOfList() {
        return this.size;
    }

    // 리스트의 모든 원소를 출력합니다.
    printList() {
        let current = this.head;
        let result = '';
        while (current !== null) {
            result += current.value + (current.next ? ' -> ' : '');
            current = current.next;
        }
        console.log(result);
    }
}

// 사용 예시
const ll = new LinkedList();