단일 연결 리스트

WooBuntu·2020년 8월 23일
1


- JavaScript Algorithms and Data Structures Masterclass(Udemy Course)

  • '자바스크립트로 하는 자료 구조와 알고리즘'은 전통적인(?) prototype을 통해 자료구조를 구현하였고, 'JavaScript Algorithms and Data Structures Masterclass'에서는 ES6의 class를 통해 자료구조를 구현하였다.

  • 개인적으로는 YDKJS에서 소개된 '위임' 디자인 패턴이 매우 인상 깊었기 때문에, 이 시리즈에서 자료구조의 구현은 모두 이 '위임'패턴을 적용해보려고 한다.

연결 리스트

  • 각 노드가 다른 노드를 가리키는 자료 구조로 시작 노드는 head, 끝 노드는 tail이라 부른다.

  • 각 노드는 값과 다른 노드(혹은 null)를 가리키는 포인터를 갖는다.

  • 배열은 인덱스가 있지만, 연결 리스트는 인덱스가 없다.
    따라서 연결 리스트의 특정 원소에 접근하려면 head(혹은 tail)부터 시작하여 하나 하나 타고 올라가는 수밖에 없다.

  • 그러나 배열에 비해서 삽입과 삭제에 있어서 효율적이다.

  • 배열 같은 경우 이미 인덱스가 정해져있기 때문에 삽입과 삭제로 인덱스의 재정렬이 필요한 경우가 많다.
    (사실상 연결 리스트를 쓰는 이유)

연결 리스트는 노드로 구성되어 있다.

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

const head = Object.create(Node);
// head는 init의 작동을 Node에 위임한 위임객체
head.init("시작 노드");
  • 클래스형 패턴에서는 new로 생성과 초기화를 한꺼번에 하는 반면, 위임 패턴에서는 이렇듯 생성과 초기화가 분리되어 있다.

  • 관점에 따라 이게 더 귀찮다고 생각할 수도 있겠지만, 생성과 초기화를 다른 시점에 수행해야 할 경우도 있기 때문에 위임 패턴이 더 유연하다고 할 수 있다.

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

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

const list = Object.create(SinglyLinkedList);
list.init();
  • 연결 리스트는 시작 노드와 끝 노드를 갖는다는 것의 구현이다.

push

const SinglyLinkedList = {
  // 앞 생략
  push: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.head) {
      // head가 없다는 것은 연결 리스트에 노드가 하나도 없다는 것이므로,
      // 새로 생긴 노드는 head이자 tail이 된다.
      this.head = newNode;
      this.tail = newNode;
    } else {
      // tail의 next에 새로운 노드를 설정해주고,
      // 그 노드를 새로 tail로 설정해준다.
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  },
};

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

list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");

  • tail을 바로 찾으면 되니 시간 복잡도는 1이다.

  • Array.prototype.push의 경우 마찬가지로 시간 복잡도는 1이다.

pop

const SinglyLinkedList = {
  // 앞 생략
  pop: function () {
    if (!this.head) {
      // head가 없다는 것은 더 이상 pop할 노드가 없다는 것
      return;
    }
    let nodeToBePopped;
    if (this.length == 1) {
      // 연결 리스트의 길이가 1이라는 것은 head와 tail을 null로 초기화해야 한다는 것
      nodeToBePopped = this.head;
      this.head = null;
      this.tail = null;
    } else {
      let previousNode = this.head;
      let currentNode = previousNode.next;
      while (currentNode.next) {
        currentNode = currentNode.next;
        previousNode = previousNode.next;
      }
      nodeToBePopped = currentNode;
      previousNode.next = null;
      this.tail = previousNode;
    }
    this.length--;
    return nodeToBePopped;
  },
};

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

list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");

  • previousNode를 찾기 위해서라도 순회를 돌아야하므로 시간 복잡도는 n이다.

  • Array.prototype.pop의 경우 마지막 인덱스에 접근만 하면 되기 때문에 시간 복잡도는 1이다.

shift

const SinglyLinkedList = {
  // 앞 생략
  shift: function () {
    if (!this.head) {
      // head가 없다는 것은 더 이상 shift할 노드가 없다는 것
      return;
    }

    const nodeToBeShifted = this.head;
    if (this.length == 1) {
      // 연결 리스트의 길이가 1이라는 것은 head와 tail을 null로 초기화해야 한다는 것
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
    }
    this.length--;
    nodeToBeShifted.next = null;
    return nodeToBeShifted;
  },
};

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

list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");

  • head를 바로 찾으면 되니 시간 복잡도는 1이다.

  • Array.prototype.shift의 경우 모든 원소들의 인덱스를 하나씩 앞으로 당겨야 하므로 시간 복잡도가 n이다.

unshift

const SinglyLinkedList = {
  // 앞 생략
  unshift: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.head) {
      // head가 없다는 것은 unshift한 노드가 head이자 tail이 되어야 한다는 것
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  },
};

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

  • head를 바로 찾으면 되니 시간 복잡도는 1이다.

  • Array.prototype.unshift의 경우 모든 원소들의 인덱스를 하나씩 뒤로 밀어내야 하므로 시간 복잡도가 n이다.

Get

const SinglyLinkedList = {
  // 앞 생략
  get: function (idx) {
    if (idx < 0 || idx >= this.length) {
      return;
    }
    let currentNode = this.head;
    for (let i = 0; i < idx; i++) {
      currentNode = currentNode.next;
    }
    return currentNode;
  },
};

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

list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");

  • 최선의 경우는 인덱스가 0인 경우로 시간 복잡도가 1이고,

  • 최악의 경우는 인덱스가 (this.length - 1)인 경우로 시간 복잡도가 n까지 올라간다.

  • 일반적으로 시간 복잡도를 n으로 간주한다.

  • Array의 경우 인덱스로 원소에 접근하는 것은 원소의 위치에 관계없이 시간 복잡도가 1이다.

Set

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

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

list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");

  • get과 동일하다.

insert

const SinglyLinkedList = {
  // 앞 생략
  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 oldNode = previousNode.next;
    // previousNode의 인덱스 범위에 1을 더한 값을 범위로 가진다.
    // 즉, 1 <= indexOfOldNode <= this.length - 1
    // 역시, oldNode도 반드시 존재한다.

    newNode.next = oldNode;

    previousNode.next = newNode;

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

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

list.push("우분투");
list.push("리눅스");
list.push("닉값하고 싶다");

  • get의 시간 복잡도와 같다 (1 <= O(n) <= n)

remove

const SinglyLinkedList = {
  // 앞 생략
  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 previousNode = this.get(idx - 1);
    // 앞선 예외처리의 결과로 인덱스의 범위는 아래와 같다.
    // 1 <= idx <= this.length - 2
    // 0 <= (idx - 1) <= this.length - 3
    // 따라서 newTail은 반드시 존재한다.

    const nodeToBeRemoved = previousNode.next;
    // 1 <= indexOfNodeToBeRemoved <= this.length - 2

    previousNode.next = nodeToBeRemoved.next;

    this.length--;
    nodeToBeRemoved.next = null;
    return nodeToBeRemoved;
  },
};

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

list.push("우분투");
list.push("리눅스");
list.push("CentOS");
list.push("레드햇");
list.push("닉값하고 싶다");

  • get의 시간 복잡도와 같다 (1 <= O(n) <= n)

reverse

const SinglyLinkedList = {
  // 앞 생략
  reverse: function () {
    if (!this.head) {
      return this;
    }
    let currentNode = this.head;
    while (currentNode.next) {
      const nextNode = currentNode.next;
      currentNode.next = nextNode.next;
      nextNode.next = this.head;
      this.head = nextNode;
    }
    this.tail = currentNode;
    return this;
  },
};

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

list.push("우분투");
list.push("리눅스");
list.push("레드햇");

  • 전체 노드를 순회해야 하므로 시간 복잡도는 n이다.

find

const SinglyLinkedList = {
  // 앞 생략
  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(SinglyLinkedList);
list.init();

list.push("우분투");
list.push("리눅스");
list.push("레드햇");

  • 최선의 경우는 찾고자 하는 노드가 head에 해당하는 경우로 시간 복잡도가 1이고,

  • 최악의 경우는 찾고자 하는 노드가 tail에 해당하는 경우로 시간 복잡도가 n까지 올라간다.

  • 일반적으로 시간 복잡도를 n으로 간주한다.

  • Array.prototype.indexOf가 이와 유사하지 않을까 추측한다
    (내부 코드를 모르니...)

removeByValue

const SinglyLinkedList = {
  // 앞 생략
  removeByValue: function (val) {
    if (!this.head) {
      return;
    }
    const indexOfTarget = parseInt(this.find(val));
    if (isNaN(indexOfTarget)) {
      return;
    }

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

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

list.push("우분투");
list.push("리눅스");
list.push("CentOS");
list.push("레드햇");
list.push("닉값하고 싶다");

  • find와 같다.

removeDuplicate

const SinglyLinkedList = {
  // 앞 생략
  removeDuplicate: function () {
    if (!this.head) {
      return this;
    }
    const hashTable = {};
    let currentNode = this.head;
    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(SinglyLinkedList);
list.init();

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

  • 전체 노드를 순회해야 하므로 시간 복잡도는 n이다.

전체 코드

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

const SinglyLinkedList = {
  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 {
      // tail의 next에 새로운 노드를 설정해주고,
      // 그 노드를 새로 tail로 설정해준다.
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  },
  pop: function () {
    if (!this.head) {
      // head가 없다는 것은 더 이상 pop할 노드가 없다는 것
      return;
    }
    let nodeToBePopped;
    if (this.length == 1) {
      // 연결 리스트의 길이가 1이라는 것은 head와 tail을 null로 초기화해야 한다는 것
      nodeToBePopped = this.head;
      this.head = null;
      this.tail = null;
    } else {
      let previousNode = this.head;
      let currentNode = previousNode.next;
      while (currentNode.next) {
        currentNode = currentNode.next;
        previousNode = previousNode.next;
      }
      nodeToBePopped = currentNode;
      previousNode.next = null;
      this.tail = previousNode;
    }
    this.length--;
    return nodeToBePopped;
  },
  shift: function () {
    if (!this.head) {
      // head가 없다는 것은 더 이상 shift할 노드가 없다는 것
      return;
    }

    const nodeToBeShifted = this.head;
    if (this.length == 1) {
      // 연결 리스트의 길이가 1이라는 것은 head와 tail을 null로 초기화해야 한다는 것
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
    }
    this.length--;
    nodeToBeShifted.next = null;
    return nodeToBeShifted;
  },
  unshift: function (val) {
    const newNode = Object.create(Node);
    newNode.init(val);
    if (!this.head) {
      // head가 없다는 것은 unshift한 노드가 head이자 tail이 되어야 한다는 것
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  },
  get: function (idx) {
    if (idx < 0 || idx >= this.length) {
      return;
    }
    let currentNode = this.head;
    for (let i = 0; i < idx; i++) {
      currentNode = currentNode.next;
    }
    return currentNode;
  },
  set: function (idx, val) {
    const nodeToChangeValue = this.get(idx);
    if (!nodeToChangeValue) {
      return;
    }
    nodeToChangeValue.val = val;
    return nodeToChangeValue;
  },
  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 oldNode = previousNode.next;
    // previousNode의 인덱스 범위에 1을 더한 값을 범위로 가진다.
    // 즉, 1 <= indexOfOldNode <= this.length - 1
    // 역시, oldNode도 반드시 존재한다.

    newNode.next = oldNode;

    previousNode.next = 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 previousNode = this.get(idx - 1);
    // 앞선 예외처리의 결과로 인덱스의 범위는 아래와 같다.
    // 1 <= idx <= this.length - 2
    // 0 <= (idx - 1) <= this.length - 3
    // 따라서 newTail은 반드시 존재한다.

    const nodeToBeRemoved = previousNode.next;
    // 1 <= indexOfNodeToBeRemoved <= this.length - 2

    previousNode.next = nodeToBeRemoved.next;

    this.length--;
    nodeToBeRemoved.next = null;
    return nodeToBeRemoved;
  },
  reverse: function () {
    if (!this.head) {
      return this;
    }
    let currentNode = this.head;
    while (currentNode.next) {
      const nextNode = currentNode.next;
      currentNode.next = nextNode.next;
      nextNode.next = this.head;
      this.head = nextNode;
    }
    this.tail = currentNode;
    return this;
  },
  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) {
    if (!this.head) {
      return;
    }
    const indexOfTarget = parseInt(this.find(val));
    if (isNaN(indexOfTarget)) {
      return;
    }

    return this.remove(indexOfTarget);
  },
  removeDuplicate: function () {
    if (!this.head) {
      return this;
    }
    const hashTable = {};
    let currentNode = this.head;
    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(SinglyLinkedList);
list.init();

0개의 댓글