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.

**Add
**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.

**Get
**From Front: O(1)
From Back: O(1)
At index: O(n) Just like add at a non-front or back index

**Remove
**From front: O(1) just like Add
From back: O(1) See above
At index: O(n)