Doubly Linked List (이중 연결 리스트)

Datastructure & Algorithm

Doubly Linked List (이중 연결 리스트)

마손리 2023. 1. 31. 22:11

이중 연결 리스트

단일 연결 리스트와 마찬가지로 head와 tail을 가지며 인덱스가 없어 인덱스를 이용한 무작위 접근을 할수 없다.

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

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

위의 클래스를 보면 단일 연결 리스트와 비슷하지만 하나 다른점은 각 노드들이 자신의 앞의 노드를 가르키는 포인터를 하나씩 더 갖으며 이로인해서 특정 작업에 관해서는 시간복잡도의 효율이 좋아지지만 공간복잡도의 효율이 나빠진다.

단일 연결 리스트의 경우 각 노드들은 자신의 정보와 다음 노드의 정보만을 저장하면되지만 이중 연결 리스트의 경우 자신의 정보, 다음노드의 정보, 이전노드의 정보까지 저장해야 되기 때문이다.

push() 메소드

리스트의 마지막에 새로운 노드를 추가하는 메소드이다.

  push(val) {
    let newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return newNode;
  }

새 노드를 생성해준뒤, 리스트가 비어있다면 리스트의 head와 tail을 생성된 노드로 지정해준다.
만약 리스트에 다른 노드가 존재한다면 현재의 tail 노드의 다음 노드를 생성한 노드로 연결한뒤
생성된 노드의 이전노드로 현재의 tail을 연결하고 현재의 tail을 생성된 노드로 지정해준 후 리스트의 길이를 +1 해준다.

pop() 메소드

리스트의 마지막 노드를 삭제 해주는 메소드이다.

단일 링크의 경우 마지막 노드의 이전 노드에 접근해야하므로 리스트의 head부터 tail까지 순차적으로 접근해 줘야됬지만 이중 링크의 경우 각 노드마다 이전 노드의 정보를 가지고 있으므로 위의 과정을 생략할수 있다.

  pop() {
    if (!this.head) return undefined;
    let removedNode = this.tail;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = removedNode.prev;
      this.tail.next = null;
      removedNode.prev = null;
    }
    this.length--;
    return removedNode;
  }

리스트에 노드가 존재하는지 확인해준뒤 리스트의 현재 tail을 변수에 저장한다.
만약 리스트의 노드가 한개 이상이라면 리스트의 tail을 자신의 이전 노드로 등록해준뒤 등록된 tail의 다음 노드를 연결해제 시켜준다.
이후 변수에 저장된 작업 전의 tail의 이전 노드의 연결을 끊고 반환시킨다.

shift() 메소드

리스트의 첫번째 노드를 삭제시키는 메소드이다.

작동 원리는 pop()과 같으나 tail이 아닌 head를 교체시켜준다.

  shift() {
    if (!this.head) return undefined;
    let removedNode = this.head;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = removedNode.next;
      this.head.prev = null;
      removedNode.next = null;
    }
    this.length--;
    return removedNode;
  }

리스트에 노드가 존재하는지 확인해준뒤 리스트의 현재 head를 변수에 저장한다.
만약 리스트의 노드가 한개 이상이라면 리스트의 head를 자신의 다음 노드로 등록해주고 등록된 head의 이전 노드를 연결해제 시켜준다.
이후 변수에 저장된 작업 전의 head의 다음 노드의 연결을 끊고 반환시킨다.

unshift() 메소드

리스트의 첫번째 노드에 데이터를 추가해주는 메소드이다.

  unshift(val) {
    let newNode = new Node(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.length++;
    return newNode;
  }

추가될 노드를 생성해준뒤 리스트가 비어있다면 리스트의 head와 tail에 생성된 노드를 등록해준다.
만약 리스트에 노드가 존재한다면 생성된 노드의 다음노드로 현재의 head를 연결하고 현재의 head의 이전 노드로 생성된 노드를 연결해준다.
이후 리스트의 head를 생성된 노드로 등록한뒤 리스트의 길이를 +1 해준다.

get() 메소드

인덱스를 받아 그 인덱스에 위치한 노드에 접근한다.

단일 연결 리스트와 작동 원리는 같다. 하지만 단일 연결의 경우 head에서부터 해당 인덱스의 노드까지 순차적으로 접근해야되지만 이중 연결의 경우 tail에서도 접근이 가능하다.

이를 이용하여 노드의 중앙을 기준으로 더 가까운쪽에서부터 접근을 실행한다.

  get(index) {
    if (index < 0 || index > this.length - 1) return null;

    let currentNode;
    if (index <= this.length / 2) {
      currentNode = this.head;
      for (let i = 0; i < index; i++) currentNode = currentNode.next;
    } else {
      let newIndex = this.length - 1 - index;
      currentNode = this.tail;
      for (let i = 0; i < newIndex; i++) currentNode = currentNode.prev;
    }
    return currentNode;
  }

우선 인자로 받은 인덱스가 알맞은 범위 인지 확인하고 해당 위치의 노드를 저장할 변수를 생성한다.
만약 받은 인덱스가 리스트 길이의 절반의 값보다 작을경우, 해당 인덱스는 head에 더 가까우므로 변수에 head를 저장한다.
이후 반복문을 이용하여 변수에 저장된 노드의 다음노드를 받은 인덱스만큼 반복하여 갱신해준뒤 반복문 종료후 반환한다.
만약 받은 인덱스가 리스트 길이의 절반의 값보다 높을경우에는 인덱스에 위치한 노드는 tail에 더 가까우므로 tail에서 부터 해당 인덱스까지의 거리를 계산해서 저장하고 노드를 저장할 변수에 현재의 tail 또한 저장한다.
이후 계산된 새 인덱스만큼 반복문을 돌려 tail부터 이전 노드들을 순차적으로 거치며 원하는 노드를 찾아낸다.

set() 메소드

데이터값과 인덱스를 인자로 받아 해당 인덱스에 위치한 노드의 데이터를 바꾼다.

  set(val, index) {
    let currentNode = this.get(index);
    if (!currentNode) return false;
    currentNode.val = val;
    return true;
  }

위에 작성된 get()메소드를 이용하여 해당위치의 노드에 접근한뒤 값을 바꿔준다.

insert() 메소드

데이터값과 인덱스를 인자로 받아 해당 인덱스에 새로운 노드를 생성한다.

  insert(val, index) {
    if (index < 0 || index > this.length) return false;
    if (index === 0) return !!this.unshift(val);
    if (index === this.length) return !!this.push(val);

    let newNode = new Node(val);
    let currentNode = this.get(index);
    let prevNode = currentNode.prev;

    prevNode.next = newNode;
    newNode.prev = prevNode;
    newNode.next = currentNode;
    currentNode.prev = newNode;

    this.length++;
    return true;
  }

받은 인덱스가 0이라면 unshift() 메소드를, 리스트의 길이와 같다면 push() 메소드를 호출한뒤 각각의 결과 값을 boolean으로 반환시켜준다.
받은 인덱스가 그 외의 범위라면 새로운 노드를 만들고 get() 메소드를 이용하여 해당 인덱스에 위치한 노드와 그 이전노드를 각각 변수에 저장한다.
이후 각각의 위치에 맞게 노드들을 연결시켜준뒤 리스트의 길이를 +1 해준다.

remove() 메소드

인덱스를 받아 해당 인덱스의 노드를 제거해준다.

insert() 메소드와 작동원리가 굉장히 비슷하게 해당 인덱스의 노드를 찾아서 그 이전 노드와 이후 노드의 연결을 알맞게 해주면 된다.

  remove(index) {
    if (index < 0 || index > this.length - 1) return undefined;
    if (index === 0) return this.shift(val);
    if (index === this.length - 1) return this.pop(val);

    let currentNode = this.get(index);
    let prevNode = currentNode.prev;
    let nextNode = currentNode.next;

    prevNode.next = nextNode;
    nextNode.prev = prevNode;
    currentNode.prev = null;
    currentNode.next = null;

    this.length--;
    return currentNode;
  }
}

받은 인덱스에 맞게 shift()와 pop() 메소드들을 이용해준다.
만약 받은 인덱스가 그 외의 범위라면 get()메소드를 이용하여 해당위치의 노드와 그 이전, 이후 노드들까지 찾아내 준다.
이후 이전 노드와 이후노드를 서로 연결해준뒤 삭제된 노드에 연결된 모든 노드들을 끊어주고 리스트의 길이를 수정한뒤 연결이 해제된 노드를 반환시킨다.

reverse() 메소드

모든 노드의 순서를 반전시키는 메소드이다.

  reverse() {
    let current = this.head;
    this.head = this.tail;
    this.tail = current;
    for (let i = 0; i < this.length; i++) {
      let prev = current.prev;
      current.prev = current.next;
      current.next = prev;
      current = current.prev;
    }
    return this;
  }

먼저 리스트의 head와 tail을 바꿔준다.
이후 반복문을 이용하여 tail의 이전 노드를 다음 노드로, 다음 노드를 이전노드로 교체해준뒤 교체된 후의 이전노드로 이동하여 반복하여 작업을 실행해준다.

Big O notation

첫 노드와 마지막노드의 삽입과 삭제의 경우 단일 연결 리스트와 마찬가지로 O(1)이 된다.

다만 탐색과 접근의 경우 약간의 변화가 있는데, 이중 연결 리스트를 사용하면 head와 tail에서 부터 접근이 가능하므로 기술적으로는 O(n/2)이 된다. 리스트의 중간부터의 삽입과 삭제의 경우도 탐색과 접근을 사용하기에 같은 O(n/2)이 된다.

마무리

이중 연결 리스트는 이전 노드를 가리키는 포인터가 하나 더있다는 점만 빼면 단일 연결 리스트와 똑같다. 그로인해 일부 기능들은 좀더 쉽게 사용할수 있다. 예를 들자면 인터넷 브라우저의 뒤로가기와 앞으로가기와 같은 기능들의 경우 이중 연결 리스트를 사용하여 단일 연결 리스트보다 더 효율적으로 사용할수 있다.

이중 연결 리스트는 무언가를 찾을때 단일 연결 리스트보다 절반의 시간을 절약할수 있다. 하지만 각 노드들이 이전 노드의 정보를 저장하기 위해 메모리를 더 소모한다는 것을 유의해야된다.

'Datastructure & Algorithm' 카테고리의 다른 글

Binary Search Tree (이진 검색 트리) (0)	2023.02.08
Stack & Queue 자료구조 (0)	2023.02.01
Singly linked list (단일 연결 리스트) (0)	2023.01.31
Radix Sort (기수 정렬) 알고리즘 (2)	2023.01.27
Quick Sort (퀵 정렬) 알고리즘 (0)	2023.01.26

현재글Doubly Linked List (이중 연결 리스트)

JPA, mysql, 비동기, sql, OOP, DB, apollo, 객체지향 프로그래밍, typescript, Thread, 재귀, Enum, optional, UsernamePasswordAuthenticationToken, GraphQL, SecurityContextHolder, transaction, 스레드, annotation, 동기,

Today :
Yesterday :

일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Mason