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

Linked List

A linked list is a linear collection of nodes where each node contains a reference (pointer) to the next node, allowing representation of sequences.

Types:

Single linked list: each node points only to the next node; the last node points to null.

Double linked list: each node has two pointers, p to the previous node and n to the next node; the last node points to null.

Circular linked list: each node points to the next node, and the last node points back to the first node.

Time Complexity:

Index: O(n)

Search: O(n)

Insert: O(1)

Delete: O(1)

Stack

A stack is a collection that supports two primary operations: push to add an element on top and pop to remove the top element, following a Last‑In‑First‑Out (LIFO) order.

Time Complexity:

Index: O(n)

Search: O(n)

Insert: O(1)

Delete: O(1)

Queue

A queue is a collection that supports enqueue to add an element at the rear and dequeue to remove an element from the front, following a First‑In‑First‑Out (FIFO) order.

Time Complexity:

Index: O(n)

Search: O(n)

Insert: O(1)

Delete: O(1)

Tree

A tree is an undirected, connected, acyclic graph.

Binary Tree

A binary tree is a hierarchical structure where each node has at most two children, referred to as the left and right child.

Full Binary Tree: every node has either 0 or 2 children.

Perfect Binary Tree: all internal nodes have two children and all leaf nodes are at the same depth.

Complete Binary Tree: all levels are completely filled except possibly the last, which is filled from left to right.

Binary Search Tree (BST)

A BST is a binary tree in which for any node, all values in the left subtree are less than or equal to the node's value, and all values in the right subtree are greater than or equal to it.

Time Complexity:

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 position of a node in the tree determines the key prefix. All children of a node share a common prefix, and the root represents the empty string.

Binary Indexed Tree (Fenwick Tree)

A binary indexed tree (BIT) implements a tree concept using an array. Array indices represent tree nodes; parent and child relationships are derived via bitwise operations. Each element stores a pre‑computed prefix sum, and updates propagate to maintain these sums.

Time Complexity:

Range sum query: O(log(n))

Update: O(log(n))

Segment Tree

A segment tree stores information about intervals (segments) and enables efficient queries and updates over ranges.

Time Complexity:

Range query: O(log(n))

Update: O(log(n))

Heap

A heap is a tree‑based structure that satisfies a specific ordering 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.

Time Complexity:

Index: O(log(n))

Search: O(log(n))

Insert: O(log(n))

Delete: O(log(n))

Extract max/min: O(1)

Hash Table

Hashing maps data of arbitrary length to fixed‑size values using a hash function. Collisions occur when different keys produce the same hash value.

Hash Map: stores key‑value pairs; the hash function determines the bucket index for each key, enabling fast lookup.

Collision Resolution:

Separate chaining: each bucket holds a linked list of entries; lookup time is the bucket access plus list traversal.

Open addressing: on insertion, if 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, where each edge connects two vertices.

Undirected graph: the adjacency matrix is symmetric; an edge between u and v implies an edge between v and u.

Directed graph: the adjacency matrix is not necessarily symmetric; an edge from u to v does not guarantee an edge from v to u.