Fundamentals of Data Structures: An Algorithmic Approach

Explore the basics of a single linked list by creating nodes, performing insertion and deletion, and looking up elements, with each node containing data and a next address.

Learn to build a single linked list by initializing the head pointer and the last pointer, reading data, creating nodes, and linking them while updating the head and last.

Demonstrate the insertion operation in a single linked list, including insert first and insert after, using a four-node example (5, 10, 20, 40).

Demonstrates deleting the first node and deleting after a given node in a single linked list. Shows updating the head and links and freeing the removed node.

Traverse a single linked list with a header pointer, printing each node’s data (5, 10, 20, 40) as you move to the next node until null.

Learn how stacks, a specialized list, support push and pop operations at one end, enabling last-in, first-out access and common applications.

Explore stack operations with push and pop, understand top, empty, and full conditions, and recognize overflow and underflow; see how stacks support recursion and infix to postfix conversions.

Explore infix to postfix conversion with a stack-based algorithm, resolving operator precedence and parentheses. See why postfix simplifies machine evaluation and how a b + c * emerges.

Evaluate postfix expressions using a stack by pushing operands, and when encountering operators, pop two values, apply the operator, and push the result until a final value remains.

Understand how a queue, a specialized list (linked or sequential), uses rear and front pointers for insertion and deletion, following first in, first out.

Learn how to implement a linear queue on a sequential list, initialize front and rear to minus one, determine empty and full conditions, and perform enqueue and dequeue operations.

Reuse empty spaces in a circular queue after deletions by wrapping the rear pointer with modulo size, using front and rear pointers to manage insertions and deletions, and empty-full conditions.

Define a tree as a collection of nodes with a designated root, partitioned into disjoint subtrees, where leaf nodes have no children.

Learn that a binary tree is a subclass of trees consisting of nodes with a designated root, whose remaining nodes split into two disjoint subtrees: left and right.

Discover how a binary search tree enforces that left subtree values are less than the root and right subtree values are greater, enabling efficient key searches, insertions, deletions, and traversals.

Demonstrate inserting data items into a binary search tree by creating nodes, starting with a null root, and placing each new node by comparing values and linking left or right.

Delete a binary search tree node by handling leaf, single-child, and two-child cases; use a dummy root to simplify deletions and attach with the rightmost node of the left subtree.

Discover inorder traversal of a binary search tree, visiting left subtree, then the node, and finally the right subtree using a recursive algorithm.

Construct a binary tree from given inorder and preorder traversals by identifying the root from preorder, splitting by inorder into left and right subtrees, and recursively applying the same process.

Define a graph as a set of vertices and edges, undirected or directed, and compare adjacency matrix and adjacency list representations by random access, memory usage, and order.

Explore depth first search, a recursive graph traversal that visits all reachable vertices and builds a dfs spanning tree, using an adjacency list and a visited array.

Explore breadth-first search, which uses a queue to visit all graph vertices from a starting vertex, marks visited nodes, and yields a BFS spanning tree.

Explore the linear search algorithm, which checks each element one by one to find a target, and compare it with binary search, noting best, worst, and average-case complexities.

Demonstrates how binary search finds a target in a sorted array by updating lower bound, upper bound, and mid, and explains its log base two time complexity.

Learn how sorting rearranges data into ascending or descending order for faster binary search. Explore bubble sort, selection sort, and insertion sort as techniques to sort information and improve organization.

This lecture explains bubble sort by repeatedly comparing adjacent elements, swapping out-of-order pairs, and moving the largest element to the end each pass, with early termination if no swaps occur.

Selection sort is a simple comparison-based algorithm that repeatedly selects the minimum from the unsorted portion and swaps it into place, yielding O(n^2) time.

Demonstrates insertion sort as a comparison-based algorithm that inserts each key from the unsorted part into the position by shifting larger elements, with best case O(n) and worst case O(n^2).