Types of Data Structures: Arrays, Linked Lists, Stacks, Queues, Trees, Graphs and Hash Tables

A carpenter doesn't use one tool for every job: a saw cuts, a hammer drives nails, a plane smooths. Programmers also choose different data structures for different jobs. This note introduces each main structure: how it works, what it is good at and where it struggles.

Year 1: The main data structures

Arrays

Picture a row of lockers, each with a number. They are all the same size, side by side, and you can go straight to locker 7 without opening the others. An array is like that: a collection of elements of the same data type, stored in contiguous (next-to-each-other) memory locations under one name. Each element has an index (or subscript), starting from 0, and you reach any element directly by its index, which makes access very fast.

A one-dimensional (1D) array is a single row of values, such as a list of test scores. Parallel arrays use two or more arrays together, where the same index matches the same record (names[5] and ages[5] belong to the sixth person). A two-dimensional (2D) array has rows and columns, like a table or matrix; you need both a row and a column number to reach an element. A 2D array is quicker to process than parallel arrays, but every element must be the same type. 2D arrays store things like the colours of pixels in a picture.

Advantages: fast access by index, efficient use of memory, items stay in order, and simple to use. Disadvantages: a fixed size set in advance, all items must be the same type, inserting or deleting in the middle means shifting other items, and memory can be wasted if the array is bigger than needed.

Linked lists

Now picture a treasure hunt: each clue tells you where to find the next one. A linked list works like this. Each element, called a node, holds some data and a pointer: the address of the next node. The entry point is the head, and the last node's pointer is null (it points to nothing).

To delete a node, you just change the pointer before it to skip over it. To insert a node, you change two pointers so the new node sits in the chain. No data needs to move, only the links. A singly linked list points forward only; a doubly linked list has two pointers per node (previous and next), so it can be walked in both directions, but it uses more memory and code.