LinkedList
(single linkedList 기준으로 설명한다.)
각 노드가 데이터와 포인터를 가지고 한줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조.
데이터를 담은 노드가 다음, 이전의 노드 '하나'와 연결되어 있는 것이 반복된다.
특징
-
자료의 주소값으로 노드를 이용해 서로 연결되어 있는 구조를 갖는다.
-
순서가 있지만, index는 없다.
-
크기가 유동적이다.
-
빈 엘리먼트를 허용하지 않는다.
array
번호(index)와 번호에 대응하는 데이터들로 이루어진 자료구조.
일반적으로 같은 종류의 데이터들이 순차적으로 저장되어있다.
특징
-
같은 자료형을 가진 변수를 하나로 묶은 것
(자바스크립트에서는 다양한 자료형이 가능하지만, 권장되지 않는다.) -
index로 해당 원소에 접근이 가능하다. (O(1))
-
메모리 공간을 연속적으로 차지한다.
따라서 논리적 저장 순서와 물리적 저장 순서가 일치한다. -
제한된 크기를 갖는다.
(자바스크립트의 경우 자동으로 늘어나긴 하지만..) -
빈 엘리먼트를 허용한다.
불필요하다면 제거하는 추가 동작이 필요하다.
LinkedList vs array
- 데이터 접근
-
LinkedList
head 원소부터 순차적으로 검색하면서 찾는다.
Random Access 지원. O(n) -
array
index를 사용해 빠르게 접근할 수 있다. O(1)
-
- 데이터 삽입
-
LinkedList
어느 곳에 삽입하든 O(1)의 시간 복잡도를 가진다.
다만 삽입 위치를 탐색해야하기 때문에 O(n) + O(1)이라 맨 앞에 삽입하는 경우가 아니라면 결과적으로 시간 복잡도는 O(n)이다.
메모리를 공간을 동적으로 할당한다. -
array
경우에 따라 다르지만 대부분 삽입 이후 데이터를 한 칸씩 미뤄야하는 과정이 필요하다.
데이터가 많을 수록 비효율이 크게 늘어난다.
최초 메모리 공간이 다 차버리면 새로 공간을 할당받아야한다
-
- 데이터 삭제
-
LinkedList
삽입과 동일한 이유로 삭제 자체는 O(1)의 시간 복잡도를 가지지만, 결과적으로 O(n)이 된다. -
array
데이터를 삭제한 후, 이후 데이터를 앞으로 당겨와야한다. O(n)
-
- 메모리 할당
-
LinkedList
새로운 node가 추가될 때 runtime때 Heap 영역에 메모리 할당 되어 진다.
(동적 메모리 할당) -
array
Array가 선언되자 마자 Compile time때 Stack 영역에 메모리 할당된다.
(정적 메모리 할당)
-
결론
- 삽입과 삭제가 빈번하다면 LinkedList를 사용
- 데이터 접근이 중요하다면 array 사용
개인적으로는 array가 사용하기 더 편하다.
하드웨어가 잘 받쳐주기만 한다면 삽입/삭제의 시간복잡도를 고려하지 않고 특정 요소에 바로 접근할 수 있는 array가 더 사용하기 편한거 같다.
single, double, circular
single 단일
head에서 시작하는 단방향 LinkedList
각 노드가 data, next에 대한 정보를 담고 있다.
double 이중
head, tail 양 쪽에서 시작할 수 있는 양방향 LinkedList
각 노드가 data, pre, next에 대한 정보를 담고 있다.
circular 원형
head와 tail이 연결되어 있는 list
JS, React에서는 배열, 리스트 등을 어떻게 활용하고 있을까
JS에는 브라우저 엔진에 의해 최적화되는 함수들이 존재한다.
이 함수들로 배열 내 객체를 탐색, 정렬, 순회하는 등 다양한 작업을 할 수 있기에 배열은 배열로써 최대한의 기능을 할 수 있다.
JS, React에서 linked list를 구현해 사용할 수 있지만, 굳이 그럴 이유가 없는 듯 하다.
자바스크립트 데이터와 기본 함수들이 이미 최대한의 자유를 보장하고 가변적인 상태를 유지하면서도 최적화 하려는 많은 처리를 해 놓았기 때문에
자바스크립트에서는 기본 함수들을 이용한 로직들을 짠다.
결론 : 지식으로서는 알고 있되, 사용할 일은 없을 듯한 list ..
Queue
Queue는 선입선출 자료구조로 한 줄로 쌓여서 먼저 들어온 요소가 먼저 나가는 구조이다.
in 기존 linkedlist와 동일하게 맨 뒤에 추가되도록 하고
out은 앞(head)를 return한 뒤 다음 next를 head로 만든다.
include는 포함하고 있는지, 있다면 몇 번째인지 알려준다.
Deque
출처
