자료구조/알고리즘 - 연결 리스트[Doubly Linked List]

💁🏻‍♀️ 전에 작성한 단일 연결 리스트와 연결되는 글 입니다.
전 글을 보지 않으면 이해되지 않는 부분은 다시 기재하였습니다.

❓ 연결 리스트란?

• 각 노드가 데이터와 포인터를 가지며, 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
• 연속된 Node의 연결체 (즉, 체인처럼 연결된 데이터 상자)

🤔 연결 리스트에서 노드란?

• 연결 리스트에서 사용되는 하나의 데이터 덩어리이며, 데이터 & 링크 2가지의 필드를 담고 있는 구조이다.
  

---

✅ 연결 리스트의 구조

• 첫번째 node next에 다음 node 주소를 지정해 주고, 두번째 node next에 다음 node 주소를 지정해 준다.
• 마지막 node는 존재하지 않기 때문에 Null로 처리한다.
• 시작 지점의 node는 head라고 부르고 마지막 node는 tail(꼬리)라고 부름
  

---

✅ 배열과 연결리스트의 특징 비교

• 배열
  • random access가 가능하다. 즉, 바로 접근이 가능하다. (ex: arr[1])
  • 원소 삽입 및 삭제가 일반적으로 시간이 소요된다.
• 연결 리스트
  • random access가 불가능 하다. 만약, n번째 노드에 접근하려면 head노드부터 n번째까지 순회해야하기 때문이다.(시간이 걸림)
  • 상황에 따라 노드 삽입 및 삭제가 배열보다 빠르게 처리할 수 있다.

---

✅ 연결 리스트의 종류

• 단일 연결 리스트(singly Linked List)
  • 위 노드의 구조 예제와 동일하게 하나의 포인터를 가지고 있는 연결 리스트(한쪽 방향으로만 흐름)

---

• 이중 연결 리스트(Doubly Linked List)
  • 다음으로 넘어갈 수 있는 포인터만 가지고 있을 뿐만이 아니라, 이전으로 갈 수 있는 포인터도 가지고 있다. (즉, next와 prev)
  • 앞뒤로 탐색하는게 빠르다는 장점이 있지만, 노드 별로 2개의 포인터를 관리해야 하기 때문에 데이터의 구조와 흐름이 복잡해 질 수 있다.

---

• 원형 연결 리스트(Circular Linked List)
  • 마지막 tail 노드가 head 노드로 연결 되어 있음 (순환 구조라고 생각하면 쉬움)

---

✅ 이중 연결 리스트

• 각 노드가 데이터와 포인터를 가지며, 두 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다.
• 이중 연결 리스트는 2개의 포인터를 가지고 있다.
• Previous Link Field가 있는 것이 단일 연결 리스트와 다른점 이다.
  (앞으로 갈 수 있는 포인터 : next, 뒤로 갈 수 있는 포인터 : prev)
• 앞 뒤 구분은 우리가 시각적으로 확인하기 위해 있는 것이다.
• 단일 연결 리스트는 tail이 없지만 이중 연결 리스트는 마지막 노드를 tail이라고 부른다.
• 2개의 포인터를 관리해야하기 때문에 데이터의 구조와 흐름을 관리하기에 복잡하다.
• 한마디로 정의하자면 양방형 연결 리스트이다.

---

✅ 장점 및 사용하는 이유

• 단일 연결 리스트는 앞에서 뒤로만 접근이 가능하지만, 이중 연결 리스트는 양방향이기 때문에 뒤부터 접근이 가능하다.

이해를 돕기 위해 예제를 통해 설명하자면,
1번 인덱스에 있는 노드를 찾고 싶을 때 당연히 앞에서부터 찾는 것이 빠르다.
하지만, 뒤에 있는(4번 인덱스(50))를 찾게 된다면 어떨까? 뒤에서 부터 찾는 것이 훨씬 빠르다.

• 단일 연결 리스트가 가지고 있는 단점(순차적 이동)을 보완하는 연결 리스트이기 때문에 이중 연결리스트를 사용한다.
• next와 prev을 둘 다 가지고 있기 때문에 필요에 따라 앞, 뒤 이동이 가능하다.

---

✅ 단점

• 단점이 있기 때문에 단일 연결 리스트가 있다.
• 양방향을 유지해야하기 때문에 메모리를 더 많이 사용한다.
• 조금 더 복잡하다.

---

💡 연결 리스트 구현 메서드

1️⃣ Node 생성

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

2️⃣ Node 개수

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

3️⃣ Node가 비어있는지 확인

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

4️⃣ 순차 출력

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

5️⃣ 역 출력

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

6️⃣ Node 추가 (2가지)

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++;
};

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

7️⃣ Node 삭제 (2가지)

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

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

8️⃣ 데이터 위치 확인

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