immersive TIL #4

linkedList

변수를 저장하는 방법에는 배열과 연결리스트(linkedList)가 있다.
배열의 장점은 i번째 원소를 바로 알 수 있지만, 원소의 추가나삭제가 복잡하다.
연결리스트는 각 원소가 node에 들어있고 이 Node는 값이 들어있는 data와 다음 원소를 가리키는 link로 구성되어 있으며
장점은 원소의 추가, 삭제가 쉽지만 처음(head)부터 순서대로 찾아봐야하기 때문에 i번째 원소를 알기 어렵다.

연결 리스트는 그 크기가 동적인 자료구조로, 자료구조를 구성하는 요소, -우리는 이것을 노드(Node) 라고 부릅니다- 노드의 연결로 이루어진 자료 구조다

임의의 지점에 데이터의 추가와 삭제를 할 경우, O(1) (상수 시간)의 시간 복잡도를 갖는다.

linkedList의 method

-addToTail(value) - 주어진 값을 연결 리스트의 끝에 추가합니다.

-remove(value) - 주어진 값을 찾아서 연결을 해제(삭제)합니다.

-getNodeAt(index) - 주어진 인덱스의 노드를 찾아서 반환합니다. 값이 아니라 노드를 반환해야 하는 것에 주의하세요. 해당 인덱스에 노드가 없다면 undefined를 반환합니다.

-contains(value) - 연결리스트에 주어진 값을 가지는 노드의 존재 여부를 반환합니다.

-indexOf(value) - 주어진 값의 인덱스를 반환합니다. 없을 경우 -1을 반환합니다.

코드로 나타내면

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

class LinkedList {
    constructor() {
        this.head = null; // 첫번째 노드
        this.tail = null; // 마지막 노드
        this._size = 0; // 연결리스트의 총 size 즉,node 개수 
    }

    addToTail(value) {
        let node = new Node(value);

        if (this._size === 0) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        this._size++;
    }

    remove(value) {
        let node = this.head;
        let nodeNext = node.next;

        if (node === null) {
            return;
        }
        if (node.value === value) {
            if (this._size === 1) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = nodeNext;
            }
        }

        if (this._size > 1) {
            for (let i = 0; i < this._size; i++) {
                if (nodeNext.value === value) {
                    if (nodeNext === this.tail) {
                        this.tail = node;
                        nodeNext = null;
                    }
                    nodeNext = nodeNext.next;
                }
                node = nodeNext;
            }
        }
        this._size--;
    }

    getNodeAt(index) {
        let node = this.head;

        if (this._size < index) {
            return undefined;
        }
        for (let i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    contains(value) {
        let node = this.head;

        for (let i = 0; i < this._size; i++) {
            if (node.value === value) {
                return true;
            }
            node = node.next;
        }
        return false;
    }

    indexOf(value) {
        let node = this.head;

        for (let i = 0; i < this._size; i++) {
            if (node.value === value) {
                return i;
            }![](https://velog.velcdn.com/images%2Fpaxkk%2Fpost%2F09008078-0088-445e-bec5-39f181383c89%2FScreenshot%20from%202020-07-27%2022-45-33.png)
            node = node.next;
        }
        return -1;
    }

    size() {
        return this._size;
    }
}

이중 연결 리스트

-이중 연결리스트는 한 노드에 두개의 링크가 존재하는데 각각 이전노드와 다음노드를 가르킵니다.
-이중 연결 리스트는 이전 노드의 링크를 통해 O(1)의 시간 복잡도로 이전 노드를 찾을 수 있습니다
-이중 연결 리스트에서 노드를 추가하거나 제거하려면 단일 연결 리스트보다 많은 작업이 필요하지만
작업이 단순하고 효율적이다.