Data Structures Fundamentals

A data structure organizes information so a program can use it efficiently. The structure does not solve a problem by itself. It gives an algorithm a way to store, find, add, remove, and traverse data.

This course gives you a practical map of the main structures. You will learn the difference between an interface and an implementation. You will also learn to choose a structure from the operations your workload needs.

Start with the interface

An abstract data type, or ADT, specifies values and operations without fixing an implementation. A stack ADT promises operations such as push and pop. It does not require an array or a linked list.

That separation matters. The interface states what your code needs. The data structure states how those operations work in memory. Two implementations can provide the same interface with different time and space costs.

Use this sequence when you choose a structure:

1. Name the data and the operations.
2. Identify which operations dominate the workload.
3. Decide whether order, duplicate values, or key lookup matters.
4. Compare time, memory, and implementation costs.
5. Check the worst case and any assumptions behind an average-case claim.

Arrays and linked lists

An array stores indexed items. An index gives direct access to an item. Arrays are a strong fit when your program often reads or replaces items by position.

Insertion in the middle of an array can require moving later items. A dynamic array adds spare capacity and grows when needed. Appending is then fast when averaged across many appends, though an individual growth can copy the stored items.

A linked list stores each item with a link to the next item. A doubly linked list also links to the previous item. A list can insert or remove near a known node without shifting later items. Finding an item by position still requires following links from a known starting point.

The comparison is about workload, not a universal winner. Choose an array for indexed access and compact sequential storage. Choose a linked list when changes near known nodes matter more than indexed access.

Stacks, queues, and deques

A stack exposes the most recently added item first. This last-in, first-out rule fits nested work, such as tracking active function calls or undoing recent actions. Push adds an item. Pop removes the top item.

A queue exposes the earliest added item first. This first-in, first-out rule fits work that should be handled in arrival order. Enqueue adds at the tail. Dequeue removes from the head.

A deque permits insertion and removal at both ends. It can serve as either a stack or a queue when your program needs both access patterns.

These are interfaces. An array or linked structure can implement them. The required end operations should guide that implementation choice.

Dictionaries, sets, and hash tables

A dictionary maps each key to a value. Its core operations are insert, find, and delete. A set stores distinct keys without associated values in its interface.

A hash table implements a dictionary by using a hash function to map keys to array positions. Two keys can map to the same position. That event is a collision, and the implementation must resolve it.

Hash tables provide expected constant-time basic operations under suitable assumptions. They do not maintain keys in sorted order. If you need minimum, maximum, predecessor, successor, or ordered iteration, an ordered structure is usually a better fit.

Trees and heaps

A tree organizes nodes from a root into parent-child relationships. Trees represent hierarchies directly. Search trees also use ordering rules to support key operations.

In a binary search tree, every key in a node's left subtree is smaller, and every key in its right subtree is larger. The tree's height controls the path length. A balanced search tree keeps height logarithmic, which keeps search, insertion, and deletion logarithmic in the worst case.

A heap is a complete tree with an ordering rule between each parent and child. A min-heap keeps a minimum key at the root. A max-heap keeps a maximum key there. Heaps implement priority queues well because they expose the most extreme priority without fully sorting every item.

A binary heap can live in an array. Its complete shape makes parent and child positions computable from indexes, so it does not need a pointer for every relationship.

Graphs

A graph stores vertices and edges. Use it when relationships form a network rather than one hierarchy. Routes, dependencies, and social connections all have this shape.

An adjacency list stores each vertex with a list of its neighbors. It is compact for a sparse graph, where relatively few possible edges exist. An adjacency matrix uses a two-dimensional table. It spends space on every possible vertex pair but can test a specific edge directly.

The graph representation and the graph algorithm are separate choices. Breadth-first search, depth-first search, and shortest-path methods operate on a representation. Their cost depends in part on how that representation exposes neighbors and edges.

Complexity is a decision tool

Big-O notation describes an asymptotic upper bound on cost as input size grows. It helps you compare operations, but it does not capture every practical factor.

The same structure can have several costs. An array offers constant-time indexed access and linear-time middle insertion. A hash table can offer expected constant-time lookup while retaining a linear worst case. A balanced search tree trades that expected bound for logarithmic worst-case key operations and sorted traversal.

Ask which guarantee your system needs. Average throughput, worst-case latency, memory use, iteration order, and implementation complexity can point to different answers.

Where this course stops

This course builds selection judgment, not implementation mastery. Your next step is to implement each core structure and test its invariants. Then study algorithm analysis, tree balancing, hashing, graph traversal, and structures designed for disks or concurrent programs.