배열(Array)
- 장점
빠른 접근 속도 : 인덱스를 사용하여 원하는 위치의 요소에 바로 바로 접근이 가능하다.
캐시 효율성 증가 : 성능 증가를 위해서는 캐시를 효율적으로 사용하려면 데이터가 지역성을 가져야 한다. 지역성은 데이터가 시간적, 공간적으로 가깝게 일어나는 것을 의미한다. 배열 요소들은 메모리에 연속적으로 저장되므로, 이에 해당된다.
크기 변경이 없는 경우에 유용 : 크기가 고정되어 있는 데이터 집합에 적합하다.
- 단점
크기 변경의 어려움 : 배열의 크기를 변경하기가 어렵다. 크기를 변경하려면 새로운 배열에 기존 요소를 복사해야 한다.
삽입 및 삭제의 비효율: 중간에 요소를 삽입하거나 삭제할 경우에는 뒤의 요소들을 다시 재배치 시켜주어야 한.
- 시간복잡도
접근 (Access): O(1) - 인덱스를 사용하여 직접 접근 가능
삽입 (Insertion) : 가장 마지막 요소: O(1) - 배열의 끝에 요소를 추가하거나 삭제
삭제 (Deletion) : 중간 또는 처음 요소: O(n) - 해당 위치 이후의 요소들을 이동시켜야 함
링크드 리스트(Linked List)
- 장점
동적 크기 조정 : 링크드 리스트는 동적으로 크기를 조절할 수 있다. 요소의 삽입 및 삭제가 쉽다.
요소 삽입 및 삭제의 효율성 : 중간에 요소를 삽입하거나 삭제할 경우에는 해당 위치의 링크만 수정하면 된다.
- 단점
느린 접근 속도 : 특정 위치의 요소에 접근하려면 첫 번째 요소부터 순차적으로 탐색하기에 접근 속도가 느리다.
추가적인 메모리 사용 : 링크드 리스트에는 각 노드마다 데이터와 다음 노드를 가리키는 링크(포인터)가 필요하므로, 배열에 비해 추가적인 메모리 공간이 필요하다.
캐시 효율성 저하 : 링크드 리스트의 요소들은 메모리에 연속적으로 저장되지 않으므로, 캐시 효율성이 낮다.
- 시간복잡도
접근 (Access) : O(n) - 특정 위치에 접근하기 위해 순차적으로 탐색해야 함
삽입 (Insertion) : 가장 마지막 요소: O(1) - 마지막 노드의 링크를 수정하면 됨
삭제 (Deletion) : 중간 또는 처음 요소: O(1) - 해당 위치의 노드의 링크를 수정하면 됨
'공부를 함시다 > 개발 한 스푼' 카테고리의 다른 글
| 멀티프로세스와 멀티스레드 (0) | 2023.06.20 |
|---|---|
| 회선교환과 패킷교환 (0) | 2023.06.19 |