Basic data structures
Lists, maps, sets, stacks, and queues: what each one is good at, how they look in Python, JavaScript, PHP, and Go, and why picking the right one can make code tens of thousands of times faster.
So far in this series we’ve looked at single values: a number, a string, a boolean. Real programs work with collections: a list of orders, a lookup of prices by product, the set of tags on an article. A data structure is a way of organizing those values so that the things you need to do with them are easy and fast.
You don’t need many. Five cover the vast majority of everyday code: lists, maps, sets, stacks, and queues. This part looks at what each one is good at, and how they appear in Python, JavaScript, PHP, and Go.
Lists (arrays): things in order
A list keeps items in order and lets you get them by position.
prices = [12, 5, 30]
prices.append(8)
print(prices, prices[0], prices[-1], len(prices))
# [12, 5, 30, 8] 12 8 4
Use a list when order matters or when you’ll mostly go through every item. Getting an item by its position is fast. Finding an item by its value is not, because the computer has to check the items one by one (more on that below).
Every language has one: list in Python, Array in JavaScript, slices in Go, and arrays in PHP.
Maps (dictionaries): look things up by key
A map stores key → value pairs, so you can find a value by its key without searching.
stock = {"book": 3, "pen": 10}
stock["mug"] = 2
print(stock["pen"]) # 10
print(stock.get("lamp")) # None
print(stock.get("lamp", 0)) # 0
print(list(stock)) # ['book', 'pen', 'mug']
The Python tutorial explains that “dictionaries are indexed by keys, which can be any immutable type”, and that list(d) “returns a list of all the keys used in the dictionary, in insertion order.” Asking for a key that isn’t there with stock["lamp"] raises a KeyError; .get() lets you choose a fallback instead.
Use a map whenever you find yourself searching a list for “the item whose id is X”. That’s what maps are for.
In JavaScript, use Map. MDN: “The Map object holds key-value pairs and remembers the original insertion order of the keys.” Plain objects also work as maps, but they come with inherited keys. MDN notes that “A Map does not contain any keys by default. It only contains what is explicitly put into it”:
const stock = new Map([["book", 3], ["pen", 10]]);
stock.set("mug", 2);
console.log(stock.get("pen"), stock.get("lamp"), stock.has("lamp"));
// 10 undefined false
const obj = {};
console.log("toString" in obj, new Map().has("toString"));
// true false
In Go, maps are built in. Two details matter. First, a missing key doesn’t fail: “If the requested key doesn’t exist, we get the value type’s zero value.” To tell “missing” from “zero”, use the two-value form, where ok “is true if the key exists in the map, and false if not”:
stock := map[string]int{"book": 3, "pen": 10}
fmt.Println(stock["chair"]) // 0
n, ok := stock["chair"]
fmt.Println(n, ok) // 0 false
Second, order isn’t kept. As the Go blog puts it, “the iteration order is not specified and is not guaranteed to be the same from one iteration to the next.” Two loops over the same map, in the same run:
book pen mug lamp cup
lamp cup book pen mug
If you need a stable order in Go, sort the keys first.
PHP: one array for everything
PHP doesn’t separate lists and maps. The manual says it directly: “An array in PHP is actually an ordered map.” A “list” is just a map whose keys happen to be 0, 1, 2, …
$prices = [12, 5, 30];
$prices[] = 8;
$stock = ["book" => 3, "pen" => 10];
$stock["mug"] = 2;
echo json_encode($prices), " ", json_encode($stock);
// [12,5,30,8] {"book":3,"pen":10,"mug":2}
It’s convenient, with a couple of surprises. Keys that look like whole numbers are converted: “Strings containing valid decimal ints, unless the number is preceded by a + sign, will be cast to the int type. E.g. the key “8” will actually be stored under 8.” So these collide:
$mixed = ["8" => "a", "08" => "b", 8 => "c"];
var_dump($mixed);
// [8] => "c", ["08"] => "b" ← "8" and 8 are the same key
And removing items can leave gaps in the keys, which turns a “list” into a map when you encode it as JSON:
$tags = array_unique(["go", "php", "go", "python"]);
echo json_encode($tags); // {"0":"go","1":"php","3":"python"}
echo json_encode(array_values($tags)); // ["go","php","python"]
That second line is worth remembering if you build APIs in PHP: an API that sometimes returns an array and sometimes an object is a common source of bugs on the client side.
Sets: unique values, fast membership
“A set is an unordered collection with no duplicate elements.” Use one when you care about whether something is present, not where or how many times.
tags = {"go", "php", "go", "python"}
print(sorted(tags), "php" in tags)
# ['go', 'php', 'python'] True
a = {"go", "php"}
b = {"php", "js"}
print(sorted(a & b), sorted(a | b), sorted(a - b))
# ['php'] ['go', 'js', 'php'] ['go']
Sets also give you intersection (&), union (|), and difference (-) for free, which replaces a lot of nested loops.
In JavaScript, a Set value “may only occur once; it is unique in the set’s collection”:
const tags = new Set(["go", "php", "go", "python"]);
console.log(tags.size, tags.has("php")); // 3 true
Go has no set type; the usual approach is a map with bool (or empty) values: map[string]bool. PHP’s closest equivalents are array_unique, or using the values as array keys.
Why the choice matters: list vs set lookup
Checking whether a value is in a list means looking at items one by one. Checking a set (or a map key) jumps almost straight to the answer. The difference grows with the size of the data. On the machine used to write this note, checking for one number 100 times in a collection of a million numbers:
big_list = list(range(1_000_000))
big_set = set(big_list)
# 999_999 in big_list ×100 → 0.5022 s
# 999_999 in big_set ×100 → 0.000011 s
About 46,000 times faster, from changing one line. Exact numbers depend on the machine, but the gap doesn’t. This is the most common performance fix in everyday code: replace “search a list in a loop” with “look up in a set or map”. Part 10 explains why with Big-O notation.
Stacks and queues: order of processing
Sometimes what matters is which item comes out next.
A stack is last in, first out, like a pile of plates. The Python tutorial: “The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved (“last-in, first-out”).” Think of a browser’s back button, or undo:
stack = []
stack.append("page1"); stack.append("page2"); stack.append("page3")
print(stack.pop(), stack) # page3 ['page1', 'page2']
A queue is first in, first out, like a line at a counter. Lists can do it, “however, lists are not efficient for this purpose”, because removing from the front means shifting every other item. “To implement a queue, use collections.deque which was designed to have fast appends and pops from both ends”:
from collections import deque
queue = deque(["order1", "order2"])
queue.append("order3")
print(queue.popleft(), list(queue)) # order1 ['order2', 'order3']
Job queues, message queues, print queues, and “process orders in the order they arrived” are all this structure.
A note on tuples and fixed records
Python also has tuples: like lists, but they can’t be changed after they’re created.
point = (3, 4)
point[0] = 5
# TypeError: 'tuple' object does not support item assignment
They’re good for small fixed groups of values, like coordinates or a (result, error) pair. In Go and PHP, the equivalent is usually a small struct or class with named fields, which is often clearer than remembering what position 0 and 1 mean.
Choosing quickly
| You need to… | Use |
|---|---|
| Keep items in order, go through all of them | List / array |
| Find something by id, name, or code | Map / dictionary |
| Check “is this in there?”, remove duplicates | Set |
| Undo, back, nested processing | Stack |
| Process things in arrival order | Queue |
Why this matters day to day
- Performance. Most slow loops in business code are “for each item, search another list”. A map or set usually fixes it.
- Correctness. Go maps and PHP arrays with gaps don’t behave like ordered lists. If the output order or JSON shape matters, make it explicit.
- Missing keys. Python raises an error, JavaScript and PHP give
undefined/null, and Go gives a zero value. Know which one you’re dealing with before treating0as “not found”. - Readable code.
if tag in allowed_tagswith a set says exactly what you mean.
Try it yourself
- Run the list vs set timing on your own machine, then try it with 10,000 and 10 million items.
- In PHP, create an array,
unset()one item in the middle, thenjson_encodeit. Fix it witharray_values. - In Go, loop over the same map three times and print the keys. Then sort the keys and loop again.
- Find a place in your code that searches a list inside a loop, and rewrite it with a map or set.
Summary
- Lists keep order; maps find by key; sets keep unique values and answer “is it there?” fast.
- Stacks are last in, first out; queues are first in, first out. In Python, use
dequefor queues. - JavaScript’s
MapandSetare cleaner than using plain objects. Go has maps but no sets, and map order is not guaranteed. - PHP’s array is an ordered map; numeric-string keys become integers, and gaps can turn a list into a JSON object.
- Picking a set or map instead of searching a list can be tens of thousands of times faster on large data.
References
- Data Structures, Python tutorial.
- Map and Set, MDN.
- Arrays, PHP Manual.
- Andrew Gerrand, Go maps in action, The Go Blog, February 2013.