[3주차] 연결리스트

1. 시간복잡도

O(1)
O(logN)
O(n)
O(NlogN)
O(n^2)

O(n^3)
O(2^n)
O(n!)

for(let i = 0; i < arr.length; i++){ // O(n)
	for(let j = 0; j < arr.length; j++) // O(n^2)
      // 지수 : 반복문 중첩횟수
}

for(let i = 0; i < arr.length; i++){ // O(n)
	for(let j = 0; j < arr.length; j * 2) // O(NlogN)
      // O(logN) : 반씩 쪼개서 사라지는
}

O(n) vs O(2n) vs O(n^2)

2처럼 계수 붙으면 같은 거로 침
지수 붙으면 차원이 다른 거 

---

2. 연결리스트

엑셀 떠올려보셈

[1, 2, 3, 4, 5]

수정, 삭제, 삽입, 조회 => O(n)
연결리스트 자료구조 O(n)
무난함

연결리스트 단점: 이전값을 못 찾음

3. add 구현

class Linkedlist {
    length = 0; 
    /* constructor(length){
        this.length = length;
    } */
    head = null;

    add(value) {
        if(head){
            let current = this.head;
            while(current.next){ // next 없을 때까지 타고타고 들어가서
                current = current.next;
            } 
            current.next = new Node(value); // current.next가 없으니까 add
        } else {
            this.head = new Node(value);    
        }
        this.length++;
        return this.length;
    }
	search(value) {}
	remove(value) {}
}

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

const ll = new Linkedlist();
ll.length;
ll.add(1); // 1
ll.add(2); // 2
ll.add(3); // 3
ll.add(4); // 4
ll.add(5); // 5
console.log(ll.add(6)); // 6

4. search 구현

class Linkedlist {
    length = 0; 
    /* constructor(length){
        this.length = length;
    } */
    head = null;

    add(value) {
        if(head){
            let current = this.head;
            while(current.next){ // next 없을 때까지 타고타고 들어가서
                current = current.next;
            } 
            current.next = new Node(value); // current.next가 없으니까 add
        } else {
            this.head = new Node(value);    
        }
        this.length++;
        return this.length;
    }
    search(index) {
        let count = 0;
        let current = this.head;
        while( count < index){ // index 만큼 current 넘겨서 찾는 거
            current = current?.next;
            count++;
        }
        return current?.value;
    }
    remove(value) {}
}

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

const ll = new Linkedlist();
ll.length;
ll.add(1); // 1
ll.add(2); // 2
ll.add(3); // 3
ll.add(4); // 4
ll.add(5); // 5
ll.add(6); // 6
console.log(ll.search(3)); // 4
console.log(ll.search(5)); // 6
console.log(ll.search(7)); // undefined
ll.remove(4);
ll.search(4); // null

5. remove 구현

...은 내일