Doubly Linked List with JS

• 단일 연결 리스트 
• 이중 연결 리스트
• 스택 & 큐 (배열로 하는 방법은 숙지했음! linked list로 구현해 보기)
• 이진 검색 트리
• 트리 순회
• 이진 힙
• 해시 테이블 (사용해 봤지만 복습)
• 그래프, 그래프 순회
• 다익스트라 알고리즘
• 동적 프로그래밍

 

doubly linked lists

이중 연결리스트를 왜 사용하는지 몰랐는데.. 최근에 풀었던 덱 문제를 풀면서 시간복잡도가 커짐을 느끼고 이중 연결리스트를 사용해서 문제를 해결했던 기억이 있다.

이중 연결리스트는 일반 연결리스트와 달리 prev, next가 생긴 것이다. 조금 더 복잡해졌지만 그만큼 효율이 좋은 거 같다. 

---

Class Setting

기본 세팅은 Linked List와 비슷하지만 추가되는 것이 있다.

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

Linked List와 비슷하게 push, pop,shift, unshift를 다룰 것이다.

---

Push

연결리스트를 이해할 때 그림을 그리고 직관적인 표현이 필요했는데 제일 만족스러운 조직도이다.

push는 새로운 node가 들어오면 

1. tail의 next를 새로운 노드에 연결

2. 새로운 노드의 prev 를 tail에 연결

3. tail을 새로운 노드로 가리킴

 push(val) {
    var 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;
  }

항상 길이가 0일때 초기화와  push 했을 때 길이를 추가해 준다. 

---

pop

맨 뒤의 값을 제거 하는 것이다.

1. tail을 전 노드를 가리킨다.

2. tail의 next를 null로 바꾼다.

3. 제거할 노드의 prev를 null로 해서 없앤다.

 pop() {
    if (!this.head) return undefined;
    var 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;
  }

---

shift 

 

맨 앞의 원소를 제거하는 것이다.

1. head를 head를 저장한 객체의 next로 연결한다.

2. 바뀐 head의 prev를 null로 바꾼다.

3. 따로 저장한 객체의 노드의 next를 null로 바꿔서 제거한다.

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

맨 앞에 원소 넣기

1. 기존 head의 prev를 새로운 Node에 연결한다.

2. 연결된 새로운 Node의 next를 아직 바꾸지 않은 head로 연결한다.

3. 연결이 됐다면 현재 head를 새로운 Node로 가리킨다.

---

set, get, insert는 간단해서 따로 안 다룰 예정(사실 조금 귀찮음..)

최종 코드

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) {
    var 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;
  }
  pop() {
    if (!this.head) return undefined;
    var 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;
  }
  shift() {
    if (this.length === 0) return undefined;
    var 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) {
    var 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;
  }
  get(index) {
    if (index < 0 || index >= this.length) return null;
    var count, current;
    if (index <= this.length / 2) {
      count = 0;
      current = this.head;
      while (count !== index) {
        current = current.next;
        count++;
      }
    } else {
      count = this.length - 1;
      current = this.tail;
      while (count !== index) {
        current = current.prev;
        count--;
      }
    }
    return current;
  }
  set(index, val) {
    var foundNode = this.get(index);
    if (foundNode != null) {
      foundNode.val = val;
      return true;
    }
    return false;
  }
  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);

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

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

var list = new DoublyLinkedList();
list.push("Harry");
list.push("Ron");
list.push("Hermione");
console.log(list);

list.pop();
console.log(list);

 

 

참고자료

JavaScript 알고리즘 & 자료구조 마스터 클래스 :

https://www.udemy.com/course/best-javascript-data-structures

Insertion in a Doubly Linked List : 

https://www.geeksforgeeks.org/introduction-and-insertion-in-a-doubly-linked-list/

Insertion in a Doubly Linked List - GeeksforGeeks

Doubly Linked List series : 

https://dev.to/tartope/doubly-linked-list-series-creating-shift-and-unshift-methods-with-javascript-2mmd

Doubly Linked List Series: Creating shift() and unshift() methods with JavaScript