1. The Basics of Linked Lists

1. What's special about linked lists?

• 순차적으로 연결된 value를 가진 data structure
• array보다 insertion/deletion이 효율적
• value의 메모리 주소들이 인접하지 않아도된다.

2. Linked lists vs arrays

노드를 접근할 경우

• array는 메모리에 인접한채로 있기 때문에, index를 통해 빠르게 접근 가능 -> O(1)
• Linked List는 메모리에 랜덤하게 저장되므로 특정 노드에 접근하려면, 첫 노드부터 순차적으로 접근해서 조회 가능 -> O(n)

새로운 노드를 삽입할 경우

• Array는 x를 삽입 시 메모리 주소를 한칸씩 밀어네고 O(n)의 복잡도 발생

• LinkedList는 삽입 할 노드의 next 메모리 주소만 변경

시간 복잡도

3. 코드 구현

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

class LinkedList {
  constructor() {
    this.head = null;
  }
  append(val) {
    if(this.head === null) {
      this.head = new Node(val)
      return;
    }
    let curr = this.head;
    while(curr.next !== null) {
      curr = curr.next;
    }
    curr.next = new Node(val) 
  }

  print() {
    let str = '';
    let curr = this.head;
    while (curr !== null) {
      str += curr.val
      curr = curr.next;
    }
    return str
  }

  contains(target) {
    let curr = this.head;
    while(curr !==  null) {
      if(curr.val === target) {
        return true;
      }
      curr = curr.next
    }
    return false;
  }

}

const list = new LinkedList();

참고 : Coderbyte - The Basics of Linked Lists