Array

Structure

Indexed set of data elements

Operations

index, search, insert, append, delete

Strengths

Element indexing

Weaknesses

searching, inserting, deleting (all O(n) operations)

Variations

static (fixed size, can’t grow), dynamic (have reserved space for additional elements), multi-dimensional (nested arrays via x,y coordinates)

Video Explanation

Example Problems

Hash Tables/Dictionary

Structure

Unordered set of <key, value> pairs that are mapped using a hash function

Operations

put, get, containsKey, delete

Strengths

All operations are O(1)

Weaknesses

No order to elements, possible hash collisions

Variations

HashSet (all keys are unique), various hash functions that minimize collision probability

Video Explanation

Example Problems

Linked List

Structure

A collection of objects that contain some data and a pointer to the next object in the list

Operations

index, search, insert, append, delete

Strengths

Insertion and deletion (O(1) for both)

Weaknesses

Indexing and searching (O(n) for both)

Variations

Doubly-linked list (pointer to next and previous objects), circular linked list (tail references head object)

Video Explanation

Example Problems

Stack

Structure

A Last In First Out (LIFO) linked list where items can only be added or removed from the head of the list

Operations

insert, pop, search, peek

Strengths

Insertion, popping, peeking (all O(1) operations)

Weaknesses

Search (O(n) operation)

Variations

Fixed-size, dynamically-sized

Video Explanation

Example Problems

Queue

Structure

A First In First Out (FIFO) doubly-linked list where items can only be added from the head and removed from the tail

Operations

insert, pop, search, peek

Strengths

Insertion, popping, peeking (all O(1) operations)

Weaknesses

Search (O(n) operation)

Variations

Circular (tail points to head), Priority Queue (items ordered by priority)

Video Explanation

Example Problems

Graph

Structure

A collection of data nodes (vertices) connected by edges

Operations

insert, delete, search, traverse

Strengths

Representing complex data, insertion, deletion

Weaknesses

Searching, traversal, low scalability

Variations

Cyclic vs. acyclic, directed vs. undirected, connected vs. unconnected, trees, etc. (many variations)

Video Explanation

Example Problems

Tree

Structure

A hierarchical variation of a graph that contains no cycles (i.e. one fewer edges than vertices)

Operations

insert, delete, search, traverse

Strengths

Organizing relational data, insertion, deletion

Weaknesses

Searching (unless Binary Search Tree), traversal, low scalability, unbalanced

Variations

Binary Search, AVL, Self-Balancing, etc. (many variations)

Video Explanation

Example Problems

Heap

Structure

A binary tree where the value of each node is greater than or equal to the value of its children

Operations

insert, extract min/max, heapify

Strengths

Insertion, deletion, sorting with Heapsort

Weaknessess

Searching, requires lot of memory, bad worst-case complexity

Variations

Min heap (smallest element at root), max heap (largest element at root)

Video Explanation

Example Problems