[Udemy 데이터구조] 이중연결리스트

1. 단일 연결리스트와 차이점

    a. Node에 next외에도 prev 프로퍼티가 있다.
    b. 장점
        i. pop 메서드가 훨씬 효율적으로 이루어진다.
        ii. reverse가 쉽다.
    c. 단점
        i. 메모리가 단일 연결 리스트보다 더 든다.

2. 이중연결리스트의 Big O

    a. 삽입 : O(1)
    b. 제거 : O(1)
    c. 검색 : O(N)
    d. 접근 : O(N)

3. Node 클래스, 이중연결리스트 클래스 생성

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;
  }
  }

4. 이중연결리스트 클래스의 메서드

1) Push

    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) Pop

  pop() {
    if (this.length === 0) return undefined;
    let poppedNode = this.tail;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      poppedNode.prev = null;
      this.tail.next = null;
    }
    this.length--;
    return poppedNode;
  }

3) Shift

  shift() {
    if (this.length === 0) return undefined;
    let shiftedHead = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = shiftedHead.next;
      this.head.prev = null;
      shiftedHead.next = null;
    }
    this.length--;
    return shiftedHead;
  }

4) Unshift

  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;
  }

5) Get

• 특정 index의 Node를 반환한다.
• 이중연결리스트는 tail부터 출발할 수 있기 때문에 index가 꼬리(tail)에 가깝다면
  탐색을 꼬리에서 시작하고, head에 가깝다면 head에서 시작한다.

  get(index) {
  /* 의사코드
  1. index가 length보다 같거나 클 경우, 음수일 경우 null 반환
  2. length /2 보다 작은지 큰지 확인 */
  if (index >= this.length || index < 0) return null;
  let targetNode = this.head;
  if (index <= this.length / 2) {
    for (let i = 0; i < index; i++) {
      targetNode = targetNode.next;
    }
  } else {
    targetNode = this.tail;
    for (let i = this.length - 1; i > index; i--) {
      targetNode = targetNode.prev;
    }
  }
  return targetNode;
  }

  6) Set
• 특정 노드의 value를 변경하는 메서드.

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

  7) Insert
• unshift는 불리언값을 return하지 않기 때문에 따로 불리언값 반환을 위한 처리를 해줘야 한다.

  insert(index, val) {
  /* index가 length보다 크거나, 음수면 false반환(get으로 얻은 변수로
      조건문 작성하면 될 듯) */
  if (index < 0 || index > this.length) return false;
  if (index === 0) {
    // return !!this.unshift(val)도 가능하다
    this.unshift(val);
    return true;
  } else if (index === this.length) {
    this.push(val);
    return true;
  }
  let targetNode = this.get(index - 1);
  let newNode = new Node(val);
  let nextNode = targetNode.next;
  targetNode.next = newNode;
  newNode.next = nextNode;
  newNode.prev = targetNode;
  nextNode.prev = newNode;
  this.length++;
  return true;
  }

  8) Remove

  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 targetNode = this.get(index);
  let prevNode = targetNode.prev;
  let nextNode = targetNode.next;
  prevNode.next = nextNode;
  nextNode.prev = prevNode;
  targetNode.prev = null;
  targetNode.next = null;
  this.length--;
  return targetNode;
  }