DoubleLinkedList

이중연결리스트(DoubleLinkedList)는 기존 단반향 리스트의 단점을 보완한 자료구조이다. 단일 연결 리스트의 노드가 next 포인터만을 가졌다면 이중 연결 리스트의 노드는 prev와 next 두 개의 포인터를 갖는다.

DoubleLinkedList 자바스크립트 구현

1.객체생성, 출력함수

// Node() 이중 연결 리스트 이기 때문에 앞에 객체를 연결시켜주는 prev 변수가 하나더 생성된다.
function Node(data) {
  this.data = data;
  this.next = null;
  this.prev = null;
}
// DobleLinkedList ()
function DoubleLinkedList() {
  this.head = null;
  this.tail = null;
  this.length = 0;
}
// size() 노드 개수
DoubleLinkedList.prototype.size = function () {
  return this.length;
};
// isEmpty() 객체 내 노드 존재 여부 파악
DoubleLinkedList.prototype.isEmpty = function () {
  return this.length === 0;
};
// printNode() 노드 출력
DoubleLinkedList.prototype.printNode = function () {
  process.stdout.write("head -> ");
  for (let node = this.head; node != null; node = node.next) {
    process.stdout.write(`${node.data} -> `);
  }
  console.log("null");
};
/*printNode() 노드 역방향 출력
출력을 하게 된다면 
tail -> node3 -> node2 -> node1 -> null
이렇게 된다.
*/
DoubleLinkedList.prototype.printNodeInverse = function () {
  let temp = [];

  process.stdout.write("null <- ");
  for (let node = this.tail; node != null; node = node.prev) {
    temp.push(node.data);
  }
  for (let i = temp.length - 1; i >= 0; i--) {
    process.stdout.write(`${temp[i]} <- `);
  }
  console.log("tail");
};

2. append()

// append() 노드 맨 끝에 데이터 추가
DoubleLinkedList.prototype.append = function (value) {
  let node = new Node(value);

  if (this.head === null) {
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;
  }

  this.length++;
};

3. insert()

// insert() 해당 위치에 데이터 저장
DoubleLinkedList.prototype.insert = function (value, position = 0) {
  if (position < 0 || position > this.length) {
    return false;
  }
  let node = new Node(value),
    current = this.head,
    index = 0,
    prev;

  if (position == 0) {
    if (this.head == null) {
      this.head = node;
      this.tail = node;
    } else {
      node.next = current;
      current.prev = node;
      this.head = node;
    }
  } else if (position == this.length) {
    current = this.tail;
    node.prev = current;
    current.next = node;
    this.tail = node;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    prev.next = node;
    node.next = current;

    current.prev = node;
    node.prev = prev;
  }
  this.length++;

  return true;
};

4. remove()

// remove() 데이터 삭제
DoubleLinkedList.prototype.remove = function (value) {
  let current = this.head,
    prev = current;

  while (current.data != value && current.next != null) {
    prev = current;
    current = current.next;
  }

  if (current.data != value) {
    return null;
  }

  if (current === this.head) {
    this.head = current.next;
    if (this.length === 1) this.tail = null;
    else this.head.prev = null;
  } else if (current === this.tail) {
    this.tail = current.prev;
    this.tail.next = null;
  } else {
    prev.next = current.next;
    current.next.prev = prev;
  }

  this.length--;

  return current.data;
};

5.removeAt()

//removeAt() 해당 위치에 있는 데이터 삭제
DoubleLinkedList.prototype.removeAt = function (position = 0) {
  if (position < 0 || position >= this.length) {
    return null;
  }

  let current = this.head,
    index = 0,
    prev;

  if (position === 0) {
    this.head = current.next;
    if (this.length === 1) this.tail = null;
    else this.head.prev = null;
  } else if (position === this.length - 1) {
    current = this.tail;
    this.tail = current.prev;
    this.tail.next = null;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

    prev.next = current.next;
    current.next.prev = prev;
  }

  this.length--;

  return current.data;
};

6. index()

// index() 해당 데이터의 인덱스를 반환한다. 존재하지 않을 경우 결과 값은 -1이다
DoubleLinkedList.prototype.indexOf = function (value) {
  let current = this.head,
    index = 0;

  while (current != null) {
    if (current.data === value) {
      return index;
    }

    index++;
    current = current.next;
  }

  return -1;
};