Linked List (연결 리스트)

Linked List는 Array와는 다르게 엘리먼트와 엘리먼트 간의 연결을 이용해서 리스트를 구현한 것을 의미한다.

Linked List는 노드에 값과 다음 값을 가르키는 값을 가지고 있다.

Big-O

• insertion: O(1)
• deletion: O(1)
• search: O(n)

Javascript 구현

class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.head = new Node('head');
  }
  find(item) {
    let currNode = this.head;
    while (currNode.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  }
  insert(newElement, item) {
    let newNode = new Node(newElement);
    let current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
  }
  display() {
    let currNode = this.head;
    while (!(currNode.next == null)) {
      console.log(currNode.next.element);
      currNode = currNode.next;
    }
  }
  findPrevious(item) {
    let currNode = this.head;
    while (!(currNode.next == null) && currNode.next.element != item) {
      currNode = currNode.next;
    }
    return currNode;
  }
  remove(item) {
    let prevNode = this.findPrevious(item);
    if (!(prevNode.next == null)) {
      prevNode.next = prevNode.next.next;
    }
  }
}

참고
https://jeong-pro.tistory.com/126