Overview

  • A head element followed by a series of nodes connected by links.
  • Commonly singly or doubly linked.  Other configurations have been proposed.
  • Can be used to implement other data types including – lists, stacks, queues, associative arrays, and S-expressions.

Advantages

  • Quick inserts and deletes
  • Dynamic size.  Able to grow without having to reallocate the entire data structure.  Able to shrink and return unused space.
  • Insertion and removal from any point in the list in constant time.

Disadvantages

  • Does not allow random access, inherently sequential access.
  • Slow traversal, requires visiting each node in order.
  • Memory and space overhead of pointers – not good for small data loads.

Time Complexities

OperationLinked list
IndexingΘ(n)
Insert/delete at beginningΘ(1)
Insert/delete at end Θ(n) when last element is unknown;
Θ(1) when last element is known
Insert/delete in middlesearch time + Θ(1)
Wasted space (average)Θ(n)

 

Types

 

Singly Linked List

Singly Linked List

Common Operations

Insertion

Deletion

Traversal

Notes

  • Singly linked lists are recursive data structures.  For that reason, many operations have a very simple recursive algorithm.

 

Doubly Linked List

Doubly Linked List

Notes

  • Require more space per node and operations are slightly more expensive.
  • Easier to manipulate, sequential access forwards and backwards.
  • Insertion or deletion in a constant time given only a nodes address.

 

Array Based Linked List

integer listHead

Entry Records[n]

IndexNextPrevData
014Jones, John
1-10Smith, Joseph
2 (listHead)4-1Adams, Adam
3Ignore, Ignore
402Another, Anita
5
6

 

Additional Links

Wikipedia – https://en.wikipedia.org/wiki/Linked_list

Leave a Reply

Your email address will not be published. Required fields are marked *