TIL: 자료구조 | 이중 연결 리스트 (doubly linked list)

이중 연결 리스트는 순차적으로 링크된 데이터 세트로 구성된 데이터 구조로 두 개의 포인터를 갖는다
각 노드에는 링크 라는 두 개의 필드가 있고,
이전 노드와 다음 노드에 대한 참조를 가진다
시작 및 종료 노드의 이전, 다음 링크는 종결자로 null 을 가진다
목록은 센티넬 노드를 통해 원형으로 연결 된다
동일한 데이터 항목을 갖지만 연결 리스트의 반대 순서로 두 개의 단일 연결 리스트로 개념화 할 수 있다

반대 방향 포인터도 갖게 되어 기능의 유연함을 갖게 되지만 더 많은 메모리가 필요하다

어느 정도 크기가 되면 이중 연결 리스트가 연결 리스트보다 효율적인지 구해보는 것도 좋겠다..

시간 복잡도

탐색: O(n)
삽입/삭제: O(1)

구현

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

class DLList {
	constructor() {
    	this.head = null;
      	this.tail = null;
      	this.length = 0;
    }
  
  	push(data) {
    	const newNode = new Node(data)
        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 true
    }
  
  	 shift() {
      if (this.length === 0) return undefined;
      const 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(data) {
      const newNode = new Node(data);
      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;
    }
  	
  	pop() {
    	if (!this.head) return undefined
      	const popNode = this.tail
        if (this.length === 1) {
        	this.head = null
          	this.tail = null
        } else {
        	this.tail = popNode.prev
          	this.tail.next = null
          	popNode.prev = null
        }
      	this.length--
      	return popNode
    }
  
  	get(index) {
    	if (index < 0 || index <= this.length) return null
      	let count
        let current
        if (index <= this.length / 2) {
        	count = 0
          	current = this.head
            while (count !== index) {
     			current = current.next
        		count++
      		}
        } else {
          count = this.length - 1
          current = this.tail
          while (count !== index) {
              current = current.prev
              count--
          }
    	}	
      	return current
    } 
	insert(index, data) {
    	if (index < 0 || index > this.length) return false
      	if (index === this.length) return !!this.push(data)
      	if (index === 0) return !!this.unshift(data)
      	const newNode = new Node(data)
        const beforeNode = this.get(index - 1)
        const afterNode = beforeNode.next
        
        beforeNode.next = newNode
      	newNode.prev = beforeNode
      	
      	newNode.next = afterNode
      	afterNode.prev = newNode
      	this.length++
      	return true
    }
    remove(index) {
      if (index < 0 || index > this.length) return undefined;
      if (index === 0) return this.shift();
      if (index === this.length - 1) return this.pop();

      const removedNode = this.get(index);
      removedNode.prev.next = removedNode.next;
      removedNode.next.prev = removedNode.prev;

      removedNode.next = null;
      removedNode.prev = null;
      this.length--;
      return removedNode;
    }
  }
	revese() {
      let node = this.head;

      this.head = this.tail;
      this.tail = node;


      let next; 
      let prev = null; 
      for (let i = 0; i < this.length; i++) {
        next = node.next;
        node.next = prev;
        prev = node;
        node = next;
      }

      next = null;  
      node = this.head;

      for (let i = 0; i < this.length; i++) {
        prev = node.prev;
        node.prev = next;
        next = node;
        node = prev;
      }
    }
}

get 함수에서 index 가 size 의 반 보다 크면
tail 부터 조회를 하여 연결 리스트보다 성능 개선이 된다

insert 시 인자로 주어진 index 가 size 범위 내의 것이 아니라면
맨 뒤에 추가해주는 방식도 고려해봐야 한다