A linked list stores data within nodes that point to other nodes at its most basic

A node is a data structure that has two parts, the data and a reference to another node

A linked list chains these nodes together

Runtime Complexity

lookup append insert delete

Space Complexity

Special Cases

  • A linked list is empty when head is null.
  • List with only one element.
  • Element activity at the beginning of the list.
  • Element activity at the end of the list.
  • Element that does not exist in the list, thus resulting in no activity.

Restrictions

Can’t use binary search since linked lists does not allow random access

Singly

Non-circular Singly Linked List

Doubly

A doubly linked list has nodes that also references the previous node

Circular

A circular linked list is a linked list whose tail (last node) references the head (first node)

Circular Singly Linked List

Exercises

  • Implement a linked list (with insert and delete functions).
  • Find the nth element in a linked list.
  • Remove the nth element of a linked list.
  • Check if a linked list has cycles.
  • Given a circular linked list, find the node at the beginning of the loop. For example: A-B-C-D-E-C, C is the node that begins the loop.
  • Check whether a link list is a palindrome.
  • Reverse a linked list iteratively and recursively.