[선형] 7. 이중 연결 리스트

02 Oct 2021 in 자료구조 on 선형

목차
- 1. 이중 연결 리스트
- 2. 이중 연결 리스트 구현하기

1. 이중 연결 리스트 (Double Linked List)

이중연결리스트

각 노드가 데이터와 포인터를 가지며, 두 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
노드 개수 / 비어있는지 확인 : DoubleLinkedList.size(), DoubleLinkedList.isEmpty()
순차 출력 / 역 출력 : DoubleLinkedList.printNode(), DoubleLinkedList.printNodeInverse()
노드 추가 : DoubleLinkedList.append(), DoubleLinkedList.insert()
노드 삭제 : DoubleLinkedList.remove(), DoubleLinkedList.removeAt()
데이터 위치 확인 : DoubleLinkedList.indexOf()

2. 이중 연결 리스트 구현하기

1. 기본

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

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

DoubleLinkedList.prototype.size = function () {
  return this.length;
};

DoubleLinkedList.prototype.isEmpty = function () {
  return this.length === 0;
};

let dll = new DoubleLinkedList();
let node;
console.log(dll); //DoubleLinkedList { head: null, tail: null, length: 0 }

node = new Node(123);
dll.head = node;
dll.tail = node;
dll.length++;
console.log(dll);

// DoubleLinkedList {
//     head: Node { data: 123, next: null, prev: null },
//     tail: Node { data: 123, next: null, prev: null },
//     length: 1
//   }

node = new Node(456);
dll.tail.next = node;
node.prev = dll.tail;
dll.tail = node;
dll.length++;
console.log(dll);

// DoubleLinkedList {
//     head: <ref *1> Node {
//       data: 123,
//       next: Node { data: 456, next: null, prev: [Circular *1] },
//       prev: null
//     },
//     tail: <ref *2> Node {
//       data: 456,
//       next: null,
//       prev: <ref *1> Node { data: 123, next: [Circular *2], prev: null }
//     },
//     length: 2
//   }

2. printNode(), printNodeInverse(), append()

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")
}

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")
}

// while 안써도 된다
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++
}

dll.append(1)
dll.append(10)
dll.append(100)

dll.printNode() //head -> 123 => 456 => 1 => 10 => 100 => null
dll.printNodeInverse() //null <- 123 <- 456 <- 1 <- 10 <- 100 <- tail

3. 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;
    current.next = node;
    node.prev = current;
    this.tail = node;
  } else {
    while (index++ < position) {
      prev = current;
      current = current.next;
    }

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

    current.prev = node;
    node.prev = prev;
  }

  this.length++;

  return true;
};

dll.insert(1);
dll.insert(10);
dll.insert(100);

dll.printNode(); //head -> 100 => 10 => 1 => 123 => 456 => 1 => 10 => 100 => null
dll.printNodeInverse(); //null <- 100 <- 10 <- 1 <- 123 <- 456 <- 1 <- 10 <- 100 <- tail

dll.insert(2,1);
dll.insert(3,3);
dll.insert(100);

dll.printNode(); //head -> 100 => 100 => 2 => 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
dll.printNodeInverse(); //null <- 100 <- 100 <- 2 <- 10 <- 3 <- 1 <- 123 <- 456 <- 1 <- 10 <- 100 <- tail

4. 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;
};

dll.insert(1);
dll.insert(10);
dll.insert(100);
dll.insert(2,1);
dll.insert(3,3);
dll.printNode(); //head -> 100 => 100 => 2 => 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
dll.printNodeInverse(); //null <- 100 <- 100 <- 2 <- 10 <- 3 <- 1 <- 123 <- 456 <- 1 <- 10 <- 100 <- tail
console.log(dll.remove(1000)) //null
dll.printNode(); //head -> 100 => 100 => 2 => 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.remove(1))
dll.printNode(); //head -> 100 => 2 => 10 => 3 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.remove(2))
dll.printNode(); //head -> 100 => 10 => 3 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.remove(100))
dll.printNode(); //head -> 10 => 3 => 123 => 456 => 1 => 10 => 100 => null

5. 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
}


dll.insert(1);
dll.insert(10);
dll.insert(100);
dll.insert(2,1);
dll.insert(3,3);
dll.printNode(); //head -> 100 => 100 => 2 => 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
dll.printNodeInverse(); //null <- 100 <- 100 <- 2 <- 10 <- 3 <- 1 <- 123 <- 456 <- 1 <- 10 <- 100 <- tail
console.log(dll.removeAt(1000)) //null
dll.printNode(); //head -> 100 => 100 => 2 => 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.removeAt(4)) //1
dll.printNode(); //head -> 100 => 2 => 10 => 3 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.removeAt()) //100
dll.printNode(); //head -> 2 => 10 => 3 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.removeAt(1)) //10
dll.printNode(); //head -> 2 => 3 => 123 => 456 => 1 => 10 => 100 => null

6. indexOf()

// LinkedList 와 완전 동일
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;
};

DoubleLinkedList.prototype.remove2 = function (value) {
    let index = this.indexOf(value);
    return this.removeAt(index);
  };

dll.insert(1);
dll.insert(10);
dll.insert(100);
dll.insert(2, 1);
dll.insert(3, 3);
dll.printNode(); //head -> 100 => 100 => 2 => 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
dll.printNodeInverse(); //null <- 100 <- 100 <- 2 <- 10 <- 3 <- 1 <- 123 <- 456 <- 1 <- 10 <- 100 <- tail
console.log(dll.remove2(1000)); //null
dll.printNode(); //head -> 100 => 100 => 2 => 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.remove2(100)); //100
dll.printNode(); //head -> 2 => 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.remove2(2)); //2
dll.printNode(); //head -> 10 => 3 => 1 => 123 => 456 => 1 => 10 => 100 => null
console.log(dll.remove2(1)); //1
dll.printNode(); //head -> 10 => 3 => 123 => 456 => 1 => 10 => 100 => null