ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • Section20 - 이중 연결 리스트
    자료구조 & 알고리즘 & CS + 2022. 7. 21. 01:12
    728x90
    반응형


    [이중 연결 리스트]

     

    싱글 리스트와 거의 비슷함

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

     

    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번째 넘게 보고 있는데, 이제 갑작스럽게 이해란것이 머리로 들어와버림

    반응형

    '자료구조 & 알고리즘 & CS +' 카테고리의 다른 글

    Section22 - 이진 검색 트리  (0) 2022.07.26
    Section21 - 스택 & 큐  (0) 2022.07.23
    Section19 - 단일 연결 리스트  (0) 2022.07.20
    Section18 - 자료 구조 소개  (0) 2022.07.18

    댓글

Designed by Tistory.