티스토리 뷰
Array vs Linked List
| 비교 | array | linked list |
|---|---|---|
| 검색 | random access 지원index를 통해 직접적으로 접근 가능, O(1) |
Sequential Access 지원처음부터 node를 순회, O(n) |
| 저장 | 논리적 저장순서와 물리적 저장순서가 일치함 | 모두 흩어져서 저장됨[head, [tail]]에서 tail에 연결된 node 정보 저장 |
| 삽입, 삭제 | 데이터를 중간에 삽입 or 맨 앞에 삽입하는 경우 : 이후 데이터를 shift 해야함 -> O(n) | 맨 앞 or 맨 뒤에 삽입 -> O(1) 중간에 삽입 : 삽입할 위치를 검색하고 삽입 -> O(n) |
| 메모리 할당 | Stack에 할당함 compile time에 할당됨 : Static Memory Allocation |
Heap에 할당 runtime에 할당됨 : Dynamic Memory Allocation |
| 크기 | 반드시 array 선언 시점에 지정되야 함, 불변 | runtime 시점에서 사이즈가 커질 수 있음, 가변 |
'CS' 카테고리의 다른 글
| 이진검색 트리 (Binary Search Tree) (0) | 2022.05.02 |
|---|---|
| Tree (0) | 2022.05.02 |
| Stack vs Queue (0) | 2022.05.02 |
| Map (0) | 2022.04.20 |
| 트라이 (Trie) (0) | 2022.04.20 |
댓글