[CS] Array, LinkedList
Array
- 배열, 연속된 메모리 주소를 할당받는 정적 자료구조
- 논리적 저장순서와 물리적 저장순서가 동일
- 특정 자료형들이 메모리 공간에서 연속적으로 이루어짐
- immutable 함
- 인덱스로 원소에 접근 가능 -> 인덱스 알고 있다면 O(1)의 시간 복잡도로 접근 가능
- 삭제 또는 삽입 과정에서는 해당 원소에 접근해 작업 완료하고 shift 필요
- 메모리 공간 활용에 제약 존재
LinkedList
- 크기를 정할 필요 없는 동적 자료구조
- 노드가 존재하며 그 안에 데이터와 다음 데이터의 주소 존재
- 논리적 저장 순서와 물리적 저장 순서가 달라 데이터 검색 시 처음 노드부터 순회 필요 -> O(n)
- 메모리 공간 상에서 각 노드들이 연속적이지 않고 흩어져 있어 각 노드가 자신의 다음 노드 위치만 알고 있는 형태
- 사용자는 첫 노드의 위치만을 알고, 각 노드들의 메모리 공간 상의 위치는 각 노드들만 알고 있음
- 원소 삽입, 삭제 시 원소를 찾는데 O(n) + 추가적인 작업 완료에 O(n) 만큰의 시간 발생 -> 검색, 삽입, 삭제 모두 시간 복잡도 O(n)
데이터 접근 속도
- Array : 인덱스를 사용해 빠르게 접근 -> O(1)
- LinkedList : 특정 원소에 접근하기 위해서 처음부터 순차 검색 필요 -> O(n)
데이터 삽입 속도
Array의 경우 데이터를 삽입해 공간이 꽉차면 새로운 메모리 공간을 할당받아 옮겨야 하지만 LinkedList는 그럴 필요 없이 추가할 때마다 동적으로 메모리 공간을 할당받는다.
- Array : 데이터를 중간이나 맨 앞에 삽입할 경우, 이후의 데이터를 shift 하는 추가 과정과 시간 소요
-> O(n)의 시간이 걸리며 데이터가 많은 경우 비효율적이다.
- LinkedList : 중간 삽입 없이 맨 앞/뒤에 삽입 -> O(1)
삽입할 위치를 찾고 삽입 연산을 진행 -> O(n)
Array 보다 빠른 성능을 갖는다.
데이터 삭제 속도
- Array : 해당 위치 데이터 삭제 후 전체적으로 Shift 필요 -> O(n)
- LinkedList : 삭제할 원소를 찾기 위해 O(n)의 시간 복잡도를 갖고 삭제
메모리 할당
- Array : 선언되자 마자 Compile time에 할당 -> 정적 메모리 할당
- LinkedList : 새로운 Node가 추가될 때 runtime에 할당 -> 동적 메모리 할당
>> 삽입과 삭제가 빈번하게 일어나면 LinkedList를 사용하고 데이터에 접근하는 것이 빈번하게 일어나면 Array를 사용하는 것이 좋다.
* Random Access : O(1) 시간에 인덱스로 모든 배열 요소에 접근할 수 있다는 의미