4.3Doubly Linked Lists

Doubly Linked List

Singly Linked List와 비슷하지만, previous 노드를 가리키는 포인터가 있는 연결된 리스트

Doubly Linked List는 앞서 살펴본 Singly Linked List와 거의 비슷하지만 양방향(next뿐 아니라 prev도)으로 포인터 정보를 포함하고 있는 리스트다.

Singly Linked List에서 구현한 몇몇 메소드들(pop, reverse등)을 생각해보면, 하나의 노드는 다음 노드만 가리키고 있어서(value외에는 next 속성밖에 없어서) 기존의 tail을 제거하고 직전 노드를 tail로 만들고 싶어도 직전 노드를 바로 찾을 수 없다거나 하는 문제가 있었다. Doubly Linked List는 메모리를 더 쓰는 반면(prev 정보 포함) prev가 없는 불편함을 줄여준다.

보다 자세한 내용은 메소드들을 구현하며 살펴보자.

노드와 리스트 만들기

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

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

push 만들기

수도코드를 만든다면 이렇게 될 것이다:

• 새 노드를 만든다.
• head가 null이라면 새 노드를 head이자 tail로 만든다.
• 아니라면, tail의 next를 새 노드로 만든다.
• 새 노드의 prev를 (기존) tail로 설정한다.
• 새 노드를 tail로 지정한다.
• length를 증가시키고 list를 반환한다.

javascript
class DoublyLinkedList {
 // ...
  push(val){
    const newNode = new Node(val);
    if(this.length === 0){
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }
}

pop 만들기

• head가 없다면, undefined를 반환한다.
• 그렇지 않다면, 현재 tail을 임시 변수에 저장한다(나중에 반환하기 위함).
• length가 1이라면, head와 tail에 null을 할당한다.
• tail을 그것의 prev 노드로 바꾼다.
• 새로운 tail의 next에 null을 할당한다.
• length를 1 감소시키고, 임시 변수에 저장한 과거 tail을 반환한다.

javascript
class DoublyLinkedList {
 // 다른 메소드들...
  pop(){
    if(!this.head) return undefined;
    const poppedNode = this.tail;
    if(this.length === 1){
      this.head = null;
      this.tail = null;
    } else {
      this.tail = poppedNode.prev;
      this.tail.next = null;
      poppedNode.prev = null;
    }
    this.length--;
    return poppedNode;
  }
}

shift 만들기

• length가 0이면 undefined를 반환한다.
• 현재 head를 임시 변수에 할당한다.
• length가 1이면 리스트의 head와 tail에 모두 null을 할당한다.
• head에 현재 head의 next를 할당한다.
• head의 prev에 null을 할당한다.
• 임시 변수에 할당한 head의 next에 null을 할당한다.
• length를 1 감소시키고 임시 변수에 할당한 예전 head를 반환한다.

javascript
class DoublyLinkedList {
 // 다른 메소드들...
  shift(){
    if(this.length === 0) return undefined;
    let oldHead = this.head;
    if(this.length === 1){
      this.head = null;
      this.tail = null;
    } else {
      this.head = oldHead.next;
      this.head.prev = null;
      oldHead.next = null;
    }
    this.length--;
    return oldHead;
  }
}

unshift 만들기

• value를 받아 노드를 생성한다.
• length가 0이면 head와 tail에 새 노드를 할당한다.
• 그렇지 않다면, head의 prev에 새 노드를 할당한다.
• 새 노드의 next에 head를 할당한다.
• head를 새 노드로 업데이트한다.
• length를 1 늘리고 리스트를 반환한다.

javascript
class DoublyLinkedList {
 // 다른 메소드들...
  unshift(val){
    let newNode = new Node(val);
    if(this.length === 0){
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length++;
    return this;
  }
}

get 만들기

Singly Linked List와 비슷하게 루프문으로 순서를 찾아야하지만, tail이 있으므로 만약 index가 tail보다 가깝다면 tail에서 시작할 수 있다는 차이가 있따.

• index가 0보다 작거나 length보다 크다면 undefined를 반환한다.
• index가 length의 절반보다 작거나 같다면 head부터, 크다면 tail부터 루프를 시작해 index를 찾는다.
• 이후 해당 index의 노드를 반환한다.

javascript
class DoublyLinkedList {
 // 다른 메소드들...
  get(index){
    if(index < 0 || index >= this.length) return undefined;
    let count, current;
    if(index <= this.length / 2){
      count = 0;
      current = this.head;
      while(count != index){
        current = current.next;
        count++;
      }
    return current;
    } else {
      count = this.length - 1;
      current = this.tail;
      while(count != index){
        current = current.prev;
        count--;
      }
      return current;
    }   
  }
}

set 만들기

Singly Linked List와 비슷하게, get으로 노드를 받아 새로운 값을 할당하고 true를 반환하면 된다.

javascript
class DoublyLinkedList {
 // 다른 메소드들... 
  set(index, value){
    let foundNode = this.get(index);
    if(foundNode){
      foundNode.val = value;
      return true;
    }
    return false;
  }
}

insert 만들기

역시 Singly Linked List와 비슷하지만, 연결이 양방향이기 때문에 삽입할 경우 끊고 연결해야하는 횟수도 두배가 된다.

• index가 0보다 작거나 length보다 크면 false를 반환한다.
• index가 0이면 unshift한다.
• index가 length와 같다면 push한다.
• get으로 index - 1번째 노드에 접근한다.
• 해당 노드의 next와 다음 노드의 prev에 새로운 노드를 할당한다.
• length를 1 늘리고 true를 반환한다.

javascript
class DoublyLinkedList {
 // 다른 메소드들...
 insert(index, value){
  if(index < 0 || index > this.length) return false;
  if(index === 0) return !!this.unshift(value);
  if(index === this.length) return !!this.push(value);
  let newNode = new Node(value);
  let beforeNode = this.get(index - 1);
  let afterNode = beforeNode.next;

  beforeNode.next = newNode, newNode.prev = beforeNode;
  afterNode.prev = newNode, newNode.next = afterNode;
  this.length++;
  return true;
  } 
}

remove 만들기

• index가 0보다 작거나 length보다 크거나 같으면 undefined를 반환한다.
• index가 0이면 shift한다.
• index가 length - 1이면 pop한다.
• get으로 index에 해당하는 노드를 찾아 임시 변수에 저장한다.
• next와 prev 노드들을 업데이트한다.
• 제거 대상 노드의 next와 prev 속성에 null을 할당한다.
• length를 1 줄이고 제거 대상 노드를 반환한다.

javascript
class DoublyLinkedList {
 // 다른 메소드들...
 remove(index){
  if(index < 0 || index >= this.length) return undefined;
  if(index === 0) return !!this.shift();
  if(index === this.length - 1) return !!this.pop();
  let removedNode = this.get(index);
  removedNode.prev.next = removedNode.next;
  removedNode.next.prev = removedNode.prev;
  removedNode.next = null;
  removedNode.prev = null;
  this.length--;
  return removedNode;
 } 
}

Doubly Linked List의 Big O

검색은 물론 앞에서 시작/뒤에서 시작하므로 O(N/2)이므로 Singly Linked List보다는 효율적이지만, 어쨌든 여전히 O(N/2) = O(N)이다.

Singly Linked List와 비교하면 제거도 O(1)로 시간 복잡도가 낮지만, 이에 대한 대가로 prev 포인터가 있어 공간 복잡도가 보다 높다.