728x90
[자료구조] 배열, 한 방향 연결리스트, 양 방향 연결리스트 시간복잡도
배열 (Array) |
한 방향 연결리스트 (Singly Linked List) |
양 방향 연결리스트 (Double Linked List) |
|
search | O(1) | O(n) | O(n) |
pushFront pushBack |
O(1) | O(1) | O(1) |
popFront popBack |
O(1) | O(1) | O(1) |
insert | O(n) | O(n) | O(1) ※ splice 연산 활용 |
remove | O(n) | O(n) | O(1) ※ splice 연산 활용 |
데이터의 접근, 탐색이 중요하다면 배열을 쓰는 것이 좋다.
데이터의 추가, 삭제가 중요하다면 연결리스트를 쓰는 것이 좋다.
728x90
'Computer Science' 카테고리의 다른 글
[자료구조] Tree 기본 개념 알아보기 (0) | 2022.05.15 |
---|---|
[자료구조] hash table(해시 테이블) python class 구현하기 (0) | 2022.05.15 |
[자료구조] Double Linked List(양 방향 연결리스트) python class 구현하기 (0) | 2022.05.14 |
[자료구조] Singly Linked List(한 방향 연결리스트) class 구현 (python) (0) | 2022.05.14 |
[자료구조] Linked List(연결리스트)의 특징 (0) | 2022.05.14 |
댓글