2. 연결 리스트-remove(), removeAt(), indexOf()

remove() 풀이

- value 데이터를 찾아서 노드를 삭제한다.

- 삭제할 value 값이 없으면 null, 있으면 해당 값을 반환하면서 길이 줄이는 함수를 만든다.

 

1. while 반복문에서 current.data가 value와 일치하는 지점까지 찾는다. prev는 current의 뒷 노드를 가리킨다. 

2. if문에서 this.head와 같을 경우에는 this.head를 current.next(current의 다음)으로 넘겨준다.

3. if문에서 this.head와 다를 경우에는 prev.next(이전 노드)를 current.next(다음 노드)로 넘겨준다. 

// remove(): value 데이터를 찾아서 노드 삭제
LinkedList.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;
  } else {
    prev.next = current.next;
  }

  this.length--;

  return current.data;
};

let ll = new LinkedList();

ll.insert(1);
ll.insert(10);
ll.insert(100);
ll.insert(2, 1);
ll.insert(3, 3);
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> 1 -> null

console.log(ll.remove(1000)); // null
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> 1 -> null
console.log(ll.remove(1)); // 1
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> null
console.log(ll.remove(2)); // 2
ll.printNode(); // 100 -> 10 -> 3 -> null
console.log(ll.remove(100)); // 100
ll.printNode(); / /10 -> 3 -> null
console.log(ll.size()) // 2

removeAt() 풀이

- position 위치의 노드를 삭제한다.

 

1. positon 값이 0보다 작거나 주어진 길이보다 클 경우 null을 반환한다.

2. position===0일 경우, this.head가 current.next를 가리키고 length는 줄어들며 삭제된 current.data 값이 반환된다.

3. position !=0일 경우, index값을 더해가며 삭제할 노드의 순서까지 반복한다. prev(바로 전 노드)에 current 값을, current에 current.next 값을 가리키게 해서 이어지지 못한 노드가 삭제된다.

// removeAt(): position 위치 노드 삭제
LinkedList.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;
  }else {
    while(index++ < position){
      prev = current;
      current = current.next;
    }

    prev.next = current.next;
  }

  this.length--;

  return current.data;
};

let ll = new LinkedList();

ll.insert(1);
ll.insert(10);
ll.insert(100);
ll.insert(2, 1);
ll.insert(3, 3);
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> 1 -> null

console.log(ll.removeAt(1000)); // null
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> 1 -> null
console.log(ll.removeAt(4)); // 1
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> null
console.log(ll.removeAt()); // 100
ll.printNode(); // 2 -> 10 -> 3 -> null
console.log(ll.removeAt(1)); // 10
ll.printNode(); // 2 -> 3 -> null
console.log(ll.size()) // 2

 

indexOf() 풀이

- indexOf()를 통해 찾은 값을 removeAt()에 넣어서 remove()와 같게 동작하도록 한다.

 

1. current가 null이 아닐 때까지 반복한다. 

2. current.data === value일 때, index 값이 더해지면서 current.data===value 값이 같아지면 index를 반환한다.

3. current가 null이 될 때까지 값을 찾지 못하면 -1이 반환된다.

4. removeAt()에 indexOf()를 통해 찾은 index를 삭제한다. 

// indexOf(): value 값을 갖는 노드 위치 반환
LinkedList.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;
};

// remove2(): indexOf + revmoveAt = remove
LinkedList.prototype.remove2 = function(value){
  let index = this.indexOf(value);
  return this.removeAt(index);
}


let ll = new LinkedList();

ll.insert(1);
ll.insert(10);
ll.insert(100);
ll.insert(2, 1);
ll.insert(3, 3);
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> 1 -> null

console.log(ll.indexOf(1000)); // -1
console.log(ll.indexOf(1)); // 4
console.log(ll.indexOf(100)); // 0
console.log(ll.indexOf(10)); // 2

console.log(ll.remove2(1000)); // null
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> 1 -> null
console.log(ll.remove2(1)); // 1
ll.printNode(); // 100 -> 2 -> 10 -> 3 -> null
console.log(ll.remove2(2)); // 2
ll.printNode(); // 100 -> 10 -> 3 -> null
console.log(ll.remove2(100)); // 100
ll.printNode(); // 10 -> 3 -> null
console.log(ll.size()) // 2