[자료구조 알고리즘] Linked List ??

Linked List란?

컴퓨터 자료구조의 한 종류로 일렬로 정렬된 데이터를 저장할때 사용한다.
데이터를 저장할 수 있는 공간이 있으면 데이터 안에 그 다음 데이터주소를 가지고 있다.

Array

배열은 배열방 크기를 물리적으로 갖고있기때문에 방 크기를 늘리거나 줄일 수 없다.
따라서 배열이 추가될때마다 배열은 다시 선언해서 복사하고 하나 추가하고 해야한다.
길이 정해지지 않은 데이터를 핸들링 할때는 Linked List를 활용해보자.

Linked List 추가와 삭제

const LinkedList = (() => {
    function LinkedList() {
        this.length = 0;
        this.head = null;
    }

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

    LinkedList.prototype.add = function (value) {
        let node = new Node(value);
        let current = this.head;

        if(!current) { // 노드가 없을때
            this.head = node; // 노드 추가
            this.length ++;
            return node;
        }
        while(current.next) { // 노드가 있을때 마지막 노드 찾기
            current = current.next
        }
        current.next = node // 마지막에 노드 추가
        this.length++;
        return node
    }

    LinkedList.prototype.remove = function (position) { // 첫번째 노드를 삭제하는건 다음 기회에 
        let current = this.head;

        while (current.next !== null) { // 노드를 돌면서 마지막노드가 아닐때 까지
            if (current.next.data === position) { // 다음 데이터가 내가 삭제해야 할 노드면
                current.next = current.next.next; // 내 다음노드를 바라보던 값을 다음다음값으로 변경
            } else {
                current = current.next;
            }
        }

        this.length--;
        return this.head;
    }
    return LinkedList;
})()

const list = new LinkedList();
list.add(1);
list.add(2);
list.add(3); // length 3
list.remove(2); // length 2