Set, List, Array, Dictionary - StudyPulse
StudyPulse Logo
Sign Up
Boost Your VCE Scores Today with StudyPulse
8000+ Questions AI Tutor Help
Create Free Account Learn More
Home Subjects Algorithmics (HESS) Set, list, array, dictionary

Set, List, Array, Dictionary

Algorithmics (HESS)

About these notes

Area of Study

Data modelling with abstract data types

Unit

Unit 3: Algorithmic problem-solving

Join StudyPulse

Sign up for a free account to access more study resources and track your progress.

Create Free Account Learn More
Get started in 60 seconds
StudyPulse

Set, List, Array, Dictionary

Algorithmics (HESS)
01 May 2026

Set, List, Array, and Dictionary ADTs

1. Set ADT

A set is an unordered collection of unique elements — no duplicates allowed.

Key Operations

Operator Description
empty → Set Create empty set
insert(Set, Element) → Set Add element (ignored if already present)
remove(Set, Element) → Set Remove element
member(Set, Element) → Boolean Test membership
union(Set, Set) → Set All elements in either set
intersection(Set, Set) → Set Elements in both sets
difference(Set, Set) → Set Elements in first but not second

Properties

  • Unordered: no first or last element
  • No duplicates: inserting the same element twice has no effect
  • Efficient membership testing

Use Case

Tracking visited nodes in a graph traversal. Storing unique usernames.

KEY TAKEAWAY: Use a set when uniqueness matters and order does not.

2. List ADT

A list is an ordered sequence of elements that allows duplicates.

Key Operations

Operator Description
empty → List Create empty list
prepend(List, Element) → List Add to front
append(List, Element) → List Add to back
head(List) → Element Return first element
tail(List) → List Return all except first
isEmpty(List) → Boolean Test if empty
length(List) → Integer Number of elements

Properties

  • Ordered: elements have positions
  • Dynamic size: grows and shrinks
  • Allows duplicates

Use Case

Maintaining an ordered sequence of steps, storing a history of actions.

3. Array ADT

An array is an ordered, indexed collection of fixed size.

Key Operations

Operator Description
create(n) → Array Create array of size n
get(Array, index) → Element Access element at index
set(Array, index, Element) → Array Update element at index
length(Array) → Integer Fixed size

Properties

  • Direct access: any element accessible in $O(1)$ by index
  • Fixed size: size determined at creation
  • Indexed from 0 (or 1 in some pseudocode conventions)

Use Case

Storing tabular data, dynamic programming tables, adjacency matrices for graphs.

EXAM TIP: Arrays differ from lists in that they allow direct indexed access in $O(1)$. Lists may require traversal to find an element.

4. Dictionary (Associative Array) ADT

A dictionary stores key–value pairs, allowing efficient lookup by key.

Key Operations

Operator Description
empty → Dictionary Create empty dictionary
insert(Dict, Key, Value) → Dict Add or update key-value pair
lookup(Dict, Key) → Value Retrieve value for key
delete(Dict, Key) → Dict Remove key-value pair
hasKey(Dict, Key) → Boolean Check if key exists
keys(Dict) → Set Return all keys

Properties

  • Key uniqueness: each key maps to exactly one value
  • Fast lookup: typically $O(1)$ average (hash table implementation)
  • Unordered (unless specified otherwise)

Use Case

Mapping city names to populations, storing adjacency lists for graphs, implementing caches.

# Python dict — the built-in Dictionary ADT
city_pop = {"Melbourne": 5000000, "Sydney": 5300000}
city_pop["Brisbane"] = 2600000
print(city_pop["Melbourne"])  # 5000000

COMMON MISTAKE: Confusing a dictionary with a list. Dictionaries use keys (not integer indices) for lookup, and insertion order is not guaranteed in all implementations.

Comparison Summary

Property Set List Array Dictionary
Ordered No Yes Yes No
Indexed No No (typically) Yes By key
Duplicates No Yes Yes No (keys unique)
Key-value No No No Yes
Dynamic size Yes Yes No Yes

Table of Contents