이중 연결 리스트

WooBuntu·2020년 8월 23일
연결리스트자료구조자바스크립트
0

자바스크립트 자료구조

목록 보기
2/8


- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)

  • 기본적으로 이중 연결 리스트는 지난 포스팅에서 다룬 단일 연결 리스트와 구조가 동일하다.

  • 다만, 각 노드가 다음 노드에 대한 포인터 뿐만 아니라 이전 노드에 대한 포인터도 갖고 있다는 점이 다르다.

  • 즉, 단일 연결 리스트에 비해 메모리를 두 배로 잡아 먹는다
    (공간 복잡도가 두배이다)

  • 공간 복잡도를 희생한 만큼 유연해지는 상충 관계가 발생한다

이중 연결 리스트의 노드는 양방향 포인터를 가진다

const Node = {
  init: function (val) {
    this.val = val;
    this.prev = null;
    this.next = null;
  },
};
// Node는 Object.create으로 생성한 위임객체로부터 동작을 위임받을 수임객체

const head = Object.create(Node);
// head는 init의 작동을 Node에 위임한 위임객체
head.init("시작 노드");

연결 리스트는 head와 tail, 그리고 length 프로퍼티를 갖는다.

const DoublyLinkedList = {
  init: function () {
    this.head = null;
    this.tail = null;
    this.length = 0;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();

push

const DoublyLinkedList = {
  // 앞 생략
  push: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.head) {
      // head가 없다는 것은 연결 리스트의 head와 tail을 초기화해주어야 한다는 것
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();

  • 단일 연결 리스트와 마찬가지로 tail에 접근해서 노드를 추가해주면 되므로 시간 복잡도는 1이다.

pop

const DoublyLinkedList = {
  // 앞 생략
  pop: function () {
    if (!this.head) {
      return;
    }

    const oldTail = this.tail;

    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      const newTail = oldTail.prev;
      newTail.next = null;
      this.tail = newTail;
      oldTail.prev = null;
    }

    this.length--;
    return oldTail;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");

  • 단일 연결 리스트가 tail바로 이전 노드를 잡기 위해 전체 순회를 돌아야 했던 반면,

  • 이중 연결 리스트는 바로 tail에 접근해서 prev포인터로 이전 노드를 잡을 수 있기 때문에 시간 복잡도가 1이다.

shift

const DoublyLinkedList = {
  // 앞 생략
  shift: function () {
    if (!this.head) {
      return;
    }

    const oldHead = this.head;
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      const newHead = oldHead.next;
      newHead.prev = null;
      this.head = newHead;
      oldHead.next = null;
    }

    this.length--;
    return oldHead;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();
list.push("우분투");
list.push("리눅스");

  • head에 접근해서 다음 노드와의 연결 고리를 끊으면 되기 때문에 시간 복잡도는 1이다.

unshift

const DoublyLinkedList = {
  // 앞 생략
  unshift: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.length++;
    return this;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();

  • head에 접근해서 새로운 노드를 추가해주면 되므로 시간 복잡도는 1이다.

Get

const DoublyLinkedList = {
  // 앞 생략
  get: function (idx) {
    if (idx < 0 || idx >= this.length) {
      return;
    }

    let currentNode, limit, command;
    const middleIndex = Math.floor((this.length - 1) / 2);

    if (idx <= middleIndex) {
      currentNode = this.head;
      limit = idx;
      command = "next";
      console.log("head부터");
    } else {
      currentNode = this.tail;
      limit = this.length - 1 - idx;
      command = "prev";
      console.log("tail부터");
    }
    for (let i = 0; i < limit; i++) {
      currentNode = currentNode[command];
    }

    return currentNode;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();
list.push(0);
list.push(1);
list.push(2);
list.push(3);
list.push(4);
list.push(5);

  • 인덱스가 head와 tail중 어디에 가깝느냐에 따라서 순회의 시작점을 달리 하기 때문에 엄밀히는 시간 복잡도가 n/2에 가깝겠으나, 시간복잡도를 계산할 때는 상수를 무시하므로 시간 복잡도는 n이다.

Set

const DoublyLinkedList = {
  // 앞 생략
  set: function (idx, val) {
    const targetNode = this.get(idx);
    if (!targetNode) {
      return;
    }
    targetNode.val = val;
    return targetNode;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();
list.push(0);
list.push(1);
list.push(2);

  • get과 같다

insert

const DoublyLinkedList = {
  // 앞 생략
  insert: function (idx, val) {
    if (idx < 0 || idx > this.length) {
      return;
    }
    if (idx == 0) {
      return this.unshift(val);
    }
    if (idx == this.length) {
      return this.push(val);
    }

    const newNode = Object.create(Node);
    newNode.init(val);

    const previousNode = this.get(idx - 1);
    // 앞선 예외처리의 결과로 여기에서 idx - 1의 범위는 다음과 같다.
    // 1 <= idx <= this.length - 1
    // 0 <= (idx - 1) <= this.length - 2
    // 따라서 previousNode는 반드시 존재할 수 밖에 없음.

    const nextNode = previousNode.next;
    // previousNode의 인덱스 범위에 1을 더한 값을 범위로 가진다.
    // 즉, 1 <= indexOfNextNode <= this.length - 1
    // 역시, nextNode도 반드시 존재한다.

    previousNode.next = newNode;
    newNode.prev = previousNode; 
    newNode.next = nextNode;
    nextNode.prev = newNode;

    this.length++;
    return this;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();
list.push(0);
list.push(1);
list.push(2);

  • 인덱스가 head와 tail중 어디에 가깝느냐에 따라 시작점을 달리한다는 것 이외에는 단일 연결 리스트와 동일하다

  • get을 재사용했기에 시간 복잡도는 n으로 간주한다.

remove

const DoublyLinkedList = {
  // 앞 생략
  remove: function (idx) {
    if (idx < 0 || idx >= this.length) {
      return;
    }
    if (idx == 0) {
      return this.shift();
    }
    if (idx == this.length - 1) {
      return this.pop();
    }

    const targetNode = this.get(idx);
    const previousNode = targetNode.prev;
    const nextNode = targetNode.next;

    previousNode.next = nextNode;
    nextNode.prev = previousNode;

    targetNode.prev = null;
    targetNode.next = null;

    this.length--;
    return targetNode;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();
list.push(0);
list.push(1);
list.push(2);
list.push(3);
list.push(4);

  • insert와 같다.

find

const DoublyLinkedList = {
  // 앞 생략
  find: function (val) {
    if (!this.head) {
      return;
    }
    let currentNode = this.head;
    for (let i = 0; i < this.length; i++) {
      if (currentNode.val == val) {
        return i.toString();
      }
      currentNode = currentNode.next;
    }
    return;
  },
};

const list = Object.create(DoublyLinkedList);
list.init();
list.push("우분투");
list.push("레드햇");
list.push("CentOS");

  • 단일 연결 리스트의 find와 동일하다.

removeByValue

const DoublyLinkedList = {
  // 앞 생략
  removeByValue: function (val) {
    const indexOfTargetNode = this.find(val);
    if (isNaN(parseInt(indexOfTargetNode))) {
      return;
    }

    return this.remove(indexOfTargetNode);
  },
};

const list = Object.create(DoublyLinkedList);
list.init();

list.push("우분투");
list.push("레드햇");
list.push("CentOS");
list.push("리눅스");
list.push("자바스크립트");

  • find와 동일하다.

removeDuplicate

const DoublyLinkedList = {
  // 앞 생략
  removeDuplicate: function () {
    if (!this.head) {
      return this;
    }

    let currentNode = this.head;
    const hashTable = {};
    let count = 0;

    while (true) {
      let nextNode = currentNode.next;
      // 밑에서 remove할 경우 currentNode의 next참조가 사라지기 때문에
      // 해당 참조를 보존할 목적
      
      if (!hashTable.hasOwnProperty(currentNode.val)) {
        hashTable[currentNode.val] = 1;
      } else {
        this.remove(count);
        count--;
      }

      if (nextNode) {
        currentNode = nextNode;
        count++;
      } else {
        return this;
      }
    }
  },
};

const list = Object.create(DoublyLinkedList);
list.init();

list.push("우분투");
list.push("리눅스");
list.push("우분투");
list.push("CentOS");
list.push("리눅스");
list.push("우분투");

  • 역시 find와 동일하다.

전체 코드

const Node = {
  init: function (val) {
    this.val = val;
    this.prev = null;
    this.next = null;
  },
};

const DoublyLinkedList = {
  init: function () {
    this.head = null;
    this.tail = null;
    this.length = 0;
  },
  push: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.head) {
      // head가 없다는 것은 연결 리스트의 head와 tail을 초기화해주어야 한다는 것
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  },
  pop: function () {
    if (!this.head) {
      return;
    }

    const oldTail = this.tail;

    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      const newTail = oldTail.prev;
      newTail.next = null;
      this.tail = newTail;
      oldTail.prev = null;
    }

    this.length--;
    return oldTail;
  },
  shift: function () {
    if (!this.head) {
      return;
    }

    const oldHead = this.head;
    if (this.length == 1) {
      this.head = null;
      this.tail = null;
    } else {
      const newHead = oldHead.next;
      newHead.prev = null;
      this.head = newHead;
      oldHead.next = null;
    }

    this.length--;
    return oldHead;
  },
  unshift: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.length++;
    return this;
  },
  get: function (idx) {
    if (idx < 0 || idx >= this.length) {
      return;
    }

    let currentNode, limit, command;
    const middleIndex = Math.floor((this.length - 1) / 2);

    if (idx <= middleIndex) {
      currentNode = this.head;
      limit = idx;
      command = "next";
      console.log("head부터");
    } else {
      currentNode = this.tail;
      limit = this.length - 1 - idx;
      command = "prev";
      console.log("tail부터");
    }
    for (let i = 0; i < limit; i++) {
      currentNode = currentNode[command];
    }

    return currentNode;
  },
  set: function (idx, val) {
    const targetNode = this.get(idx);
    if (!targetNode) {
      return;
    }
    targetNode.val = val;
    return targetNode;
  },
  insert: function (idx, val) {
    if (idx < 0 || idx > this.length) {
      return;
    }
    if (idx == 0) {
      return this.unshift(val);
    }
    if (idx == this.length) {
      return this.push(val);
    }

    const newNode = Object.create(Node);
    newNode.init(val);

    const previousNode = this.get(idx - 1);
    // 앞선 예외처리의 결과로 여기에서 idx - 1의 범위는 다음과 같다.
    // 1 <= idx <= this.length - 1
    // 0 <= (idx - 1) <= this.length - 2
    // 따라서 previousNode는 반드시 존재할 수 밖에 없음.

    const nextNode = previousNode.next;
    // previousNode의 인덱스 범위에 1을 더한 값을 범위로 가진다.
    // 즉, 1 <= indexOfNextNode <= this.length - 1
    // 역시, nextNode도 반드시 존재한다.

    previousNode.next = newNode;
    newNode.prev = previousNode;
    newNode.next = nextNode;
    nextNode.prev = newNode;

    this.length++;
    return this;
  },
  remove: function (idx) {
    if (idx < 0 || idx >= this.length) {
      return;
    }
    if (idx == 0) {
      return this.shift();
    }
    if (idx == this.length - 1) {
      return this.pop();
    }

    const targetNode = this.get(idx);
    const previousNode = targetNode.prev;
    const nextNode = targetNode.next;

    previousNode.next = nextNode;
    nextNode.prev = previousNode;

    targetNode.prev = null;
    targetNode.next = null;

    this.length--;
    return targetNode;
  },
  find: function (val) {
    if (!this.head) {
      return;
    }
    let currentNode = this.head;
    for (let i = 0; i < this.length; i++) {
      if (currentNode.val == val) {
        return i.toString();
      }
      currentNode = currentNode.next;
    }
    return;
  },
  removeByValue: function (val) {
    const indexOfTargetNode = this.find(val);
    if (isNaN(parseInt(indexOfTargetNode))) {
      return;
    }

    return this.remove(indexOfTargetNode);
  },
  removeDuplicate: function () {
    if (!this.head) {
      return this;
    }

    let currentNode = this.head;
    const hashTable = {};
    let count = 0;

    while (true) {
      let nextNode = currentNode.next;
      // 밑에서 remove할 경우 currentNode의 next참조가 사라지기 때문에
      // 해당 참조를 보존할 목적

      if (!hashTable.hasOwnProperty(currentNode.val)) {
        hashTable[currentNode.val] = 1;
      } else {
        this.remove(count);
        count--;
      }

      if (nextNode) {
        currentNode = nextNode;
        count++;
      } else {
        return this;
      }
    }
  },
};

const list = Object.create(DoublyLinkedList);
list.init();
  • 이중 연결 리스트가 단일 연결 리스트와 비교해서 가장 크게 차이를 보이는 것은, pop의 시간 복잡도가 n이 아닌 1이라는 것이다.
profile
WooBuntu
이전 포스트

단일 연결 리스트

다음 포스트

스택/큐

0개의 댓글