프론트엔드 선형 자료구조
선형 자료구조는 요소를 순차적으로 배열합니다. 각 요소는 하나의 이전 요소와 하나의 다음 요소를 가집니다.
Arrays 배열은 JavaScript의 주요 도구입니다. 연속된 메모리를 사용하므로 인덱스를 통해 어떤 요소든 즉시 접근할 수 있습니다.
push: 끝에 요소를 추가합니다.unshift: 시작 부분에 요소를 추가합니다. 다른 모든 요소가 오른쪽으로 한 칸씩 이동해야 하므로 속도가 느립니다.splice: 임의의 위치에 요소를 추가하거나 제거합니다. 이 메서드는 원본 배열을 변경하므로 순수 함수(pure function)가 아닙니다.
참고: 배열이 너무 커지면 JavaScript는 더 큰 메모리 블록을 할당하고 모든 데이터를 복사해야 합니다. 이는 성능 저하를 초래합니다.
Stacks 스택은 LIFO(Last In, First Out, 후입선출) 규칙을 따릅니다. 쌓여 있는 접시를 생각해보세요. 맨 위에서만 요소를 추가하거나 제거할 수 있습니다.
push: 맨 위에 추가합니다.pop: 맨 위에서 제거합니다.peek: 요소를 제거하지 않고 맨 위의 요소를 확인합니다.
Queues 큐는 FIFO(First In, First Out, 선입선출) 규칙을 따릅니다. 상점의 줄 서기를 생각해보세요.
push: 뒤에 추가합니다.shift: 앞에서 제거합니다.
경고: 대규모 데이터셋에서 배열에 shift를 사용하는 것은 느립니다. 빈 공간을 채우기 위해 모든 요소가 왼쪽으로 이동해야 하기 때문입니다. 데이터 양이 많다면 대신 연결 리스트(linked list)를 사용하세요.
Linked Lists 연결 리스트는 노드(node)로 구성됩니다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가집니다.
- 장점: 위치를 찾은 후에는 노드를 추가하거나 제거하는 것이 빠릅니다. 포인터만 변경하면 되기 때문입니다.
- 단점: 특정 인덱스로 바로 건너뛸 수 없습니다. 헤드(head)부터 시작하여 포인터를 하나씩 따라가야 하므로 속도가 느립니다.
Comparison Summary:
- Arrays: 빈번한 읽기와 작은 데이터에 적합합니다. 접근 시간 복잡도는 O(1)입니다.
- Linked Lists: 빈번한 쓰기와 큰 데이터에 적합합니다. 노드의 위치를 알고 있다면 삽입은 O(1)입니다.
Pro Tips for JavaScript:
- 배열에 여러 데이터 타입을 섞어서 사용하지 마세요. 타입을 통일하면 엔진이 연속된 메모리를 사용하는 데 도움이 됩니다.
- 숫자를 정렬할 때는 항상 비교 함수(comparator function)를 사용하세요.
[10, 2].sort()는 문자열로 정렬하기 때문에[10, 2]라는 결과를 반환합니다. - 대부분의 기본 배열 메서드는 원본 배열을 변경(mutate)한다는 점을 기억하세요.