연결 리스트

1. 배열과 다르게 탐색에 불리함 O(n)
2. 요소 추가와 삭제는 유리함 O(1)
   (중간에 추가, 삭제하려면 노드 위치 찾아야 해서 결국 O(n)이기는 하다.)
3. 메모리가 허용하는 만큼 추가 가능
4. 싱글리, 더블리, 써큘러 형태가 있음

// 값과 다음을 가지고 있는 노드
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// 노드 간의 연결을 표현하는 링크드 리스트
class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  // 해당 값을 받고 node를 리턴해줌
  find(value) {
    let curNode = this.head;

    while (value !== curNode.value) {
      curNode = curNode.next;
    }

    return curNode;
  }

  // 해당 값을 추가해줌
  append(value) {
    const newNode = new Node(value);
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  // node와 값을 받고 해당 노드 다음 값을 넣어줌
  insert(node, value) {
    const newNode = new Node(value);
    newNode.next = node.next;
    node.next = newNode;
  }

  // 해당 값을 삭제
  remove(value) {
    let preNode = this.head;

    while (preNode.next.value !== value) {
      preNode = preNode.next;
    }

    if (preNode.next !== null) {
      preNode.next = preNode.next.next;
    }
  }

  // 링크드 리스트 출력
  display() {
    let curNode = this.head;
    let displayString = '[';

    while (curNode !== null) {
      displayString += curNode.value + ', ';
      curNode = curNode.next;
    }

    displayString = displayString.slice(0, displayString.length - 2);
    displayString += ']';
    console.log(displayString);
  }
}

const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(4);
linkedList.append(5);
linkedList.display();
console.log(linkedList.find(3));
linkedList.remove(3);
linkedList.display();
linkedList.insert(linkedList.find(2), 10);
linkedList.display();

• 싱글리
  

• 더블리
  

• 써큘러