Master Core Data Structures: Linked Lists, Trees, Heaps, and More

Linked List

A linked list is a linear collection of nodes where each node points to the next node, forming a sequence.

Index: O(n)

Search: O(n)

Insert: O(1)

Delete: O(1)

Stack

A stack stores elements with two basic operations: push to add an element on top and pop to remove the top element. It follows Last‑In‑First‑Out (LIFO) order.

Index: O(n)

Search: O(n)

Insert: O(1)

Delete: O(1)

Queue

A queue supports enqueue to add an element at the rear and dequeue to remove the front element, operating in First‑In‑First‑Out (FIFO) order.

Index: O(n)

Search: O(n)

Insert: O(1)

Delete: O(1)

Tree

A tree is an undirected, connected, acyclic graph.

Binary Tree

Each node in a binary tree has at most two children, called left and right.

Variations:

Full binary tree: every node has 0 or 2 children.

Perfect binary tree: all internal nodes have two children and all leaves are at the same depth.

Complete binary tree: all levels are fully filled except possibly the last, which is filled from left to right.

Binary Search Tree (BST)

A BST is a binary tree where each node’s value is greater than or equal to all values in its left subtree and less than or equal to all values in its right subtree.

Index: O(log n)

Search: O(log n)

Insert: O(log n)

Delete: O(log n)

Trie (Prefix Tree)

A trie, also called a radix tree or prefix tree, stores a dynamic set of strings. Nodes do not store the full key; instead, the path from the root to a node defines the key’s prefix. All children of a node share a common prefix.

Binary Indexed Tree (Fenwick Tree)

A binary indexed tree (BIT) implements a tree concept using an array. Array indices represent nodes; parent‑child relationships are derived via bitwise operations. It efficiently maintains prefix sums and supports updates.

Range sum query: O(log n)

Update: O(log n)

Segment Tree

A segment tree stores information about intervals and allows queries over arbitrary segments, such as counting how many intervals cover a point.

Range query: O(log n)

Update: O(log n)

Heap

A heap is a tree‑based structure that satisfies a heap property: in a max‑heap, each parent’s key is greater than or equal to its children’s keys; in a min‑heap, each parent’s key is less than or equal to its children’s keys.

Index: O(log n)

Search: O(log n)

Insert: O(log n)

Delete: O(log n)

Extract max/min: O(1)

Hashing

Hashing maps data of arbitrary length to fixed‑size values. A hash function produces a hash value; collisions occur when different keys produce the same hash.

Hash Map

A hash map stores key‑value pairs by converting keys to bucket indices via a hash function, enabling fast lookup.

Collision Resolution

Separate Chaining : each bucket holds a linked list of entries; lookup time equals bucket access plus list traversal.

Open Addressing : when a bucket is occupied, a probing sequence searches for the next free slot; the final position may not directly reflect the original hash.

Graph

A graph G = (V, E) consists of a set of vertices V and a set of edges E connecting pairs of vertices.

Undirected Graph

Its adjacency matrix is symmetric; an edge between u and v implies an edge between v and u.

Directed Graph

Its adjacency matrix is not necessarily symmetric; an edge from u to v does not guarantee an edge from v to u.