Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 225 ยท Getting Started

Abstract Data Types and Data Structures

Learn the difference between an abstract data type and its implementation, meet the List, Stack, Queue, Map, Set and Priority Queue, and choose by operations.

Ask for "a stack" and you have said what you want without saying how it is built. You want to put things on top, take the top thing off, and peek at it. Whether the thing underneath is an array, a linked list, or something else is a separate decision. That separation between what a structure promises and how it keeps the promise is one of the most useful ideas in computer science.

The promise is an abstract data type (ADT). The way of keeping it is a data structure. This lesson names the standard ADTs, shows two different structures keeping the same promise, and gives you a method for choosing: list the operations you need, then pick the structure where those operations are cheap.

ADT versus data structure

An abstract data type is defined only by its operations and their behaviour: what goes in, what comes out, what rules hold. It says nothing about memory.

A data structure is a concrete way to store the data and carry out those operations, with real costs.

Abstract data type Data structure
Answers What can I do? How is it stored and done?
Example Stack Array-backed stack, linked stack
Describes Interface and rules Memory layout and algorithms
Has a cost? No (only the contract) Yes (time and space)

An everyday analogy: a vehicle has a steering wheel, pedals and a way to go forward. A car, a truck and a golf cart all keep that promise with different engines and different costs. Code that only needs to drive doesn't care which one it is.

The standard ADTs

Here are the six you will meet again and again. The bold names are the operations.

ADT Rule Core operations Typical Python tool
List Ordered items, accessed by position get(i), insert(i, x), remove(i), length list
Stack Last in, first out (LIFO) push(x), pop(), peek(), is_empty() list (end) or deque
Queue First in, first out (FIFO) enqueue(x), dequeue(), peek(), is_empty() collections.deque
Map (dictionary) Keys to values, unique keys put(k, v), get(k), remove(k), contains(k) dict
Set Unique items, no positions add(x), remove(x), contains(x) set
Priority queue Always serves the most important item insert(x, priority), extract_min(), peek() heapq

Related ADTs build on these: a deque (double-ended queue) allows adding and removing at both ends, and a graph or tree models connections.

TEXT
 Stack (LIFO)             Queue (FIFO)                 Priority queue
  push/pop here             dequeue    enqueue           always serves
      |                       |           |              the smallest first
      v                       v           v
   +-------+             +---+---+---+---+---+            insert(7)  insert(2)
   |   c   | <- top      | a | b | c | d | e |            insert(9)  insert(4)
   |   b   |             +---+---+---+---+---+            extract_min() -> 2
   |   a   |             front            back             extract_min() -> 4
   +-------+

One ADT, two implementations

Prove the idea with code. Below, a Stack is defined by an interface (an abstract base class listing the operations), then built twice: once on a Python list, once on linked nodes. Because both keep the promise, the same test code works with either.

Python One Stack interface, two implementations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

reverse_word only knows about the Stack interface. You could swap in a third implementation tomorrow without touching it. That is the practical payoff of abstraction: code depends on the contract, not on the guts. Full stack coverage is in Stacks.

Python usually doesn't need explicit interfaces, because of duck typing: if an object has push and pop, it works as a stack. We used ABC here to make the contract visible and enforced. Try creating Stack() directly and Python refuses.

Costs differ even though behaviour is the same

Both stacks give identical results, but their costs and memory use differ. The list-based stack stores items contiguously, with occasional resizing. The linked stack allocates one node per push and stores an extra reference per item. Both do push and pop in constant time, so for a stack either is fine. For other ADTs the choice matters a lot. A queue built on a plain Python list suffers because removing from the front shifts every item:

Python Queue on a list vs a deque (counting moves)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The list version moved 499,500 items to serve 1,000 dequeues, while the deque moved none. Same ADT, very different structure cost. This is why you pick by operations, as the next section shows. The queue family continues in Queues, and the deque in Deques and Monotonic Queues.

Choosing by operations

Do not start with "which structure do I know?" Start with "what will my program do most?". Write the operations down and compare.

Need Reach for Why
Read or change item by position list / array O(1) index
Add and remove at one end, newest first stack (list) O(1) push and pop at the end
Process in arrival order queue (deque) O(1) at both ends
Look up a value by key dict about O(1) lookup
Test membership, remove duplicates set about O(1) membership
Always need the smallest or largest priority queue (heapq) O(log n) insert and extract
Keep items sorted, search quickly sorted list + bisect, or a tree O(log n) search
Model connections graph (dict of lists) edges are first-class
Python Same job, three structures

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same holds for the Map ADT. A map can be built on an unsorted list of pairs (every lookup scans) or on a hash table (a lookup jumps to its slot). Count the comparisons the list version needs, and try to instantiate the abstract class too:

Python Map ADT on a list of pairs, and an abstract class (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The list-backed map needed 20,100 comparisons for 200 lookups (1 + 2 + ... + 200), while a dict does one hash lookup per key. Same promise, very different cost; Hash Tables shows how the dict achieves it.

Classifying data structures

Structures are grouped in a few useful ways. You will see these words in every later lesson:

TEXT
Data structures
|
+-- Linear (items in a sequence)
|     +-- Array-based:  array, dynamic array (list), string
|     +-- Linked:       singly / doubly / circular linked list
|     +-- Restricted:   stack, queue, deque
|
+-- Non-linear (items related in other ways)
|     +-- Hierarchical: tree, binary search tree, heap, trie
|     +-- Networked:    graph
|
+-- Associative (by key, not position)
      +-- Hash-based:   hash table, dict, set
      +-- Ordered:      balanced search trees
  • Linear vs non-linear: does each item have at most one previous and one next?
  • Static vs dynamic: fixed size at creation, or can grow and shrink?
  • Homogeneous vs heterogeneous: all items of one type, or mixed? Python lists allow mixed types, though uniform data is easier to reason about.
  • Primitive vs composite: numbers and booleans versus structures built from other values.

One more distinction pays off later: mutable vs immutable (persistent). An immutable structure never changes once built; every update returns a new version. Tuples and strings are immutable; lists and dicts are not.

Common mistakes

  • Mixing up ADT and implementation. "A stack is an array" is wrong; an array is one way to build a stack.
  • Using a list as a queue with pop(0) on large data. Use collections.deque.
  • Choosing by habit. Always list the operations first.
  • Ignoring the constraints such as size and how often each operation runs. A structure that is perfect for 100 items may be wrong for 10 million.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which statement best describes an abstract data type?

    An ADT specifies behaviour (operations and their rules), not storage. Data structures are the concrete implementations.
  2. 2. A stack serves items in which order?

    A stack removes the item most recently pushed, so the last item in is the first out.
  3. 3. Why did ListQueue shift 499,500 items for 1,000 dequeues?

    Removing the front of a list shifts every later item one place. Dequeuing 1,000 items shifts 999 + 998 + ... + 0 = 499,500 items in total.
  4. 4. You must repeatedly retrieve the smallest of a changing collection. Which ADT fits best?

    A priority queue is designed to give the minimum (or maximum) quickly, usually implemented as a heap. Python offers heapq.
  5. 5. What is the main benefit of coding against an interface such as Stack?

    Depending on the contract instead of the implementation lets you replace one structure with another with no changes to client code.

Summary

  • An ADT defines operations and rules; a data structure is a concrete implementation with real costs.
  • The standard ADTs are list, stack, queue, map, set and priority queue, with deque, tree and graph building on them.
  • The same ADT can have several implementations (array or linked stack) with identical behaviour and different costs.
  • Choose by operations first: what you do most decides the structure.
  • A list used as a queue pays to shift items on every dequeue; collections.deque avoids that.
  • Structures are classified as linear or non-linear, static or dynamic, mutable or immutable.

Next: How to Solve Algorithm Problems, a repeatable method for turning a problem statement into tested code.