Big

Singly Linked Lists

  • Insertion - O(1)
  • Removal
    • shift - O(1)
    • pop - O(n)
  • Searching - O(n)
  • Access - O(n)

Doubly Linked Lists

  • Insertion - O(1)
  • Removal - O(1)
  • Searching - O(n)
    • Technically searching is O(n/2), but that's still O(n)
  • Access - O(n)

Stacks (LIFO)

  • Insertion - O(1)
  • Removal - O(1)
  • Searching - O(n)
  • Access - O(n)

Queues (FIFO)

  • Insertion - O(1)
  • Removal - O(1)
  • Searching - O(n)
  • Access - O(n)

Binary Search Trees (BST)

  • Insertion - O(log n)
  • Searching - O(log n)