Singly linked list operations complexity
|
Complexity |
|
| Тип |
|
|
| операции |
Только head |
Head + Tail |
| Взять первый |
O(1) |
O(1) |
| Взять последний |
O(n) |
O(1) |
| Вставка в начало |
O(1) |
O(1) |
| Вставка в конец |
O(n) |
O(1) |
| Вставка до заданного |
O(n) |
O(n) |
| Вставка после заданного |
O(1) |
O(1) |
| Удаление первого |
O(1) |
O(1) |
| Удаление последнего |
O(n) |
O(n) |
| Удаление по значению |
O(n) |
O(n) |
| Поиск элемента |
O(n) |
O(n) |
Doubly linked list operations complexity
|
Complexity |
|
| Тип |
|
|
| операции |
Только head |
Head + Tail |
| Взять первый |
O(1) |
O(1) |
| Взять последний |
O(n) |
O(1) |
| Вставка в начало |
O(1) |
O(1) |
| Вставка в конец |
O(n) |
O(1) |
| Вставка до заданного |
O(n) O(1) |
O(n) O(1) |
| Вставка после заданного |
O(1) |
O(1) |
| Удаление первого |
O(1) |
O(1) |
| Удаление последнего |
O(n) |
O(n) O(1) |
| Удаление по значению |
O(n) |
O(n) |
| Поиск элемента |
O(n) |
O(n) |