linkedList prev와 tail 사용 후 o... - Inflearn

Non-majors catching up with majors - Data Structures (with JavaScript)

homework

linkedList prev와 tail 사용 후 o(1) 구현.

Written on

class LinkedList {
  length = 0;
  head = null;
  tail = null;

  add(value) {
    if (this.head) {
      this.tail.next = new Node(value);
      this.tail.next.prev = this.tail;
      this.tail = this.tail.next;

    } else {
      this.head = new Node(value);
      this.tail = this.head;
    }
    this.length++;
    return this.length;
  }
  search(index) {
    return this.#search(index)[1]?.value;
  }

  #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) {
      prev.next = current.next;
      this.length--;
      return this.length;
    } else if(current){ // index = 0 일 떄
      current = current.next;
      this.length--;
      return this.length;
    } 
    if (current.next === null) { // index = tail
      this.tail = current.prev;
      current.prev.next = null;
      this.length--;
    }
    // 삭제 대상 없을 때 아무것도 안함.
    
  }
}

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

const li = new LinkedList();

li.add(1);
li.add(2);
li.add(3);
li.add(4);
li.add(5);
console.log(li.add(6));
console.log(li.remove(5));
console.log(li.remove(4));

console.log 찍었을때는 오류 없이 나온거 같은데 잘 구현 했나 궁금합니다!

javascript코딩-테스트알고리즘

Answer 1

zerocho

Instructor

index가 0부터 시작하는 게 아니라 1부터 시작하는 건가요?

그리고 next의 마지막에 4가 남아있습니다

1,2,3,4,5,6에서 4, 5를 지우는 걸 의도하신 거죠? 그러면 remove(4), remove(3)이 되어야 하는 게 아닌가싶습니다. 그리고 중간에 value 4인 node도 제거하셔야 하고, tail과의 연결도 끊어져있어서 다시 이어주셔야 합니다.

samkookji12

Questioner

remove(index) {
    const [prev, current] = this.#search(index);

    if (prev && current) { // prev와 current 존재 중간 삭제
      if (current.next === null) { // tail 부분 삭제
        this.tail = current.prev;
        this.tail.next = null;
      } else {
          prev.next = current.next;
          current.next.prev = prev;
      }
    } else if (current === this.tail) { // index = 0, head 삭제
        this.head = null;
        this.tail = null;
    }
    this.length--;
    return this.length;
  }

li.add(1);
li.add(2);
li.add(3);
li.add(4);
li.add(5);
console.log(li.add(6));
console.log(li.remove(5));
console.log(li.remove(4));
console.log(li.remove(3));
console.log(li.remove(2));
console.log(li.remove(1));
console.log(li.remove(0));
console.log(li.remove(0));

remove() 부분을 다시 고쳐봤는데 어떤가요?
그리고 마지막에 remove(0)을 2번 반복했을떄 -1이 return 되는데 length에 조건이 없어서 그런건가요?

zerocho

Instructor

this.length--;를 무조건 수행해서 -1이 되는 것 같습니다.

Inflearn Community Q&A

linkedList prev와 tail 사용 후 o(1) 구현.