Skip to content
MathSolver Pro
  • Open the math solver
  • Ask the AI tutor
  • Find an AP course
  • Create a quiz
  • Open the calculator
  • Graphing Calculator
  • Browse all calculators
  • Read math guides
↑ ↓Enter to open · Esc to close
Solve a problem
Computer Science1 course

Data Structures

Arrays, lists, stacks, queues, trees, hash tables and graphs.

About Data Structures

Data structures are ways of organising data so that the operations a program needs are fast. Arrays, linked lists, stacks, queues, hash tables, trees, heaps and graphs each trade memory and simplicity for speed on particular operations.

Choosing well depends on complexity analysis. Looking up a key in a hash table takes constant time on average, a balanced binary search tree takes O(log⁡n)O(\log n), and scanning a list takes O(n)O(n). For a million items that is the difference between a handful of steps and a million.

Every large application depends on these choices: databases use trees and hash indexes, browsers keep history on stacks, operating systems schedule work with queues and heaps, and maps and social networks are graphs. Data structures are also a core topic in technical interviews.

Data Structures

How data is organized and what each operation costs. (College)

Arrays and Lists

An array stores a sequence of values in consecutive memory, so any element can be reached instantly by its index. Most languages count from 0, so an array of length nn has indices 00 to n−1n - 1. Reading or writing `a[i]` takes constant time, which is the array's great strength.

Stacks and Queues

A stack is a last-in, first-out (LIFO) collection: you push items onto the top and pop them off the top, like a pile of plates. A queue is first-in, first-out (FIFO): you enqueue at the back and dequeue from the front, like a checkout line. Both restrict access on purpose, which makes them simple, fast and hard to misuse.

Hash Tables

A hash table stores key-value pairs so that looking up a key takes, on average, constant time. A hash function turns each key into an index in an underlying array. Python dictionaries, JavaScript objects and Maps, and Java HashMaps are all hash tables.

Full Data Structures course outline

How to study Data Structures

  • Draw the structure after each operation (insert, delete, rotate) until you can predict the result.
  • For each structure, make a table of the cost of access, search, insert and delete.
  • Implement the basic structures yourself once, even if your language provides them.
  • Match structures to problems: a stack for undo or matching brackets, a queue for breadth-first search, a heap for always taking the smallest item.
Before you start
Introductory programming.
Where it leads
Algorithms, databases and systems courses. A clear mental model of each structure also makes it much easier to read library documentation and to choose the right collection in any language.

Key terms in Data Structures

Array
Items stored in consecutive slots and reached by index in constant time; inserting in the middle means shifting the rest.
Linked list
Nodes that each point to the next, so inserting after a known node is O(1)O(1) but finding the kkth item is O(k)O(k).
Stack
Last in, first out: push adds to the top and pop removes from the top, as in undo history and function calls.
Queue
First in, first out: items join at the back and leave from the front, as in print jobs and breadth-first search.
Hash table
A structure that maps keys to slots with a hash function, giving average O(1)O(1) lookup when collisions are handled well.
Binary search tree
A tree where each left subtree holds smaller keys and each right subtree larger ones, so a balanced tree searches in O(log⁡n)O(\log n).

More in Computer Science