1. Advanced Data Structures

A linked list is a sequence of nodes where each node stores a value and a reference (or pointer) to the next node. Unlike arrays, the elements are not stored in one continuous block of memory; each node can live anywhere, and links connect them.

Strengths and Weaknesses

Linked lists make insertion and deletion at known positions (especially at the head) very cheap because you only change a few pointers. However, they are slower for random access because you must walk from the head node to reach a specific index. This trade‑off makes them useful when you care about flexible insertion more than fast indexing.

Common Variants

There are several variants: singly linked lists (each node points only to the next), doubly linked lists (nodes point to both next and previous), and circular lists (the last node links back to the first). Each variant adjusts performance and convenience for different scenarios.

b. Stacks and Queues

Stacks (LIFO)

A stack is a data structure that follows Last‑In, First‑Out (LIFO) behavior. You push items onto the top and pop them off the top. It is like a stack of plates: the last plate you put down is the first you pick up. Stacks are used for function calls, undo operations, and parsing expressions.

Queues (FIFO)

A queue follows First‑In, First‑Out (FIFO) behavior. You enqueue items at the back and dequeue from the front. It is like a line at a ticket counter: the first person in line is served first. Queues are used in scheduling, buffering, and processing tasks in order.

When to Use Which

Use a stack when you need to “remember” things in reverse order, such as tracking nested function calls. Use a queue when order of arrival matters, like processing requests in the order they were received.

Concept and Hierarchy

A tree is a hierarchical structure made of nodes, with a single root at the top and children branching downward. Each node can have zero or more children. Trees naturally model hierarchical relationships like file systems, organization charts, or HTML documents.

Binary Trees and BSTs

A binary tree is a tree where each node has at most two children. A binary search tree (BST) maintains an order rule: left subtree values are smaller, right subtree values are larger. This allows efficient search, insert, and delete operations when the tree is balanced.

Balanced Trees and Use Cases

Balanced trees (like AVL or red‑black trees) automatically keep their height small so operations stay fast. Trees are widely used in indexing, parsers, GUIs, and many system internals where structured, ordered data is needed.

Nodes and Edges

A graph is a set of nodes (vertices) connected by edges. Edges may be directed or undirected, weighted or unweighted. Graphs are more general than trees: there is no single root, and cycles are allowed.

Representations

Graphs are often represented as adjacency lists (for each node, a list of neighbors) or adjacency matrices (a 2D grid marking connections). The choice depends on density: sparse graphs prefer lists; dense graphs sometimes use matrices.

Real-World Uses

Graphs naturally model networks: social networks, road maps, communication networks, and dependency graphs. Many advanced algorithms (shortest paths, connectivity, spanning trees) operate on graph structures.

Key–Value Mapping

A hash table stores key–value pairs and uses a hash function to map keys to positions in an underlying array. This allows average‑case constant‑time lookup, insertion, and deletion, which is extremely powerful for many applications.

Collisions and Handling

Because different keys can hash to the same position, collisions occur. Common collision strategies include chaining (storing a list at each bucket) and open addressing (probing for another bucket). Good hash functions and load‑factor control help keep performance stable.

Practical Uses

Hash tables back many language primitives (like dictionaries or maps). They are ideal when you need fast lookups by key, such as caching, symbol tables in compilers, or configuration maps.