리스트, 해쉬테이블을 사용하는 이유 / 시간복잡도 / 메서드들의 동작 방식

요약

링크드 리스트를 사용하는 이유는 주로 동적 데이터 구조 또는 삽입 및 삭제 연산이 빈번한 상황에서 활용됩니다. 배열의 중간에 요소를 삽입하거나 삭제할 경우, 해당 위치 이후의 모든 요소를 이동시켜야 하므로 O(n) 시간 복잡도를 가지는 반면, 링크드 리스트는 해당 노드의 링크를 조정하는 것으로 가능하므로 O(1) 시간 복잡도를 가지게 됩니다. 해쉬 테이블을 사용하는 이유는 빠른 데이터 검색과 접근이 필요한 상황에서 활용됩니다. 해시 함수를 통해 데이터를 고르게 분산시키며 고유한 키-값 쌍을 통해 검색, 삽입, 삭제는 O(1) 시간복잡도를 가지게 됩니다. 단, 충돌이 발생할 경우 충돌 해결 알고리즘이 사용되며, 시간복잡도에 영향을 줄 수 있습니다.

Linked List란?

데이터 구조의 하나로 여러 개의 값을 저장하기 위한 구조

데이터와 포인터가 한 쌍으로 구성되어 있음, 포인터가 다음 데이터의 메모리 위치를 가리킴.

단일 연결 리스트(Singly-Linked List)

각 노드에 자료 공간과 1개의 포인터 공간이 있으며 각 노드의 포인터는 다음 노드를 가리킨다. 단방향이다.

이중 연결 리스트(Doubly-Linked List)

구조는 단일 연결 리스트와 비슷하나 포인터 공간이 2개이고, 각각의 포인터는 앞의 노드와 뒤의 노드를 가리킨다. 양방향이다.

원형 연결 리스트(Circular-Linked List)

일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 이뤄짐.

Linked List vs 배열

배열은 JS 같은 경우에는 타 언어와는 다르게 동적인 자료구조이다.

배열	Linked List
정적 자료구조	동적 자료구조
연속된 메모리 주소를 할당받음	연속된 메모리 주소를 할당 받지 않음
접근 및 탐색이 용이	삽입 및 삭제 용이
index 존재	Node 존재

배열은 index를 가지고 있기 때문에 탐색은 O(1)의 시간복잡도를 가지게 됨.

삽입의 경우는 O(n)의 시간복잡도를 가지게 됨.

Linked List의 탐색은 O(n)의 시간복잡도를 가지게 됨.

삽입의 경우는 O(1)의 시간복잡도를 가지게 됨.

해쉬 테이블

키와 값으로 데이터를 매핑하여 자료를 정리한것을 말함.


fruits = [
  { kind: '🥑', price: 10 },
  { kind: '🍓', price: 8 },
  { kind: '🥕', price: 12 },
];

// 과일 중에서 당근의 가격을 알고 싶을경우 위의 코드로 구현한다면 선형검색으로 찾아야함.

for (const el of fruits) {
  if (el.kind == '🥕') {
    console.log(el.price);
    break;
  }
}

// 즉 하나하나 요소를 검색해보며 찾아야 하기 때문에 시간복잡도는 O(n)이 됨.

따라서 이런 식으로 키를 통해 값을 쉽게 찾을수 있음. 검색 뿐만 아니라 추가 및 삭제도 마찬가지로 O(1)의 시간복잡도를 가지게 됨.


fruits = {
  '🥑': 10,
  '🍓': 8,
  '🥕': 12,
};

console.log(fruits['🥕']); // 12

해쉬 테이블은 여러개의 물건을 일렬로 세우는 것이 아닌, 각각의 바구니에 담는것과 같음.

해쉬 테이블의 원리를 이용하여 빠른 배열 만들기


animal = ['🐶', '🐱', '🐭', '🐯', '🐷', '🐵', '🦄', '🦅'];

// 만약 유니콘(🦄)이 해당 리스트에 있는지 체크하고 싶다면 선형 검색을 해야함.
// 시간 복잡도는 O(n)이 나오게 됨.

따라서 해시 테이블 사용하게 되면 동물들이 키가 되고, 값은 true가 됨. 이렇게 하면 유니콘이 해당 리스트에 있는지 찾는데 단 한번의 단계만 소요됨.


animal = {
  '🐶': true,
  '🐱': true,
  '🐭': true,
  '🐯': true,
  '🐷': true,
  '🐵': true,
  '🦄': true,
  '🦅': true,
};

console.log(animal['🦄']); // true
console.log(animal['🦖']); // undefined