자료구조 이중 연결 리스트(Doubly Linked List) 맨 뒤 노드 삽입, 삭제 구현하기 #1 (JS)

단일 연결리스트는 다음 노드의 주소만 기억하고 이전 노드를 기억하지 않았지만,
이중 연결 리스트는 다음 노드의 주소와 이전 노드의 주소를 함께 기억하고 있는 자료구조이다.

오늘은 DDL에서 맨 뒤에 노드 삽입(append), 맨 뒤 노드 삭제(pop)하는 것을 구현해보기로 했다.
그나마 가장 간단한 맨 뒤 추가, 삭제 먼저 작성하면서 개념 다시 정리하기! 😊

연결 리스트가 막 어려운 개념은 아닌데 직접 코드로 짜려고하면 생각해야 하는 게 많아서
코드 짜면서 블로그에 정리겸 다른 기능(i번째 추가, 삭제 등)은 나눠서 구현해보려한다.

function DoublyLinkedList(){
  this.length = 0;
  this.head = null;
  this.tail = null;
}

function Node(data){
  this.data = data;
  this.next = null;
  this.prev = null;
}

let dll = new DoublyLinkedList();
console.log(dll)

먼저 가장 중요한 생성자 함수 만들기
DLL과 Node 생성자 함수를 만들어주었다.

appned

이중 연결 리스트 맨 뒤에 노드 삽입하기

DoublyLinkedList.prototype.append = function (data) {
  let newNode = new Node(data);

  if (this.length === 0) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.prev = this.tail;
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.length++;
};

먼저 현재 이중 연결 리스트의 길이가 0인 상태(노드가 아무것도 없는)라면 새로운 노드를 가장 맨 앞 노드로 설정해주면 되기 때문에 매우 간단하다. head와 tail 값을 새로운 노드의 값으로 설정만 해주면 된다.

만약 노드가 1개라도 있는 상태라면, 새로운 노드의 이전 값으로 현재 이중 연결 리스트의 맨 뒤 노드로 설정해주고, 현재 맨 뒤 노드의 다음 노드로 새로운 노드를 설정해준다.
이것이 완료되었다면, 이제 새로운 노드가 맨 뒤 노드여야하므로 tail값으로 새로운 노드를 설정해주면 된다.

let dll = new DoublyLinkedList();
dll.append(1);
dll.append(2);
dll.append(3);
console.dir(dll);

제대로 되는지 테스트도 해보았다.
next와 prev 값이 잘 연결되어 있다면 제대로 작성한 것!

pop

맨 뒤 노드를 삭제하는 메서드를 구현해보았다.

DoublyLinkedList.prototype.pop = function () {
  if (this.length > 1) {
    this.tail = this.tail.prev;
    this.tail.next = null;
  } else {
    this.head = null;
    this.tail = null;
  }
  this.length--;
};

처음에 뭐야 왜이렇게 간단해? 하고 넘어갈 뻔 했었던 pop.. ㅋㅋ
현재 노드가 1개인 경우의 예외처리를 해주어야 했다.
1개 이상이라면 맨 뒤 노드 자리를 맨 뒤 노드의 바로 앞에 있는 노드에게 전달해주고 새로운 맨 뒤 노드의 next를 null로 변경해주면 된다.
그리고 노드를 삭제했으므로 현재 이중 연결 리스트의 길이도 1 감소 시켜주어야 한다.

다음에 해볼 것은 벌써부터 무시무시한 n번째 추가, 삭제이다.
이전에 단일 연결 리스트 할 때도 엄청 헷갈려하면서 구현했던 기억이 있다..