Array vs Linked List

서머스 2022. 9. 23. 17:52

Array

- 메모리 위치가 연속적이다

- 위치 계산이 쉽고 인덱스값으로 쉽게 요소에 접근 가능하다.

장점

- 같은 이름으로 비슷한 타입의 데이터를 여러개 저장할 수 있다.

- 요소에 랜덤하게 엑세스 가능하다. = 원소의 인덱스 값을 알고 있으면 바로 접근 가능 => O(1)

- 사이즈가 고정되어있고 메모리에 연속적으로 저장되기 때문에 메모리 오버플로우가 발생하지 않는다.

- 어떤 데이터든 고정된 사이즈로 저장하기 좋다

- 연속된 메모리 위치에 저장되기 때문에 반복적인 작업을 하기 쉽고 인덱스를 알고 있다면 접근하는데 유닛 타임만 필요하다(연속적으로 접근할 필요가 없다는 의미)

단점

- static하기 때문에 한번 사이즈가 정해지면 고칠 수 없다.

- 연속적인 메모리 위치에 저장되기 때문에 삽입/삭제가 어렵다.

- 어느 원소를 맨 앞에 삽입하게 되면 그 뒤의 원소들의 인덱스를 1씩 shift 해야하므로 => Time Complexity의 worst case는 O(n)

- 어느 원소를 삭제했을 때 그 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 하는 작업이 비용이 많이 든다. => Time Complexity의 worst case는 O(n)

- 사전에 size를 정해야 한다.

- 메모리 낭비가 되기 쉽다.

- 스토리지 구조가 덜 엄격함

- 연속적인 위치에 저장되지 않음 - 추가적인 태그로 다음 요소에 대한 정보를 저장해야 됨

장점

- 사이즈가 동적이다

- 노드의 삽입/삭제가 쉽다 => O(1), but 원하는 위치에 대해 삽입 삭제는 O(n)

단점

- 랜덤 액세스가 허용되지 않는다. 무조건 순서대로 액세스 해야 한다.

- 따라서 binary search 를 할 수 없다.

- traversing하는 시간이 오래 걸린다. => 어떤 원소를 찾을 때 O(n)

- 각각의 요소에 대해 추가적인 메모리가 필요하다.(포인터)

- 포인터로 작업할 때 혼란스럽게 된다.

	Array	Linked List
Size	사이즈 고정	다음 데이터들이 흩어져 있는 형태이기 때문에 사이즈가 dynamic하고 런타임 내 변경된다.
Memory Allocation	컴파일할 때 메모리에 할당됨, 하지만 동적으로 할당된 배열 또한 런타임때 할당됨	런타임 때 할당됨
Memory Efficiency	Linked List보다 메모리를 덜 쓴다	다음 노드의 위치에 대한 값까지 저장해야 하므로 메모리를 더 쓴다. 하지만 유연하게 크기가 바뀌므로 전체적인 메모리 사용량은 적다. 길이에 대한 변화가 클 때는 유용하다.
Execution Time	각각의 요소를 인덱스로 바로 접근 가능하다. 연속적인 메모리 할당으로 인해 성능이 더 늘어난다. 특정 요소 수정 등의 작업이 빠르다.	특정 요소에 도달하기 위해선 사전의 요소들을 거쳐야 한다. 데이터에 요소를 추가하거나 삭제하는 작업이 빠르다
Insertion	느리다 만약 배열이 꽉 찼을 때 새로운 요소를 삽입해야 한다면 배열을 복사한 후 추가해야 한다.	빠르다
Dependency	각각의 요소들이 독립적이다	각각의 요소들이 dependent 하다. 중간에 노드가 사라지면 그 다음 노드를 못 찾게 된다.

- 참고

Linked List vs Array - GeeksforGeeks

Both Arrays and Linked List can be used to store linear data of similar types, but they both have some advantages and disadvantages

www.geeksforgeeks.org