Array(배열)
인덱스와 그 인덱스에 대응하는 데이터들로 이루어진 자료 구조
배열의 종류에는 정적 배열과 동적 배열이 있음
Static Array(정적 배열)
- 크기가 고정되어 있는 배열
- Compile 시 스택(Stack) 영역에 할당됨
- 필요에 따라 배열의 크기를 조절할 수 없음
- 한번 할당하면, 메모리를 추가적으로 할당하거나 해제하지 않아도 됨
- 메모리 할당이 비교적 비효율적이나 속도가 빠르고 구현이 쉬움
- 일반적으로 스택(Stack) 영역에 할당되기 때문에, 최대 크기가 제약됨
Dynamic Array(동적 배열)
- 크기가 고정되지 않은 배열
- Runtime 시 힙(Heap) 영역에 할당됨
- 필요에 따라 배열의 크기를 조절할 수 있음
- 메모리를 추가적으로 할당하므로 부가적인 연산이 추가됨.
- 메모리 할당이 비교적 효율적이나 속도가 느리고 구현이 복잡함
Linked List(연결 리스트)
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조
연결리스트의 종류에는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있음
Singly Linked List(단일 연결 리스트)
- 각 노드에 데이터와 한 개의 포인터가 있고 포인터는 다음 노드를 가리키는 구조
Doubly Linked List(이중 연결 리스트)
- 각 노드에 데이터와 두개의 포인터가 있고 한 개의 포인터는 이전 노드를, 다른 한 개의 포인터는 다음 노드를 가리키는 구조
Circular Linked List(원형 연결 리스트)
- 각 노드에 데이터와 한개의 포인터가 있고 마지막 노드의 포인터는 처음 노드를 가리키는 구조
비교(Array VS Linked List)
Search(검색)
Array
- Arrary는 Random Access를 지원하므로 element들을 index를 통해 직접적으로 접근 가능
- 특정 element 접근하는 시간 복잡도 O(1)
Linked List
- Linked List는 Sequential Access를 지원하므로 element/node에 접근할 때 처음부터 순차적으로 접근하여 찾아야함
- 특정 element 접근하는 시간 복잡도 O(n)
Insert(삽입)
Array
- Array는 데이터들이 순차적으로 저장되어있으므로 맨 처음이나 그 이후에 데이터가 추가될 경우 그 뒤에 있는 데이터들을 모두 한 칸씩 뒤로 미뤄야함
- 추가하려는 데이터가 맨뒤가 아니라면 O(n)의 시간복잡도
- 추가하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남는다면 O(1)의 시간복잡도
Linked List
- 데이터를 추가하는 행위 자체의 시간복잡도는 O(1)
- 데이터의 위치가 맨 처음이 아닌 그 이후라면 순차적으로 탐색하여 해당위치 까지가 가야함
- 추가하려는 데이터의 위치가 맨 앞이라면 O(1)의 시간복잡도
- 추가하려는 데이터의 위치가 맨 앞 그 이후라면 O(n)의 시간복잡도
Deletion(삭제)
Array
- Array는 데이터들이 순차적으로 저장되어있으므로 맨 처음이나 그 이후에 데이터가 삭제될 경우 그 뒤에 있는 데이터들을 모두 한 칸씩 앞으로 당겨야함
- 삭제하려는 데이터가 맨뒤가 아니라면 O(n)의 시간복잡도
- 삭제하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남는다면 O(1)의 시간복잡도
Linked List
- 데이터를 삭제하는 행위 자체의 시간복잡도는 O(1)
- 데이터의 위치가 맨 처음이 아닌 그 이후라면 순차적으로 탐색하여 해당위치 까지가 가야함
- 삭제하려는 데이터의 위치가 맨 앞이라면 O(1)의 시간복잡도
- 삭제하려는 데이터의 위치가 맨 앞 그 이후라면 O(n)의 시간복잡도
저장 방식
Array
- Array에서 element들은 인접한 memory 위치에 저장되거나 memory에 연이어 저장
Linked List
- Linked List에서 새로운 element/node들은 memory 어딘가에 저장
- 새로운 element/node에 할당된 memory 위치 주소는 linked list의 이전 node에 저장
Memory Allocation(메모리 할당)
Array
- Stack section에 메모리 할당이 이루어짐
- Memory는 Array가 선언되자마자 Compile time에 할당
- Static Memory Allocation이라고 부름
Linked List
- Heap section에 메모리 할당이 이루어짐
- Memory는 새로운 node가 추가될 때 runtime에 할당
- Dynamic Memory Allocation이라고 부름
Size(크기)
Array
- Array의 size는 array 선언 시점에 지정
Linked List
- Linked List의 size는 다양할 수 있음
- node들이 추가될 때 runtime 시점에서 size가 커질 수 있기 때문
결론
- 데이터 접근이 중요하다면 Array
- 데이터 수정(삽입 및 삭제)이 중요하다면 Linked List
참조
https://ko.wikipedia.org/
https://medium.com/@audrl1010/linked-list-%EC%99%80-array-%EC%B0%A8%EC%9D%B4%EC%A0%90-4ba873c2e5f5
https://m.blog.naver.com/raylee00/221944085465
