Array vs LinkedList
영어 https://www.javatpoint.com/ds-array-vs-linked-list
한국어 https://medium.com/@audrl1010/linked-list-와-array-차이점-4ba873c2e5f5
1. 특정 Element 검색 시 : Array [O(1)] 승
Array은 Random Access를 지원합니다. element들을 index를 통해 직접적으로 접근할 수 있습니다. ex) arr[0], arr[1] 따라서, 특정 element에 접근하는 시간 복잡도는 O(1)으로 빠르게 찾을 수 있습니다.
LinkedList는 Sequential Access를 지원합니다. 어떤 element/node를 접근할 때 처음 부터 찾는 element에 도달할 때까지 순차적으로 검색하면서 찾아야 합니다. 특정 element에 접근할 때의 시간 복잡도는 O(n)이 됩니다.
데이터 저장 방식
Array 그냥 인접,
LinkList 아무데나 = 주소값만 이전노드에
Array에서 element들은
인접한 memory 위치에 저장 되거나 memory에 연이어 저장됩니다.
LinkedList에서 새로운 element들은 memory 어딘가에 따로따로 저장되며, 새로운 element에 할당된 memory 위치 주소만이 linked list의 이전 node에 저장되어집니다.
Insertion과 Deletion : 저장방식 때문에 LinkList 승
Array에서 삽입과 삭제 연산은 memory 위치가 연속적이고 고정적이기 때문에 많은 시간을 소모합니다.
LinkedList의 경우, 새로운 element는 첫 번째 사용 가능한 빈 Memory 위치에 저장되며, 이전 Node에 Memory 위치의 주소를 저장하는 단 하나의 overhead만이 존재합니다. 따라서 Insertion과 Deletion 연산이 빠릅니다.
메모리 할당 Memory Allocation
Array : 정적 할당
LinkedList : 동적 할당, 새로운 노드가 추가될때 할당됨
어디에 할당되는가 Memory Allocated in Section
Array는 Stack section // LinkedList는 Heap section
Size
array의 size는 반드시 array 선언 시점에 지정되어있어야 함
LinkedList의 size는 다양할 수 있습니다.
node들이 추가될 때 동적으로 메모리가 할당되기 때문
