-
Array
- Array 의 element 들은, 인접한 memory 위치에 저장됩니다.
- 일반적으로 정적 자료구조이다
- 크기를 정해놓고 배열을 만들게 되면 딱 그 크기 만큼 연속된 메모리 주소를 할당
- 크기 수정이 불가하고 배열 크기 이상의 데이터를 저장할 수 없다
- 임의 접근(random access)이 가능
-
LinkedList
- LinkedList 의 element 들은, memory 어딘가에 저장됩니다.
- 연결리스트에는 노드가 존재하는데, 그 노드에는 저장된 데이터 값과 다음 데이터가 있는 메모리 주소(단일 연결리스트의 경우)를 가지고 있다.
- 새로운 요소에 할당된 메모리 위치 주소가 linkedlist의 이전 요소에 저장
-
Array
-
데이터 탐색 : O(1)
-
데이터 추가 : O(n)
추가하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남아있다면, O(1)
-
데이터 삭제 : O(n)
삭제하려는 데이터의 위치가 맨 뒤이고 배열에 공간이 남아있다면, O(1)
-
-
LinkedList
-
데이터 탐색 : O(n)
-
데이터 추가 : O(1) (데이터를 추가하는 행위 자체)
추가하려는 데이터의 위치가 맨 앞이라면, O(1)의 시간복잡도를 가진다.
추가하려는 데이터의 위치가 맨 앞 그 이후라면, O(n)의 시간복잡도를 가진다.
-
데이터 삭제 : O(1) (데이터를 삭제하는 행위 자체)
삭제하려는 데이터의 위치가 맨 앞이라면, O(1)의 시간복잡도를 가진다.
삭제하려는 데이터의 위치가 맨 앞 그 이후라면, O(n)의 시간복잡도를 가진다.
-
-
Array
- 인덱스 접근 가능
- 연속된 메모리에 할당
- 삽입과 삭제가 어렵고 오래 걸림
- 배열의 크기는 고정적
- 공간 낭비 발생 가능
-
LinkedList
- 삽입과 삭제가 용이
- 크기가 가변적
- 불연속적 메모리 할당
- 인덱스 접근이 불가능
- 포인터로 인한 저장 공간의 낭비