Data Structures: Doubly-Linked List Big O
A doubly-linked list is a linked list in which each node has a pointer to the next node and the previous node. Lists such as these usually have both a head and tail pointer which, naturally, points to the first and last node inside the list. Here are the Big O time complexities of some common functions.
**To front: O(1) because we have a pointer to head
To back: O(1) because we have a pointer to tail
Anywhere else: O(n) as we must still traverse the list to find the correct index. Note that it is possible to optimize such a function by traversing from the end of the list if the index were to be past the list’s midpoint and thus claiming a slight performance superiority over a singly-linked list.
**From Front: O(1)
From Back: O(1)
At index: O(n) Just like add at a non-front or back index
**From front: O(1) just like Add
From back: O(1) See above
At index: O(n)