연결 리스트(Linked List)

---

연결 리스트(Linked List)

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 구조의 자료구조이다. 각 노드는 데이터와 링크로 이루어져있다.

data : 노드가 가지고 있는 데이터
link : 다음 노드의 주소를 담고 있음

연결 리스트는 head와 tail이 존재하는데 head는 첫번째 노드를 가르키고 tail은 마지막 노드를 가르킨다.

연결 리스트 특징

• 메모리가 허용하는 한 노드를 제한없이 추가할 수 있다.
• 연결 리스트의 탐색은 O(n)이 소요된다.
• 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
• 메모리가 분산되어 노드를 저장하고 포인터를 통해 서로를 참조한다.

연결 리스트 종류

연결 리스트에는 3가지 종류가 있다.

• singly linked list : Head에서 Tail까지 단방향으로 이어지는 연결 리스트
  

• doubly linked list : 양방향으로 이어지는 연결 리스트
  

• circular linked list : Tail이 Head로 연결되는 연결 리스트
  

구현

• singly linked list

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

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

    find(value) {
        let currNode = this.head;

        while(currNode.value !== value) {
            currNode = currNode.next;
        }

        return currNode;
    }

    append(newValue) {
        if(!newValue) {
            return;
        }

        const newNode = new Node(newValue);

        if(this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        }
        else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
    }

    insert(node, newValue) {
        if(!node?.value || ! newValue) {
            return;
        }

        const newNode = new Node(newValue);

        newNode.next = node.next;
        node.next = newNode;
    }

    remove(value) {
        let prevNode = this.head;

        while(prevNode.next.value !== value) {
            prevNode = prevNode.next;
        }

        if(prevNode.next !== null) {
            prevNode.next = prevNode.next.next;
        }
    }

    size() {
        let size = 1;
        let currNode = this.head;

        if(!currNode) {
            return 0;
        }

        while(currNode !== this.tail) {
            size++;
            currNode = currNode.next;
        }

        return size;
    }

    display() {
        let currNode = this.head;
        let displayString = "[";

        while(currNode !== null) {
            displayString += `${currNode.value}, `;
            currNode = currNode.next;
        }

        displayString = displayString.substr(0, displayString.length - 2);
        displayString += "]";
        
        console.log(displayString);
    }
}

const singlyLinkedList = new SinglyLinkedList();

singlyLinkedList.append(1);
singlyLinkedList.append(2);
singlyLinkedList.append(3);
singlyLinkedList.append(5);
singlyLinkedList.display();
console.log(singlyLinkedList.find(3));
singlyLinkedList.remove(3);
singlyLinkedList.display();
singlyLinkedList.insert(singlyLinkedList.find(2), 10);
singlyLinkedList.display();
console.log(singlyLinkedList.size());

• doubly linked list

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

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

    find(value) {
        let currNode = this.head;

        while(currNode.value !== value) {
            currNode = currNode.right;
        }

        return currNode;
    }

    append(newValue) {
        if(!newValue) {
            return;
        }

        const newNode = new Node(newValue);

        if(this.head === null) {
            this.head = newNode;
            this.tail = newNode;
        }
        else {
            newNode.left = this.tail;

            this.tail.right = newNode;
            this.tail = newNode;
        }
    }

    insert(node, newValue) {
        if(!node?.value || ! newValue) {
            return;
        }

        const newNode = new Node(newValue);

        node.right.left = newNode;
        newNode.right = node.right;
        newNode.left = node;
        node.right = newNode;
    }

    remove(value) {
        let prevNode = this.head;

        while(prevNode.right.value !== value) {
            prevNode = prevNode.right;
        }

        if(prevNode.right !== null) {
            prevNode.right.left = null;
            prevNode.right.right.left = prevNode;
            prevNode.right = prevNode.right.right;
            prevNode.right.right = null;
        }
    }

    size() {
        let size = 1;
        let currNode = this.head;

        if(!currNode) {
            return 0;
        }

        while(currNode !== this.tail) {
            size++;
            currNode = currNode.right;
        }

        return size;
    }

    display() {
        let currNode = this.head;
        let displayString = "[";

        while(currNode !== null) {
            displayString += `${currNode.value}, `;
            currNode = currNode.right;
        }

        displayString = displayString.substr(0, displayString.length - 2);
        displayString += "]";
        
        console.log(displayString);
    }
}

const doublyLinkedList = new DoublyLinkedList();

doublyLinkedList.append(1);
doublyLinkedList.append(2);
doublyLinkedList.append(3);
doublyLinkedList.append(5);
doublyLinkedList.display();
console.log(doublyLinkedList.find(3));
doublyLinkedList.remove(3);
doublyLinkedList.display();
doublyLinkedList.insert(doublyLinkedList.find(2), 10);
doublyLinkedList.display();
console.log(doublyLinkedList.size());

• circular linked list

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

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

    find(value) {
        let currNode = this.head;

        while(currNode.value !== value) {
            currNode = currNode.next;
        }

        return currNode;
    }

    append(newValue) {
        if(!newValue) {
            return;
        }

        const newNode = new Node(newValue);

        if(this.head === null) {
            this.head = newNode;
            this.tail = newNode;
            newNode.next = this.head;
        }
        else {
            newNode.next = this.tail.next;
            this.tail.next = newNode;
            this.tail = newNode;
        }
    }

    insert(node, newValue) {
        if(!node?.value || ! newValue) {
            return;
        }

        const newNode = new Node(newValue);

        newNode.next = node.next;
        node.next = newNode;
    }

    remove(value) {
        let prevNode = this.head;

        while(prevNode.next.value !== value) {
            prevNode = prevNode.next;
        }

        if(prevNode.next !== null) {
            prevNode.next = prevNode.next.next;
        }
    }

    size() {
        let size = 1;
        let currNode = this.head;

        if(!currNode) {
            return 0;
        }

        while(currNode !== this.tail) {
            size++;
            currNode = currNode.next;
        }

        return size;
    }

    display() {
        let currNode = this.head;
        let displayString = "[";

        if (currNode !== null) {
            do {
                displayString += `${currNode.value}, `;
                currNode = currNode.next;
            } while(currNode !== this.head);
        }

        displayString = displayString.substr(0, displayString.length - 2);
        displayString += "]";
        
        console.log(displayString);
    }
}

const circularLinkedList = new CircularLinkedList();

circularLinkedList.append(1);
circularLinkedList.append(2);
circularLinkedList.append(3);
circularLinkedList.append(5);
circularLinkedList.display();
console.log(circularLinkedList.find(3));
circularLinkedList.remove(3);
circularLinkedList.display();
circularLinkedList.insert(circularLinkedList.find(2), 10);
circularLinkedList.display();
console.log(circularLinkedList.size());