Linked List

A Linked List is a linear data structure, which consists of nodes which point from one to the next to the next.

Variations

• A singly linked list has nodes which only point forward to the next node.
• A doubly linked list has nodes which also point back to the previous node.
• A cyclical linked list is one in which the last node's "next" points to the first node.

Operations and their time complexity (big-o)

There doesn't seem to be consistent terminology accross languages for these operations, so I'm using the names I find most intuitive.

• Prepend:
  • Adds an item to the beginning of the list
  • O(1): Constant time
• RemoveFirst:
  • Removes the first item from the list, and makes the second (if any) the first
  • O(1): Constant time
• Append:
  • Adds an item to the end of the list
  • O(n) in a naive version which traverses the entire list to reach the end
  • O(1) in an optimized version which maintains a reference to the last item
• RemoveLast:
  • Removes the last item from the list
  • O(n) in a naive version which traverses the entire list to reach the end
  • O(1) in an optimized version which maintains a reference to the last item
• Reverse:
  • Reverses the older of the items in the list
  • O(n) because it must traverse the entire list once to reverse it