[TIL 3] 배열과 연결리스트 in JS

자료구조의 기본, 배열과 연결리스트에 대해 공부했다.😶

배열(Array)

연관된 데이터를 연속적인 형태로 구성된 구조로, index를 가지고 있다.
고정된 크기를 가지며, 일반적으로 동적으로 크기를 늘릴 수 없다.
c나 c++에서는 배열을 선언할 때, 크기를 같이 선언해야 한다. 하지만 자바스크립트는 동적으로 늘릴 수 있다! 간편쓰하다.
자바스크립트처럼 대부분의 스크립트 언어는 동적으로 크기가 증감되도록 만들어져있다고 한다.
원소를 삭제하면 해당 index에 빈자리가 생긴다!

연결리스트(Linked List)

연결 리스트는 각 요소를 포인터로 연결해 관리하는 선형 자료구조이다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.

연결리스트는 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.

배열과 연결리스트 비교

메모리 차이

배열은 연속적으로, 링크드 리스트는 띄엄띄엄 메모리 공간을 차지한다! 배열은 메모리 공간을 연속적으로 차지하지만 링크드 리스트는 그럴 필요 없이 아무데나 있어도 된다. 위치를 포인터로 가지고 있기 때문이다.

탐색, 추가, 삭제 시간 차이

배열은 인덱스 값을 알고 있다면 탐색 시 O(1)시간이 걸린다. 하지만 값으로 찾는다면 O(n)시간이 걸린다.
연결리스트 또한 따로 인덱스가 없기 때문에, O(n)시간이 걸린다.

배열은 추가, 삭제 시 O(n)시간이 걸린다. 순차적으로 메모리 구조가 되어있기 때문에 중간에 삭제가 들어가면 나머지 요소들을 일일이 당기거나 밀어야 하기 때문이다. 따라서 배열을 사용할 때에는 추가, 삭제가 많은 것 보다는 탐색이 많은 로직을 사용할 때 쓰는 것이 좋다.
반면 연결리스트는 추가, 삭제는 O(1)시간이 걸리기 때문에, 추가, 삭제가 많은 로직에 용이하다고 할 수 있다.

singly Linked List 구현하기

//javascript로 singly linked list 구현하기👍

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

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.size = 0; // 링크드 리스트의 길이
    }

    find(value){
        let curNode = this.head;
        while(curNode != null){ // 링크드 리스트가 끝날 때 까지 
            if(curNode.value === value)
                return curNode;
            curNode = curNode.next;
        }
        return null; // 없을 때에는 null 반환
    }

    append(value){
        const newNode = new Node(value);
        if(this.head === null){
            this.head = newNode;
            this.tail = newNode;
        }else{
            this.tail.next = newNode;
            this.tail = newNode;
        }

        this.size += 1;
    }

    insert(node, value){
        const newNode = new Node(value);
        newNode.next = node.next;
        node.next = newNode;
        this.size += 1;
    }

    remove(value){
        let prevNode = this.head;
        while(prevNode.next !== null){
            if(prevNode.next.value === value){
                prevNode.next = prevNode.next.next;
                this.size -=1;
                return true;
            }
            prevNode = prevNode.next;
        }
        return false;
    }

    display(){
        let curNode = this.head;
        let displayString = "[";
        while(curNode!== null){
            displayString += `${curNode.value}, `;
            curNode = curNode.next;
        }
        displayString = displayString.substr(0, displayString.length - 2);
        displayString += "]";
        console.log(displayString);
    }

    returnSize(){
        return this.size;
    }
}
// 사용해보기 
const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(5);
linkedList.display(); //[1, 2, 3, 5]
console.log(linkedList.find(3)); //Node { value: 3, next: Node { value: 5, next: null } }
console.log(linkedList.find(6)); //null
console.log(linkedList.remove(3)); //true
console.log(linkedList.remove(6)); //false
linkedList.display(); //[1, 2, 5]
linkedList.insert(linkedList.find(2), 10);
linkedList.display();
console.log(linkedList.returnSize()); //4