인프런 커뮤니티 질문&답변

// 숙제1 next가 아닌 이전것 prev를 구하기
// 숙제2 삽입이 시간복잡도가 O(n)인데 O(1)으로 변경하기 (hint tail)
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}

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

  add(value) {
    const newNode = new Node(value);

    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      /*
      수정 
      const [prev] = this.#search(this.length - 1);

      this.tail.prev = prev;
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
      */
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this.length;
  }

  search(index) {
    return this.#search(index)[1]?.value;
  }

  prevSearch(index) {
    return this.#search(index)[0]?.value;
  }

  currentAndPrevNode(index) {
    return this.#search(index);
  }

  #search(index) {
    let count = 0;
    let prev;
    let current = this.head;
    while (count < index) {
      prev = current;
      current = current?.next;
      count++;
    }

    return [prev, current];
  }

  remove(index) {
    const [prev, current] = this.#search(index);
    if (prev && current) {
      if (!current.next) {
        // 마지막 노드 삭제일경우!
        prev.next = null; // 마지막 노드 삭제일때 이전 노드의 next를 null로 만들어주면 끝
        this.tail = prev; // 마지막 노드를 삭제 했기 때문에 tail을 이전 노드로 바꾸어주어야 한다.
      } else {
        // 중간 삭제 일때
        prev.next = current.next;
        current.next.prev = prev; // 현재 노드의 next노드의 이전 노드 prev를 prev 노드로 변경
      }
      this.length--;
      return this.length;
    } else if (current) {
      // index 0일 때
      this.head = current.next;

      this.length--;
      return this.length;
    } else {
      // 삭제하고자 하는 대상이 없을 떄
      // 아무것도 안함
    }
  }
}

const linkList = new LinkedList();
linkList.add(1); // 삭제
linkList.add(2);
linkList.add(3);
linkList.add(4);
linkList.add(5); // 삭제
linkList.add(6);
linkList.add(7);
linkList.add(8); // 삭제

console.log(linkList.search(6)); // 7
console.log(linkList.prevSearch(2)); // 2
console.log(linkList.tail.prev.value); // 마지막 꼬리의 이전이니까 7
console.log(linkList.remove(0)); // 첫번째 삭제 7
console.log(linkList.prevSearch(2)); // 3
console.log(linkList.tail.prev.value); // 마지막 꼬리의 이전이니까 7

console.log(linkList.remove(6)); // 마지막 삭제 6
console.log(linkList.tail.prev.value); // 삭제후 꼬리 이전이니까 6
console.log(linkList.tail.next); // null

console.log(linkList.remove(3)); // 5
const [prev, cur] = linkList.currentAndPrevNode(3); // 첫번째 튜플은 이전노드 두번째 튜플은 현재 노드
console.log(prev.value); // 4
console.log(prev.next.value); // 6
console.log(cur.value); // 6
console.log(cur.prev.value); // 4

::) prev와 tail을 추가 하였고 add 메서드와 remove 메서드를 수정 하였습니다.

질문1) 연결리스트 구현 숙제에 해당하는 정답 코드인지 리뷰 부탁드려도 될까요?

질문2) tail만 사용 했을때는 O(1) 시간복잡도를 가지게 add 메서드를 구현했었는데 prev가 추가되면서 const [prev] = this.#search(this.length - 1); 로직을 추가하여 prev를 구해서 O(1)가 아니게 된것 같은데 무언가 더 좋은 방법이 있을것 같습니다! (저는 고민 해봤는데 모르겠습니다)