What Is a Data Structure? Types, Examples and Real Timings

A data structure is a way of storing data in a computer's memory so that a program can find, add, remove or change items efficiently. The structure decides which operations are cheap. Asked whether one value is among a million, a Python list took 3,540 microseconds and a set took 0.028, in the timings below. Same data, same question, different structure.

What is a data structure, in simple words?

Think of a thousand books. Piled on the floor, finding one means picking through the pile. Shelved alphabetically by author, you walk to the right shelf. Same books, same information; a different arrangement, and a different cost for the one thing you keep doing. A data structure is that arrangement, chosen for the operations a program performs most.

Every data structure has two parts: a layout in memory, and the set of operations it supports with a known cost. An array keeps items side by side, so jumping to item 500 is one step; inserting at the front means shifting everything. A hash table scatters items by a computed address, so a lookup is one step, but the items have no order. Choosing a structure means choosing which operations you want to be fast.

The subject is usually taught with algorithms, as "DSA", because the two are chosen together. The algorithm is the sequence of steps; the data structure is what the steps run on. Binary search is a fast algorithm only on a sorted array, and a queue is useful only with an algorithm that takes items in arrival order. The Python tutorial's chapter on data structures shows the same idea with lists, sets and dictionaries.

What are the types of data structures?

Textbooks sort them two ways. Primitive structures are the single values a language gives you: integers, floating-point numbers, characters, booleans. Non-primitive structures are built from those: arrays, linked lists, stacks, queues, hash tables, trees and graphs. Non-primitive structures split again into linear, where items sit in one sequence, and non-linear, where an item can connect to several others.

The right-hand column matters more than the classification. Students memorise "linear versus non-linear"; working programmers remember "what is this fast at". The sections below take each structure in the order most courses teach them, and the timing section puts numbers on the claims.

What operations do data structures support?

The same six operations come up on every structure, and the cost of each is what separates them: traversal (visit every item), search (find one item), insertion, deletion, sorting and merging. Costs are written in "Big O" notation, which says how the time grows with the number of items, n. O(1) means the same time however much data there is. O(n) means the time grows in step with the data. O(log n) means doubling the data adds one step.

These are not abstractions. Python's own developers publish the cost of every operation on the built-in types, and the list page says why: "Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move)." That page is the source for the table below.

Python's TimeComplexity page on October 7, 2026: a list is an array, so Get Item is O(1) while Insert and Delete Item are O(n).

What is an array?

An array is a block of items stored side by side in memory, each the same size. Because item k sits at a fixed offset from the start, reading or changing it is one calculation, however long the array is. That is the O(1) "Get Item" in Python's table. The price is paid on insertion and deletion anywhere but the end: every later item has to move one place.

A Python list is a dynamic array, one that grows by allocating a bigger block when it fills. Strings are arrays of characters, which is why our regex cheat sheet is really a guide to searching one particular array. Arrays are the default structure: when nothing else is obviously right, a sorted array plus binary search solves a surprising number of problems.

prices = [120, 95, 230, 88]
prices[2]          # 230, one step however long the list is
prices.append(150) # cheap: there is room at the end
prices.insert(0, 5)  # expensive: all four items shift right

What is a linked list in data structure?

A linked list stores each item in its own node, together with a pointer to the next node. The nodes can live anywhere in memory. To insert an item after a node you already hold, you change two pointers, and nothing else moves, so the operation is O(1). To reach item number k you have to follow k pointers from the head, which is O(n), the exact opposite of an array.

A singly linked list points forward only. A doubly linked list points both ways, so you can walk backwards and delete a node you hold in O(1). A circular list links the last node back to the first. Python's collections.deque is built from a chain of small arrays, which gives it O(1) at both ends; the TimeComplexity page warns that even looking at its middle is slow.

class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next

head = Node("a", Node("b", Node("c")))
# insert "x" after "a": two pointer changes, nothing shifts
head.next = Node("x", head.next)

What is a stack in data structure?

A stack holds items so that the last one added is the first one out: LIFO. It supports three operations, all O(1): push an item onto the top, pop the top item off, and peek at the top without removing it. Nothing else is reachable, and that limit is the point. A stack models anything that unwinds in reverse order.

Your program is running on one now. Every function call pushes a frame holding its local variables, and returning pops it; a function that never returns overflows the call stack. Undo in an editor is a stack of edits. The back button is a stack of pages. Matching brackets is a stack: push each opener, pop on each closer, and the expression is balanced if the stack ends empty. In Python a list is a stack, since append and pop both work at the end in O(1).

def balanced(expr):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

balanced("f(a[0], {b: 1})")  # True
balanced("f(a[0)]")          # False

What is a queue in data structure?

A queue holds items so that the first one added is the first one out: FIFO. You enqueue at the back and dequeue from the front. A print queue, a request queue on a web server, the order in which a breadth-first search visits nodes, and the ready queue an operating system picks the next process from are all queues. A circular queue reuses an array's slots by wrapping the front and back indices around, so it never needs to shift items. A priority queue hands out the most urgent item rather than the oldest; it is usually a heap, covered under trees.

A Python list is the wrong structure for a queue, and the official tutorial says so: "doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one)." It recommends collections.deque, "which was designed to have fast appends and pops from both ends". The tutorial section is short and worth reading once.

The Python tutorial on October 7, 2026: a list is "not efficient" as a queue; use collections.deque instead. In the timing below the difference was 457 times.

from collections import deque

jobs = deque()
jobs.append("print report.pdf")   # enqueue at the back
jobs.append("print invoice.pdf")
jobs.popleft()                    # dequeue from the front: 'print report.pdf'

What is hashing in data structure?

Hashing turns a key into a number, and that number says where in an array the key's value is stored. A hash function does the turning; a hash table is the array plus the function. To store "alice", hash it to, say, slot 7,213 and put the value there. To find "alice" later, hash it again and look in slot 7,213. There is no searching, which is why lookup, insertion and deletion are O(1) on average whatever the table's size.

Two keys can hash to the same slot; that is a collision, and every hash table has a plan for it. Chaining keeps a short list in each slot. Open addressing steps to the next free slot. A good hash function keeps collisions rare, and Python's own figures assume one: the average-case times for a dict hold for a hash function good enough "to make collisions uncommon". Python's dict and set are hash tables, and the same page lists their operations.

Python's TimeComplexity page on October 7, 2026: a dict's Get Item, Set Item and Delete Item are O(1) on average, with O(n) as the worst case when collisions pile up.

What hashing gives up is order. A hash table cannot tell you the smallest key, the next key after "alice", or every key between two values, without visiting all of them. When you need those questions answered, you want a tree.

ages = {"alice": 31, "bob": 27}   # a hash table
ages["carol"] = 45                 # hash "carol", store at its slot
"bob" in ages                      # hash "bob", look in one slot: True

What is a tree?

A tree is a hierarchy: one root node, each node holding links to its children, every node except the root having exactly one parent. Nodes with no children are leaves. The height is the longest path from root to leaf. A file system is a tree. So is the HTML of this page, which browsers call the DOM, and so is the structure a compiler builds from your source code before it checks it.

A binary tree allows at most two children per node. A binary search tree (BST) keeps every key in the left subtree smaller than the node and every key in the right subtree larger, so a search halves the remaining tree at each step: O(log n) when the tree is balanced. The catch is balance.

Insert sorted keys into a plain BST and it degenerates into a linked list, O(n). AVL trees and red-black trees rebalance themselves on every insert, and B-trees, with many keys per node, are what databases use: SQLite stores every table and index as a B-tree.

A heap is a binary tree with one rule: each parent is smaller than (or equal to) its children. The smallest item is therefore always at the root, and adding or removing an item costs O(log n). That makes a heap the usual priority queue. Python ships one as heapq, and in the timings below it beat a kept-sorted list by a hundred times. The three classic traversals of a binary tree, in-order, pre-order and post-order, differ only in when the node itself is visited; in-order on a BST yields the keys sorted.

class Tree:
    def __init__(self, key, left=None, right=None):
        self.key, self.left, self.right = key, left, right

def in_order(node):
    if node:
        yield from in_order(node.left)
        yield node.key
        yield from in_order(node.right)

bst = Tree(8, Tree(3, Tree(1), Tree(6)), Tree(10, None, Tree(14)))
list(in_order(bst))   # [1, 3, 6, 8, 10, 14]: a BST read in order is sorted

What is a graph?

A graph is a set of nodes (vertices) and edges that connect pairs of them, with no rule about hierarchy. Edges can be directed (a follows b) or undirected (a and b are friends), and can carry weights (the road is 12 km). A map is a graph, a social network is a graph, the links between web pages are a graph, and the dependencies between the packages in your project are a graph.

Graphs are stored two ways. An adjacency matrix is an n-by-n grid of yes/no cells: simple, but n² memory. An adjacency list keeps, for each node, the list of its neighbours, which is what almost everyone uses. Questions about graphs are algorithms: breadth-first search, which uses a queue, finds the fewest hops; depth-first search, which uses a stack, finds whether a path exists at all; Dijkstra's algorithm, which uses a heap, finds the shortest weighted route.

from collections import deque

roads = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}  # adjacency list

def hops(graph, start, goal):
    seen, queue = {start}, deque([(start, 0)])
    while queue:                       # breadth-first: a queue
        node, n = queue.popleft()
        if node == goal:
            return n
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt); queue.append((nxt, n + 1))

hops(roads, "A", "D")   # 2

Where do searching and sorting fit in?

Courses teach them beside the structures because they are what the structures are for. Linear search reads items one by one and costs O(n) on anything. Binary search needs sorted data and costs O(log n): it looks at the middle, discards the half that cannot contain the target, and repeats, so 100,000 items take about 17 looks. Sorting a general list costs O(n log n) at best, which is what Python's built-in sort achieves; the TimeComplexity page lists it as O(n log n). Sorting once and searching many times is therefore a data structure in its own right, and the timing below puts a number on it.

Which data structure is fastest? The same job, timed

Big O says how cost grows; it does not say what you will feel. So the table below is the same job on two structures each, timed in Python 3.12.4 on an Apple Silicon Mac, median of five rounds. The script is bench.py and is described at the end. Every structure is a Python built-in, so the numbers measure the structure and not a library. Times are for the whole batch of operations, with the per-operation figure in the text; the published costs predict every row.

The benchmark's own output file, summary.json, as written on October 7, 2026 by Python 3.12.4 on an arm64 Mac. Each figure is the median of five rounds.

Read the first row per operation, against Python's published costs: each list lookup took 3,540 microseconds, because half the values we asked about were not in the data and the list had to be read to its end; each set lookup took 0.028 microseconds, because the value's hash said where to look. The front-insert row is the sentence from the Python wiki made visible: 57 microseconds per insert into a list, where 100,000 items shift right each time, against 0.02 for a deque. The dict row is hashing again: 525 microseconds to scan pairs for a key, 0.027 to hash it.

The last two rows show that even a plain sorted list is a structure: binary search on it is 1,737 times faster than scanning, and a heap beats keeping it sorted a hundredfold when the job is "always give me the smallest".

Two cautions. These ratios depend on the data size; at ten items every structure is fast and the simplest one wins. And a hash table's O(1) assumes a good hash function and spare slots; Python's figures give O(n) as the worst case for a dict for that reason. Measure your own case before you redesign anything.

How do you choose a data structure?

Start from the operation you will perform most, not from the data:

• Look things up by a key, in any order: hash table (dict, set).

• Read items by position, mostly append at the end: array (list).

• Take items in arrival order: queue (deque).

• Take the most recent item first, or unwind something: stack (list).

• Add and remove at both ends, or in the middle of something you are walking through: deque or linked list.

• Repeatedly take the smallest or most urgent item: heap (heapq).

• Keep items sorted and ask range questions ("everything between 10 and 20"): sorted array with binary search if it changes rarely; a balanced tree if it changes often.

• Represent a hierarchy: tree. Represent arbitrary relationships: graph.

When two fit, take the simpler one and measure. A sorted list with bisect handles more than people expect, and a dict handles most of the rest. Hand-written linked lists and trees are for when the measurement says the built-ins are the bottleneck, which in application code is rare.

Examples of data structures in real software

• Hash tables: every JSON object your code receives from an API becomes one; so do caches, symbol tables in compilers and the index a database keeps for equality lookups.

• Stacks: function calls, undo and redo, the browser's back button, evaluating arithmetic expressions, matching brackets in an editor.

• Queues: print jobs, web server requests, message queues between services, the scheduler's ready queue in an operating system, breadth-first search.

• Trees: file systems, the DOM, database indexes (B-trees), the parse tree of every program you compile, the Huffman tree inside a zip file.

• Graphs: maps and routing, social networks, package dependencies, the web itself, and the networks that machine learning models are built as.

• Arrays: images (a grid of pixels), audio (a sequence of samples), strings, and the tensors that machine learning frameworks compute on.

How should you learn data structures and algorithms?

In the order above, which is the order almost every university course and the ranking lecture notes use: arrays and strings, then linked lists, stacks and queues, then hashing, then trees, then graphs, with searching and sorting alongside. Implement each one once by hand in whatever language you know, so you have felt where the cost is, then use the standard library's version from then on. Measure as you go; a timing script like the one here is twenty lines, and one measured surprise teaches more than a chapter of Big O.

How these timings were measured

The benchmark is a plain Python script, bench.py, run on 7 October 2026 with CPython 3.12.4 on an arm64 Mac running macOS (Darwin 25.6.0), using time.perf_counter. For each job it builds both structures from the same data, runs the batch of operations on each, repeats that five times and reports the median. The data is generated with a fixed random seed so a rerun gives the same shape of result.

Nothing outside the standard library is used: list, set, dict, collections.deque, bisect and heapq, all documented on docs.python.org. The script and its raw output are kept with the article's draft, and summarize.py produces the file in the screenshot from the raw output.

Frequently asked questions

What is a data structure in simple words?

A chosen way of arranging data in memory so that the operations you need are fast. A list, a dictionary and a queue are all data structures; each makes a different operation cheap.

What are the two main types of data structures?

Linear structures, where items form one sequence (arrays, linked lists, stacks, queues), and non-linear structures, where an item can connect to many others (trees, graphs, and hash tables, which have no order at all). Textbooks also split primitive types (integers, characters) from the non-primitive structures built out of them.

What is the difference between a data type and a data structure?

A data type says what a single value is and what you can do with it: an integer, a character. A data structure organises many values and defines operations over the collection: a list of integers, a tree of characters.

What is the difference between a data structure and a database?

A database is a program that stores data on disk and answers queries about it; inside, it is built from data structures. SQLite keeps each table and index as a B-tree, and most databases keep hash indexes for equality lookups. A data structure lives in a program's memory; a database outlives the program.

What is the full form of DSA?

Data Structures and Algorithms. The two are taught together because an algorithm's cost depends on the structure it runs on, and a structure is only useful with an algorithm that exploits it.

Which language is best for learning data structures?

The one you already know. Python shows the ideas with the least code, and every timing in this article used its built-ins. C makes the memory visible, which is why university courses in India mostly use C or C++. Java is common in interviews. The structures are identical in all of them.

Is DSA hard?

The ideas are not; there are about eight structures and most are a few lines of code. What takes practice is recognising which one a problem wants, and that comes from implementing each one once and measuring, not from reading definitions.