연결리스트란??

value와 pointer가 한 쌍인 노드가 모여있는 자료구조형이다

linked list vs 배열, 객체

탐색할때 특정값을 살펴보려면 heade부터 시작해서 노드들을 traversing해야하므로
시간복잡도는 O(n)이다
반면 특정 값을 삽입할 경우에는 배열보다 낫다

삭제와 추가: 객체와 linked list모두 빠르다
하지만 다음 노드를 가리키는 pointer가 있으므로 order가 있는 자료구조이다

pointer란?

원하는 데이터가 저장되어 있는 메모리 주소를 referencing하는 작업이다

const obj1 = { a: true };
const obj2 = obj1; // 이게 pointer이다.

메모리에 저장되어있는것은?? { a: true } 하나만이다!!
다만 obj1, obj2가 참조를 하는 것뿐

• 포인터가 특정메모리 주소를 참조할경우, 삭제를 해도 메모리 공간에는 삭제되지 않는다
  왜??? 가비지콜렉터가 해당 메모리 주소를 참조중인걸로 간주한다

구현

class LinkedList {
            constructor(value) {
                this.head = {
                    value,
                    next: null
                };
                this.tail = this.head;
                this.length = 1;
            }
            append(value) {
                const newNode = {
                    value,
                    next: null
                }
                
                this.tail.next = newNode;
                console.log(this.tail)
                this.tail = newNode;
                this.length++;
                return this;
            }
            prepend(value) {
                const newNode = {
                    value,
                    next: null
                }
                newNode.next = this.head;
                this.head = newNode;
                this.length++;
                return this;
            }
        }
        let myLinkedList = new LinkedList(10);
        myLinkedList.append(5)
        console.log(myLinkedList)

5를 append했을때
현재 노드의 head 10, next 5
다음 노드의 head 5, next null
를 확인해볼수 있다

레퍼런스

자바스크립트의 자료구조 3 : 연결 리스트(Linked List)