Udemy - 이중 연결 리스트

이중 연결 리스트란?

단일 연결 리스트가 단방향으로만 연결된 리스트였다면,
이중 연결 리스트는 양방향으로 연결된 리스트다.

위의 사진에서 확인할 수 있듯, next와 prev를 통해 노드들이 양방향적으로 연결되어 있다.

이러한 특성 때문에 조금 더 유연하고 효율적으로 연결 리스트를 활용할 수 있다. 하지만, 이중 연결 리스트는 prev라는 프로퍼티가 하나 더 추가되었기 때문에 메모리 차지 비중이 단일 연결 리스트에 비해 크다는 상대적 단점을 갖는다. 따라서 이중 연결 리스트를 활용할 때, 이러한 공간 복잡도를 잘 고려하여 활용해야 한다.

연결 리스트에 대한 기본적인 내용들은 앞선 포스팅에서 다뤘기에, 바로 활용 방법에 대한 설명으로 들어가보도록 하겠다.

---

활용 방법

주요 메소드는 앞 장에서 설명했던 것과 같다. (push, pop, get, set, insert, remove)

공통 클래스

// 노드 생성을 위한 클래스
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

// DLL 생성을 위한 클래스 뼈대
class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

push

단일 연결리스트와 거의 유사하다.
next 외에도 prev를 신경 써서 연결해주면 된다!

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(val) {
    const newNode = new Node(val);
    // 헤드가 없으면 (리스트가 비어있으면) -> 삽입될 노드가 헤드와 테일이 된다.
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 기존 테일의 next = push 될 노드
      this.tail.next = newNode;
      // push될 노드의 prev = 기존 tail
      newNode.prev = this.tail;
      // push될 노드가 새로운 테일이 됨
      this.tail = newNode;
    }
    this.length++;
    return link;
  }
}

pop

이 또한 매우 간단하다.
다만 주의할 점은, 기존 Tail의 prev를 신경 써서 제거해줘야 한다는 것이다.

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  pop() {
    // 리스트가 비어있으면 어떠한 것도 pop할 수 없음
    if (!this.head) return null;
    // 기존 tail이 삭제되면 새로운 tail이 될 끝에서 두 번째의 노드
    const newTail = this.tail.prev;
    // 끝에서 두 번째 노드의 next를 삭제
    newTail.next = null;
    // 기존 tail의 prev도 삭제
    this.tail.prev = null;
    // 테일의 최신화
    this.tail = newTail;
    this.length--;
    return DLL;
  }
}

get

이 부분이 단일 연결리스트와 큰 차이점(?)을 보인다.
이전에 했던 분할 점령 방식을 활용하여 탐색 효율성을 증진 할 수 있기 때문이다.

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  get(index) {
    // 인덱스가 0보다 작거나, 리스트의 길이보다 길 수는 없다.
    if (index < 0 || index >= this.length) return null;
    // 오름차순으로 탐색을 할 지, 내림차순으로 탐색을 할 지 체크하기 위한 변수
    const isDesc = index > this.length / 2;
    let count;
    let tempNode;
    // 오름차순 -> 계속 상향식 탐색을 하며 인덱스와 카운트 수가 동일해질 때 까지 탐색한다.
    if (!isDesc) {
      tempNode = this.head;
      count = 0;
      while (count !== index) {
        count++;
        tempNode = tempNode.next;
      }
    } else {
      // 위와 반대!
      tempNode = this.tail;
      count = this.length - 1;
      while (count !== index) {
        count--;
        tempNode = tempNode.prev;
      }
    }
    this.length--;
    return tempNode;
  }
}

set

set은 get을 통해 노드에 접근을 한 뒤, 값만 변경해주면 되기 때문에 매우 간단하다.

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  set(index, val) {
    // 위에서 활용했던 것과 동일하게 인덱스 가능 범위를 벗어나면 return null
    if (index < 0 || index >= this.length) return null;
    // 1. get을 활용하여 타겟 노드를 반환 받는다.
    const targetNode = this.get(index);
    // 2. 타겟노드가 존재하지 않는다면 return null
    if (!targetNode) return null;
    // 3. 존재한다면 ? -> 매개변수로 받은 val을 노드에 갱신
    targetNode.val = val;
    return targetNode;
  }
}

shift

맨 앞의 노드를 제거해준다.
head가 변경되어야 하는 것을 주의해야 한다.

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  shift() {
    if (!this.head) return null;
    const currentHead = this.head;
    const newHead = currentHead.next;
    this.head = newHead;
    newHead.prev = null;
    currentHead.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return link;
  }
}

unshift

맨 앞에 새로운 노드를 추가해준다.

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  unshift(val) {
    if (!this.head) return this.push(val);
    const newNode = new Node(val);
    const currentHead = this.head;
    this.head = newNode;
    newNode.next = currentHead;
    currentHead.prev = newNode;
    this.length++;
    return link;
  }
}

insert

원하는 위치에 새로운 노드를 삽입해주면 된다.
하지만 주의할 점은, 위에서도 그러하였듯이 prev와 next의 연결을 명확하게 해줘야 한다.

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  insert(index, val) {
    // 인덱스 범위 밖 X (하지만, 삽입을 원하는 위치가 가장 끝일 수도 있기 때문에 이번에는 index > this.length가 조건)
    if (index < 0 || index > this.length) return null;
    // index가 0이면 unshift와 동일하다 (맨 앞에 삽입을 하겠다는 것이기 때문)
    if (index === 0) return this.unshift(val);
    // 끝에 삽입하겠다는 것은 push와 동일하다.
    if (index === this.length) return this.push(val);
    const newNode = new Node(val);
    const leftNode = this.get(index - 1);
    const rightNode = leftNode.next;
    // 좌우 노드들과 삽입 노드를 연결지어 준다.
    newNode.next = rightNode;
    newNode.prev = leftNode;
    rightNode.prev = newNode;
    leftNode.next = newNode;
    this.length++;
    return link;
  }
}

remove

원하는 노드를 삭제해주면 된다.
여기서도 동일하게 노드 간의 연결과 기존 연결의 제거를 신경써줘야 한다.

class DLL {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  remove(index, val) {
    // 없는 노드를 삭제할 수는 없으니까!
    if (index < 0 || index >= this.length) return null;
    // 0번을 삭제 ? -> shift()
    if (index === 0) return this.shift();
    // 끝을 삭제 ? -> pop()
    if (index === this.length - 1) return this.pop();
    const targetNode = this.get(index);
    const leftNode = targetNode.prev;
    const rightNode = targetNode.next;
    // 삭제할 노드의 next prev는 제거해준다.
    targetNode.next = null;
    targetNode.prev = null;
    // 그리고 left와 right 노드를 서로 연결해준다.
    leftNode.next = rightNode;
    rightNode.prev = leftNode;
    this.length--;
    return link;
  }
}

---

이중 연결 리스트의 시간 복잡도

메소드	시간 복잡도
Insertion (삽입)	O(1)
Removal (삭제)	O(1)
Search (탐색)	O(N)
Access (접근)	O(N)

단일 연결 리스트에서의 Insertion과 removal은 모두 O(N)의 시간복잡도를 가졌다.

하지만, 이중 연결 리스트에서는 두 메소드 모두 **O(1)**이라는 굉장히 효율적인 시간복잡도를 갖는다.

따라서, 삽입과 삭제가 잦은 경우에는 단일 연결 리스트보다 이중 연결 리스트를 활용하는 것이 효율적일 것이다.
반면, 이중 연결 리스트는 위에서도 설명했듯, 메모리 효율성이 단일 연결 리스트보다는 떨어지기에 이를 잘 고려하여 두 자료구조 중 하나를 선택하여 활용하는 것이 좋다.

---