The Stack Overflow podcast is back! Listen to an interview with our new CEO.

A linked list is a data structure in which the elements contain references to the next (and optionally the previous) element.

A Linked List is a data structure in which the elements contain references to the next (and optionally the previous) element. Lists, where nodes have links to both the next and the previous element are usually referred to as doubly-linked. Another form of the Linked List is the Circular Linked List, in which the last element contains link of the first element as next and the first element has a link to the last element as previous.

Linked Lists offer \$O(n)\$ insert and removal at any position, \$O(1)\$ list concatenation, and \$O(1)\$ access at the front position (and the back, in the case of doubly-linked lists) as well as \$O(1)\$ next element access. This makes them ideal for sequential operations (and recursive functions operating on sequential data); indexed data structures (e.g. maps, vectors, arrays) can only offer \$O(log \space n)\$ speed.

history | excerpt history