• Finding all subsets of a set O(2^n)
• Finding all permutations of a string O(n!)
• Binary search O(log n)
• Sorting using mergesort O(n log(n))
• Iterating over all cells of a matrix (m,n) O(m*n)

Singly Linked List time complexities

• Search O(n)
• Insert at head O(1)
• Inset at tail O(1)
• Remove at head O(1)
• Remove at tail O(n)
• Remove in middle O(n)

Doubly Linked List time complexities

• Search O(n)
• Insert at head O(1)
• Inset at tail O(1)
• Remove at head O(1)
• Remove at tail O(1)
• Remove in middle O(n)

Usage examples

• Undo mechanisms in text editors
• Compiler syntax checking for matching brackets and braces
• Can model pile of objects
• Used behind the scenes to support recursion by keeping track of previous function calls
• Depth First Search (DFS) on a graph

Time complexity analysis (implemented using LinkedList)

• Pushing O(1)
• Popping O(1)
• Peeking O(1)
• Searching O(n)
• Size O(1)

A queue is a linear data structure which models real world queues by having two primary operations enqueue and dequeue.

Usage

• Any waiting line models (lineup at a movie theater, McDonald waiting numbers)
• Can be used to keep track of the n most recently added elements
• Web server request management where you want first come first serve
• Breadth first search (BFS) graph traversal

Time complexity analysis

• Enqueue O(1)
• Dequeue O(1)
• Peeking O(1)
• Contains O(n)
• Removal O(n)
• Is Empty O(1)