Section20 - 이중 연결 리스트

---

---

[이중 연결 리스트]

 

싱글 리스트와 거의 비슷함

하지만 해줘야하는 일은 좀 더 많음

 

previous로 가는 node도 있음

 

 

[코드]

 

// piece of data -val
// reference to next node - next

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

class DoublyLinkedList{
  constructor(){
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  push(val){

    const newNode = new Node(val);

    if(this.length === 0){
      this.head = newNode;
    } else {

      this.tail.next = newNode;
      newNode.prev = this.tail;

    }

    this.tail = newNode;
    this.length ++;

    return this;

  }

  pop(){

    if(this.length === 0) return undefined;
    
    const poppedNode = this.tail;

    if(this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {

      // const newTail = this.tail.prev;
      // this.tail.prev = null;
      // newTail.next = null;
      // this.tail = newTail;

      this.tail = poppedNode.prev;
      this.tail.next= null;
      poppedNode.prev = null;

    }

    this.length --;
    return poppedNode;

  }

  shift(){
    if(this.length === 0 ) return undefined;

    const oldHead = this.head;

    if(this.length === 1){
      this.head = null;
      this.tail = null;
    } else {

      this.head = oldHead.next;
      this.head.prev = null;
      oldHead.next = null

    }
    this.length --;
    return oldHead;

  }

  unshift(val){
    const newNode = new Node(val);
    if(this.length === 0){
      // this.push(val); 

      this.head = newNode;
      this.tail = newNode;

    } else {

      // const oldHead = this.head;
      
      // this.head = newNode;
      // this.head.next = oldHead;
      // oldHead.prev = newNode;
      // this.length++

      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;

    }
    this.length++;

    return this;
  }

  get(idx){

    if(idx < 0 || idx >= this.length) return null;

    if(idx < Math.ceil(this.length/2)){

      let cnt = 0;
      let temp = this.head;
      while(cnt !== idx){
        temp = temp.next;
        cnt++
      }

      return temp;
    } else {
      let cnt = this.length-1;
      let temp = this.tail;
      while(cnt !== idx){
        temp = temp.prev;
        cnt--;
      }
      return temp;
    }

  }

  set(idx,val){
    
    let foundNode = this.get(idx);

    if(foundNode !== null){
      foundNode.val = val;
      return true;
    }

    return false;
  }

  insert(idx,val){

    if(idx < 0 || idx > this.length) return false;
    if(idx === 0) return !!this.unshift(val);
    if(idx === this.length) return !!this.push(val);

    const newNode = new Node(val);
    const beforeNode = this.get(idx-1);
    const afterNode = beforeNode.next;

    beforeNode.next = newNode;
    newNode.prev = beforeNode;
    newNode.next = afterNode;
    afterNode.prev = newNode;

    this.length++;
    return true;

  }

  remove(idx){

    if(idx <= 0 || idx >= this.length) return false;
    if(idx === 0) return !!this.shift();
    if(idx === this.length-1) return !!this.pop();

    const removedNode = this.get(idx);
    removedNode.prev.next = removedNode.next;
    removedNode.next.prev = removedNode.prev;

    removedNode.next = null;
    removedNode.prev = null
    
    this.length--;

    return removedNode;

  }

}

 

[BigO]

삽입 O(1)

제거 O(1)

검색 O(N)

접근 O(N)

 

기술적으로는 검색이 O(N/2)이긴 함

 

[Recap]

1.이전으로 가는 포인터가 있다는것 이외엔 싱글 리스트와 동일

검색기록 같은것들 뒤로가기 앞으로가기 이런것들 이중연결리스트로 많이 사용하곤 함

2.무언가를 찾는데 싱글보단 빠름

3.하지만 메모리가 조금 더 많이 든다

 

 

이 강의를 벌써 3번째 넘게 보고 있는데, 이제 갑작스럽게 이해란것이 머리로 들어와버림