array와 linked list
배열(array)
텍스트배열을 생성하는 시점에는 반드시 배열의 크기를 지정해줘야 하고 그 크리를 변경할 수 없다.
index가 존재하기 때문에 접근과 탐색에 용이하다.
해당 배열 크기 이상의 데이터를 저장할 수 있다.
연결 리스트(linked list)
크기를 미리 정할 필요가 없다.
데이터가 저장되어 있는 Node가 존재한다.
삽입과 삭제가 자유롭다.
임의접근이 불가능하고 데이터 탐색 시 순차적으로 접근해야 한다.
시간복잡도
| array | linked list | |
|---|---|---|
| 탐색 | O(1) | O(n) |
| 삽입 | 맨뒤라면 O(1), 맨 뒤가 아닌 나머지는 O(n) | 맨 앞인 경우 O(1), 맨 앞이 아닌 나머지는 O(n) |
