Quick Introduction to 8 Common Data Structures

1. Array

An array is a fixed‑size structure that stores elements of the same data type and provides random access via indexed positions.

Common operations include traversal, insertion, deletion, search, and update. Arrays serve as the foundation for other structures such as array lists, heaps, hash tables, vectors, and matrices, and they are used in sorting algorithms like insertion sort, quicksort, bubble sort, and merge sort.

2. Linked List

A linked list is a sequential structure composed of nodes, each containing a key and a pointer to the next node; the first node is referenced by a head pointer and the last node is the tail.

Variants include singly linked lists (forward traversal only), doubly linked lists (forward and backward traversal), and circular linked lists (head’s previous points to tail, tail’s next points to head). Operations include search, insertion (at head, tail, or middle), and deletion (from head, tail, or middle).

3. Stack

A stack follows a LIFO (last‑in‑first‑out) order. The two basic operations are push (insert at the top) and pop (remove from the top). Additional utilities include peek, isEmpty, and isFull.

Stacks are used for expression evaluation, implementing recursion, and as the underlying structure for priority queues.

4. Queue

A queue follows a FIFO (first‑in‑first‑out) order. Basic operations are enqueue (add to the tail) and dequeue (remove from the head).

Queues are employed for thread management, scheduling systems, and implementing priority queues.

5. Hash Table

A hash table stores key‑value pairs and uses a hash function to map keys to indices in an array, enabling efficient insertion and lookup.

Hash functions compute an index (hash value) from a key; collisions are resolved with techniques such as chaining or open addressing. Applications include database indexing, associative arrays, and set implementations.

6. Tree

A tree is a hierarchical structure where each node may have multiple children, unlike the linear order of linked lists.

Common variants include binary search trees, B‑trees, red‑black trees, AVL trees, and n‑ary trees. Binary search trees store keys in sorted order, supporting efficient search, insertion, and deletion.

7. Heap

A heap is a specialized binary tree that satisfies the heap property: in a min‑heap each parent’s key is ≤ its children’s keys; in a max‑heap each parent’s key is ≥ its children’s keys.

Heaps can be represented as trees or as arrays. They are used to implement priority queues, perform heap sort, and find the k smallest or largest elements in a dataset.

8. Graph

A graph consists of a finite set of vertices (nodes) and edges connecting pairs of vertices. Graphs can be directed (edges have orientation) or undirected (edges have no orientation).

Applications include modeling social networks, web page linking for search engines, and routing in GPS navigation.