Arrays: Address Calculation and Special Matrices
An array stores elements of one type in consecutive memory locations, so the address of any element can be computed from its indices with a little arithmetic.
DS · Short notes
Data Structures short notes
11 short notes in syllabus order, about 85 minutes to read end to end.
Arrays
Stacks
Stacks
A stack is a collection in which insertions and deletions happen at one end only, called the top. The element removed is always the one inserted most recently: last in, first out (LIFO). A stack of plates is the usual picture.
Stack Applications: Expression Conversion and Evaluation
Arithmetic expressions are usually written in infix form, a + b, with the operator between its operands. Infix needs precedence rules, associativity rules and parentheses to be unambiguous.
Queues
Queues, Circular Queues and Deques
A queue is a collection in which elements are inserted at one end, the rear, and removed from the other end, the front. The element removed is the one that has waited longest: first in, first out (FIFO). A ticket counter line is the usual picture.
Linked lists
Linked Lists
A linked list stores a sequence as separate nodes, each holding an element and a pointer to the next node. Unlike an array, the nodes need not be contiguous, the length can change one node at a time, and inserting or deleting at a known position needs no shifting.
Trees and binary trees
Trees and Binary Trees
A tree is a hierarchical structure made of nodes joined by parent-child links, with one special node, the root, and no cycles.
Binary Tree Traversals
A traversal visits every node of a tree exactly once, in some systematic order. For a binary tree there are three natural depth-first orders, distinguished only by when the root is visited relative to its two subtrees, plus the breadth-first level order.
Binary search trees
Binary Search Trees
A binary search tree (BST) is a binary tree that keeps its keys in order, so that searching can discard one whole subtree at every step. It supports the dynamic-set operations search, minimum, maximum, successor, predecessor, insert and delete, each in time proportional to the height of the tree.
AVL Trees and Balanced BSTs
Search, insertion and deletion in a binary search tree take time proportional to the tree's height h. Inserting keys in sorted order builds a path of height n - 1, so an unbalanced BST can degrade to Θ(n) per operation.
Binary heaps
Binary Heaps
A binary heap is a complete binary tree, stored in an array, in which every parent is at least as large as its children (a max-heap) or at most as large (a min-heap)." The answer sits at the root, and the structure can be repaired in O(lg n) time after an insertion or a removal.
Graphs and their representations
Graph Representations
A graph G = (V, E) is a set of vertices V and a set of edges E, each edge joining two vertices. Graphs model road networks, links between web pages, dependencies between tasks and much more.".