12. Doubly Linked Lists.md

Doubly Linked Lists

목표

• Doubly Linked List를 만듭니다.
• Singly Linked List와 비교합니다.
• 기본 연산 메소드를 구현합니다.

왜 Doubly 일까

• Singly Linked Lists 처럼 다음 노드를 point 할 뿐만 아니러 이전 노드도 point 합니다.

Singly Linked Lists 와 비교

• previous 노드를 가르키는 point가 있음으로 더 효율적입니다.
• But, More memory === More Flexibility 두개는 항상 tradeoff 관계입니다.

구현

기본 세팅

1. Node

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

2. DoublyLinkedLists

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

1. Pushing

노드 끝에 새로운 노드를 추가하는 메소드입니다.

의사코드

1. 새 노드를 만듭니다.
2. 기존 head가 없으면 새로 생성한 노드를 head와 tail로 지정합니다.
3. 기존에 노드가 있으면 tail의 next 프로퍼티를 새 노드로 지정합니다.
4. 새 노드의 이전 point를 기존 tail로 지정합니다.
5. 길이를 증가시킵니다.
6. Doubly Linked Lists를 return 합니다.

구현

  push(val) {
    let newNode = new Node(val);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

2. Popping

마지막 노드를 제거합니다.

의사코드

1. head가 없으면 undefined를 return 합니다.
2. 현재 tail을 변수에 저장하고 나중에 return 합니다.
3. 만약에 길이가 1이면 head와 tail을 null로 설정합니다.
4. tail을 삭제한 노드의 이전 노드로 설정합니다.
5. 새 tail의 next를 null로 설정합니다.

구현

  pop() {
    if (!this.head) return undefined;
    let poppedNode = this.tail;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = poppedNode.prev;
      this.tail.next = null;
      // 연결을 완전히 끊기
      poppedNode.prev = null;
    }
    this.length--;
    return poppedNode;
  }

3. Shift

맨 앞의 노드를 제거합니다.

의사코드

1. 길이가 0이면 undefined를 return 합니다.
2. 현재 head 프로퍼티를 변수에 저장합니다. (사용함)
3. if length === 1 이면
   • head = null
   • tail = null
4. 새 head를 old head의 next로 설저합니다.
5. 새 head의 prev를 null로 설정합니다.
6. old head의 next를 null로 설정합니다.
7. 길이를 1 감소합니다.

구현

  shift() {
    if (this.length === 0) return undefined;
    let 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;
  }

4. Unshifting

맨 앞에 새 노드를 추가합니다.

의사코드

1. 새 노드를 만듭니다.
2. if length === 0 이면
   • 새 노드를 head와 tail로 지정합니다.
3. else
   • 이전 head의 prev를 새 노드로 설정합니다.
   • 새 노드의 next 프로퍼티를 기존 head로 설정합니다.
   • head를 새 노드로 설정합니다.
4. 길이를 증가시킵니다.
5. return list

구현

  unshift(val) {
    let newNode = new Node(val);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }

4. GET

index를 기반으로 노드에 접근하는 메소드 입니다. Singly Linked Lists와 다르게 이전 값에 접근 할 수 있으므로 index가 끝과 가까우면 tail에서 prev로 접근합니다.

의사코드

1. 만약 index가 0보다 작거나 length와 같거나 크면 null을 return 합니다.
2. if (index <= length / 2 ) 이면
   • head에서 시작해서 중간까지 Loop합니다.
   • 찾은 노드를 return 합니다.
3. else 이면
   • tail에서 시작해서 중간까지 Loop합니다.
   • 찾은 노드를 return 합니다.

구현

  get(index) {
    if (index < 0 || index >= this.length) return null;
    let getNode = this.head;
    if (index <= this.length / 2) {
      for (let i = 0; i < index; i++) {
        getNode = getNode.next;
      }
      return getNode;
    } else {
      getNode = this.tail;
      for (let i = this.length - 1; i > index; i--) {
        getNode = getNode.prev;
      }
      return getNode;
    }
  }

5. SET

index와 값을 받아 특정 위치의 값을 변경하는 메소드 입니다.

의사코드

1. get 메소드를 이용해 특정 index에 있는 노드를 찾습니다.
2. if get 메소드가 노드를 찾으면
   • 값을 새로 지정해줍니다.
   • return true
3. else 특정 노드를 못찾으면
   • return false를 합니다.

구현

set(index, val) {
    let foundNode = this.get(index);
    if (foundNode != null) {
      foundNode.val = val;
      return true;
    }
    return false;
  }

6. Insert

특정 위치에 새 노드를 추가하는 메소드 입니다.

의사코드

1. index가 0보다 작거나 길이보다 크면 return false를 합니다.
2. 만약 index가 0이면 unshift를 합니다.
3. 만약 index가 길이와 같다면 push를 이용합니다.
4. get 메소드를 사용해서 index-1에 접근합니다.
5. next, prev 프로퍼티를 설정합니다.
6. 길이를 1증가시킵니다.
7. return true

구현

  insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === 0) return !!this.unshift(val);
    if (index === this.length) return !!this.push(val);

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

    (beforeNode.next = newNode), (newNode.prev = beforeNode);
    (newNode.next = afterNode), (afterNode.prev = newNode);
    this.length++;
    return true;
  }

7. Remove

특정 위치의 노드를 제거하는 메소드 입니다.

의사코드

1. if index < 0 이거나 index >= this.length이면 return undefined를 합니다.
2. if index === 0 이면 shift를 사용합니다.
3. if index === this.length - 1 이면 pop을 사용합니다.
4. get메소드를 사용해서 삭제할 node를 찾습니다.
5. 앞뒤 노드를 이어줍니다.
6. 삭제한 node의 prev, next를 null 로 바꿉니다.
7. 길이를 1 감소시킵니다.
8. return true

구현

  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();
    let removedNode = this.get(index);
    removedNode.prev.next = removedNode.next;
    removedNode.next.prev = removedNode.prev;
    removedNode.next = null;
    removedNode.prev = null;
    this.length--;
    return removedNode;
  }

8. Reverse

순서를 뒤집는 메소드 입니다.

구현

  reverse() {
    if (this.length === 0) return undefined;
    this.head = this.tail;
    let current = this.head;
    for (let i = 0; i < this.length; i++) {
      let temp = current.next;
      current.next = current.prev;
      current.prev = temp;
      this.tail = current;
      current = current.next;
    }

    return this;
  }

Big O

• Insertion - O(1)
• Removal - O(1)
• Searching - O(N)
• Access - O(N)

SLL vs DLL

• 두개는 동일하지만 단지 previous를 pointer의 유무만 다릅니다.
• previous pointer를 이용해서 searching이 더 빠릅니다.
• 그러나 메모리를 더 사용하기는 합니다.