[TIL 21][Data Structure] Single Linked List 코드 구현

function singleLinkedListNode(data) {
  this.data = data;
  this.next = null;
}

class singleLinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  isEmpty() {
    return this.size === 0;
  }
  insert(value) {
    if (this.head === null) {
      this.head = new singleLinkedListNode(value);
    } else {
      const temp = this.head;
      this.head = new singleLinkedListNode(value);
      this.head.next = temp;
    }
    this.size++;
  }
  remove(value) {
    let currentHead = this.head;
    if (currentHead.data === value) {
      this.head = currentHead.next;
      this.size--;
    } else {
      let prev = currentHead;
      while (currentHead.next) {
        if (currentHead.data === value) {
          prev.next = currentHead.next;
          prev = currentHead;
          currentHead = currentHead.next;
          break;
        }
        prev = currentHead;
        currentHead = currentHead.next;
      }
      if (currentHead.data === value) {
        prev.next = null;
      }
      this.size--;
    }
  }
  deleteHead() {
    const toReturn = null;

    if (this.head !== null) {
      toReturn = this.head.data;
      this.head = this.head.next;
      this.size--;
    }
    return toReturn;
  }
  find(value) {
    const currentHead = this.head;
    while (currentHead.next) {
      if (currentHead.data === value) {
        return true;
      }
      currentHead = currentHead.next;
    }
    return false;
  }
}

insert

• head가 null 일경우 head가 신규 node로 설정됨 null이 아닐 경우 예전 head가 temp에 저장되고 새로운 head가 신규로 추가된 node가 된다. 새로운 head의 next는 temp를 가리킴.

remove

• 삭제는 해당 node의 참조를 제거함으로서 구현할 수 있다. 위의 그림처럼 node가 연결 리스트의 중간에 있으면 삭제하고자 하는 node 이전 node의 next가 삭제하고자 하는 node의 다음 node를 가리키도록 한다. node가 단일 연결 리스트의 끝에 위치하면 마지막에서 두 번째 node가 자신의 next를 null로 설정하고 노드의 참조를 끊는다.

deleteHead

• 이름 그대로 head를 삭제한다

find

• value가 연결 리스트내에 존재하는지 확인하고 반복문을 통해 next가 가리키는걸 순회한다.

코드를 작성할 때 prototype에다가 넣어볼까 했는데 지금 class를 공부하고 있는중이라 class로 만들어서 해봤는데 이론을 실전에 대입하니까 상당히 괜찮은것 같다.