JavaScript 이중 연결 리스트

이중 연결 리스트 (Doubly Linked List)

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

 이중 연결 리스트는 단일 연결 리스트와는 다르게 다음 노드를 가리키는 포인터와 이전 노드를 가리키는 포인터를 갖고 있다. 따라서 단일 연결 리스트보다는 자료 구조의 크기가 조금 더 크다.

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }
}

 이중 연결 리스트또한 head, tail 포인터를 갖는다. 생성과 동시에 바로 null로 초기화 된다.
아래에 있는 함수들은 모두 이중 연결 리스트 클래스 내부에 있는 함수들이다.
이번에는 바로 prototype을 적용해서 구현했다.

find(targetValue)

DoublyLinkedList.prototype.find = function (targetValue) {
  let currNode = this.head;
  let findNode = null;
  
  while (currNode !== null) {
    if (currNode.value === targetValue) {
      findNode = currNode;
      break;
    }
    currNode = currNode.next;
  }
  return findNode;
};

 단일 연결 리스트와 마찬가지로 특정 값이 존재하지 않을 경우 null을 반환한다. 또한 탐색 시간을 줄이기 위해서 특정 값을 갖는 노드를 찾을 경우 탐색 루프를 바로 종료한다.

실질적으로 이렇게 한다 해도 마지막에 있는 노드를 찾는다면 탐색시간은 길어지기 때문에 시간 복잡도가 줄어들지는 않는다.

append(newValue)

DoublyLinkedList.prototype.append = function (newValue) {
  const newNode = new Node(newValue); 
  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
    newNode.prev = newNode;
    newNode.next = newNode;
  } else {
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.count += 1;
};

 이중 연결 리스트는 단일 연결 리스트와 달리 이전 노드를 가리키는 포인터와 다음 노드를 가리키는 포인터를 관리해야 하기 때문에 조금 복잡하다. this.head가 null이라는 것은 비어있는 노드에 첫 번째로 추가한다는 의미임으로 head와 tail이 모두 newNode를 가리키고 newNode의 prev와 next는 모두 자기 자신이 된다.

 첫 번째 추가하는 노드가 아닐 경우 새로운 노드의 이전 노드는 현재 tail노드로 연결시키고 현재 tail노드의 다음으로 새로운 노드를 연결 시킨다. 그리고 tail 포인터를 이동시킨다.

insert(targetValue, newValue)

DoublyLinkedList.prototype.insert = function(targetValue, newValue) {
  const targetNode = this.find(targetValue);
  if (targetNode === null) {
    console.log("insert Fail. can't find target node.");
  } else {
    const newNode = new Node(newValue);
    newNode.next = targetNode.next;
    newNode.prev = targetNode;
    targetNode.next = newNode;
    this.count += 1;
  }
};

 find함수를 사용해서 타겟 값을 갖는 노드가 있는지 탐색한다. 타겟 노드가 있을 경우 새로운 노드를 생성하고 새로운 노드의 다음 노드는 타겟 노드의 다음으로 연결시킨다. 그리고 새로운 노드의 이전 노드를 타겟 노드로 연결시킨다. 마지막으로 타겟 노드의 다음 노드를 새로운 노드로 연결시킨다.

remove(targetValue)

DoublyLinkedList.prototype.remove = function (targetValue) {
  if (this.find(targetValue) === null) {
    console.log("remove faill...");
    return;
  }

  let prevNode = this.head;

  if (prevNode.value === targetValue) {
    this.head = this.head.next;
    this.head.next.prev = null;
    this.count -= 1;
  } else {
    while (prevNode.next.value !== targetValue) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      if (prevNode.next.next === null) {
        prevNode.next = null;
      } else {
        prevNode.next = prevNode.next.next;
        prevNode.next.prev = prevNode;
      }
      this.count -= 1;
    }
  }
};

 find함수를 사용해서 타겟 값을 갖는 노드를 찾는다. 여기서는 노드를 찾지 못할경우 return을 사용해서 함수를 바로 종료하도록 만들었다. 삭제하려는 노드가 첫 번째일 경우 리스트의 head 포인터를 두 번째 노드로 이동시키고 두 번째 노드의 prev 포인터를 null로 만든다.

 삭제하려는 노드가 첫 번째 노드가 아닐 경우 탐색을 시작한다. 탐색하려는 노드는 삭제하려는 노드의 이전 노드를 의미한다. 이중 연결 리스트에서는 삭제하려는 노드가 마지막일 경우 마지막 전 노드의 다음 노드를 null로 만들어 주면 된다.

 이제 삭제하려는 노드가 첫 번째 노드도 아니고 마지막 노드도 아닐 경우 이전 노드의 다음 노드를 삭제하려는 노드의 다음 노드로 연결한다. 그렇게 되면 이전 노드의 다음 노드는 삭제할 노드의 다음 노드가 되기 때문에 이전 노드의 다음 노드의 prev는 이전 노드로 설정한다.

Size()

DoublyLinkedList.prototype.size = function () {
  console.log(this.count);
}

노드를 추가하거나 삭제할 때 count 값을 변화시켜서 size 함수를 호출하면 현재 리스트의 사이즈를 리턴한다.

완성본

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }
}
DoublyLinkedList.prototype.find = function (targetValue) {
  let currNode = this.head;
  let findNode = null;
  while (currNode !== null) {
    if (currNode.value === targetValue) {
      findNode = currNode;
      break;
    }
    currNode = currNode.next;
  }

  return findNode;
};

DoublyLinkedList.prototype.append = function (newValue) {
  const newNode = new Node(newValue);
  if (this.head === null) {
    newNode.prev = newNode;
    newNode.next = newNode;
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.count += 1;
};

DoublyLinkedList.prototype.insert = function (targetValue, newValue) {
  const targetNode = this.find(targetValue);
  if (targetNode === null) {
    console.log("insert Fail. can't find target node.");
  } else {
    const newNode = new Node(newValue);
    newNode.next = targetNode.next;
    newNode.prev = targetNode;
    targetNode.next = newNode;
    this.count += 1;
  }
};

DoublyLinkedList.prototype.remove = function (targetValue) {
  if (this.find(targetValue) === null) {
    console.log("remove faill...");
    return;
  }

  let prevNode = this.head;

  if (prevNode.value === targetValue) {
    this.head = this.head.next;
    this.head.next.prev = null;
    this.count -= 1;
  } else {
    while (prevNode.next.value !== targetValue) {
      prevNode = prevNode.next;
    }

    if (prevNode.next !== null) {
      if (prevNode.next.next === null) {
        prevNode.next = null;
      } else {
        prevNode.next = prevNode.next.next;
        prevNode.next.prev = prevNode;
      }
      this.count -= 1;
    }
  }
};

DoublyLinkedList.prototype.display = function () {
  let currNode = this.head;
  let displyString = " ";

  while (currNode !== null) {
    displyString += `${currNode.value} `;
    currNode = currNode.next;
  }

  console.log(displyString);
};

DoublyLinkedList.prototype.size = function () {
  console.log(this.count);
};

const doubleLink = new DoublyLinkedList();
doubleLink.append(10);
doubleLink.append(20);
doubleLink.append(30);
doubleLink.append(40);
doubleLink.append(50);
doubleLink.insert(10, 25);
doubleLink.remove(40);
doubleLink.display();
doubleLink.size();