[알고리즘] 이중 연결 리스트 (자바스크립트)

단일 연결 리스트 글과 이어집니다.

 

1. 이중 연결 리스트

단일 연결 리스트에서 추가적인 포인터가 하나 더 붙는게 다지만, 메서드 구현 시 많은 추가 코드를 필요로 한다. 따라서 지난 학습 때 구현했던 메서드들을 비교해보며 구현할 예정이다.

 

인덱스가 없고, 노드의 집합으로 이루어졌다는 연결 리스트의 특징을 여전히 갖고 있다. 추가적으로, 각 노드는 이전의 노드를 가리키는 prev 속성을 추가로 갖는다. 그러면 루프를 통해 Head부터 타고 들어갈 필요 없이, Tail부터 연산을 시작할 수 있으니 Reverse()같은 메서드를 구현하기는 더 쉬워질 것 같다.

 

노드 클래스 셋업

Node - val, next, prev

DLL - head, tail, length

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

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

 

2. 구현 메서드

Push 메서드

1. 기존 Tail의 .next가 새로운 노드를 가리키게 한다.
2. 마찬가지로 새로운 노드의 .prev는 기존의 Tail을 가리킨다.
3. 연결리스트의 Tail을 새로운 노드로 갱신하고, 길이를 1 증가시킨다.
4. 예외처리 : Head === null || Length ===0이면 리스트가 비어있다는 뜻이므로, Head와 Tail 둘 다 해당 노드에 부여하면 된다.

  push(val) {
    var newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = ths.head;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

 

Pop 메서드

1. Prev Attribute가 있기 때문에, Tail에서 연결을 끊어주면 된다.
2. 기존 Tail 노드의 .prev를 새로운 Tail로 지정
3. 기존 Tail 노드의 .prev와 새로운 Tail 노드의 .next 연결을 끊어줌
4. 요소가 제거된 후 길이가 0이 된다면, 연결 리스트의 Head과 Tail을 null로 지정
5. 길이를 1 감소시키고, 제거된 값을 반환한다.

  pop() {
    if (!this.head) return undefined;
    var temp = this.tail;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = poppedNode.prev;
      this.tail.next = null;
      temp.prev = null;
    }
    this.length--;
    return temp;
  }

 

Shift 메서드

1. 연결리스트가 0인 경우, Undefined를 반환하고 메서드를 종료한다.
2. 현재 Head의 .next를 새로운 Head로 지정
3. 기존 Head의 .next와 새로운 Head의 .prev를 null로 지정하여 연결을 끊어준다.
4. 연결리스트 길이가 1인 경우 원소가 제거되면 0이 되므로, Head와 Tail 값을 null로 지정해준다.

 shift() {
    if (!this.head) return undefined;
    var temp = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = temp.next;
      this.head.prev = null;
      temp.next = null;

      this.length--;
      return temp;
    }
  }

 

Unshift 메서드

1. 초기조건 : 연결리스트 길이가 0인 상태였다면, 새로 추가되는 노드를 Head와 Tail로 지정해준다.
2. 기존 Head의 .prev를 새로운 노드로, 새로운 노드의 .next를 기존 노드로 지정한다.
3. 연결리스트의 Head를 새로운 노드로 갱신한다.

  unshift(val) {
    var newNode = new Node(val);

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

 

Get 메서드

입력한 인덱스에 있는 노드를 반환. 기존의 단일 연결 리스트에서는 인덱스에 관계 없이 Head부터 순회하였으나, Tail에서부터 노드를 제어할 수 있게 되었기 때문에, 입력받은 인덱스에 따라 둘 중 하나를 시작점으로 선택하여 효율성을 증대

 

1. 입력 인덱스가 음수이거나 길이와 같을 시 null 반환
2. 입력된 인덱스 값이 0에 가까운지 (Head ~), Length - 1에 가까운지 (Tail~) 확인 : Length / 2와 인덱스 비교
3. 카운트 변수를 별도 선언하여 무한루프를 통해 인덱스 노드에 도달할 때 까지 반복

  get(idx) {
    if (index < 0 || index === this.length) return null;

    if (index <= this.length / 2) {
      var count = 0;
      var current = this.head;

      while (count != idx) {
        current = current.next;
        count++;
      }
      return current;
    } else {
      var count = this.length - 1;
      var current = this.tail;

      while (count != idx) {
        current = current.prev;
        count--;
      }
      return current;
    }
  }

 

Set 메서드

1. Get 메서드를 활용하여 입력한 인덱스에 위치하는 노드 값을 변경
2. 실행 여부에 따라 불린 타입 반환
3. 순회하는 특성이 없으므로 단일 연결 리스트의 방식과 동일

  set(idx, val) {
    var foundNode = this.get(idx);

    if (foundNode) {
      foundNode.val = val;
      return true;
    }
    return false;
  }

 

Insert 메서드

인덱스와 값을 입력받고, 해당 인덱스에 위치하는 노드에 값을 삽입하고 기존 노드를 한 칸 씩 미룬다.

1. 입력 인덱스가 음수이거나 길이보다 크거나 같은 경우, false 반환
2. 입력 인덱스가 0인 경우, Unshift
3. 입력 인덱스가 Length-1인 경우, Push
4. get(Index - 1) 노드에 접근하여, .next, .prev 관계 수정
5. 길이 증가 및 true 반환

  insert(idx, 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(idx - 1);
    var afterNode = beforeNode.next;

    beforeNode.next = newNode;
    afterNode.prev = newNode;

    newNode.prev = beforeNode;
    newNode.next = afterNode;

    this.length++;
    return true;
  }

 

Remove 메서드

1. 입력 인덱스가 음수이거나 길이보다 크거나 같은 경우, false 반환
2. 입력 인덱스가 0인 경우, shift
3. 입력 인덱스가 Length-1인 경우, Pop
4. get(Index) 노드에 접근하여, .next, .prev 값 null 지정 (연결 끊어냄)
5. 끊어낸 노드의 이전 노드와 다음 노드를 서로 연결
6. 길이 1 감소 및 제거된 노드 반환

  remove(idx) {
    if (index < 0 || index >= this.length) return false;
    if (index === 0) return this.shift(val);
    if (index === this.length) return this.pop(val);

    var foundNode = this.get(idx);
    var beforeNode = foundNode.prev;
    var afterNode = foundNode.next;

    foundNode.next = null;
    foundNode.prev = null;

    beforeNode.next = afterNode;
    afterNode.prev = beforeNode;

    this.length--;
    return foundNode;
  }

 

3. 이중 연결 리스트의 빅오 복잡도

• 삽입 : O(1)
• 제거 : O(1)
• 탐색 : O(N)
• 접근 : O(N)