Go to the first, previous, next, last section, table of contents.

Doubly Linked List Overview

Doubly linked lists are the peanut butter sandwich of datastructures: They're not the fanciest or most elegant solution, often, but they're quick to build and will usually do in a pinch, so they get used a lot.

Their biggest disadvantage is that finding an arbitrary given value in a doubly-linked list is normally an O(n) operation, since it requires searching all the entries in the list one by one. (If you rarely need to do this operation, or if your lists are so short that the search time is not an issue, doubly linked lists may be just what the doctor ordered.)

Other disadvantages are that storing a given set of values in a doubly linked list takes several times more memory than just packing them in a vector would, and just finding the nth element of a doubly linked list is an O(n) operation -- whereas it is an O(1) operation in a vector, and an O(n*log(n)) operation in most tree datastructures.

The greatest advantage (other than sheer simplicity) of the doubly linked list is that deleting an element, once you've found it, is an O(1) operation... whereas the same operation on a packed vector is an O(n) operation. (The story is the same for insertion of elements.) Hence, doubly linked lists are particularly appropriate when you expect to be inserting and deleting elements frequently, particularly in the middle of the list.

Go to the first, previous, next, last section, table of contents.