Data structures exist in both the digital and physical worlds. A dictionary is a physical example of a data structure where the data comprises word definitions organized in alphabetical order within a book. This organization allows for a specific query: given a word, one can look up its definition.
At its core, a data structure is a method of organizing data that facilitates specific types of queries and operations on that data.
We'll begin by covering linear data structures like arrays, lists, queues, and stacks. We'll then circle back to explain the difference between linear and non-linear structures before diving into hash tables, trees, and graphs.
If you want to learn more, check out this course on data structures and algorithms in Python.
Arrays
Arrays are fundamental data structures widely available across programming languages. They enable the storage of a fixed number (N) of values sequentially in memory.
Array elements are indexed from the first element at index (0) to the last element at index (N-1).

They allow the following operations:
- Read the value at a given index.
- Update the value at a given index.
- Iterate over all stored values.
- Obtain the size of the array.
Arrays are highly effective in scenarios where the number of values to be stored is known in advance, and the primary operations involve reading and writing data at specific indexes.
Consider a scenario in which you need to store daily temperature readings for the month of December. You might want to enable users to retrieve the temperature for a specific day and perform various statistical analyses on the temperatures throughout the month.
Since the number of days in December is known in advance to be 31, arrays are an excellent choice for storing the temperature readings. Initially, one would create an array with 31 empty positions. Then, after obtaining each temperature reading, the temperature for a given day would be assigned to the corresponding array index: day 1 would be stored at index 0, day 2 at index 1, and so on, until day 31, which would be stored at index 30.

Accessing the corresponding index allows retrieval of the temperature for a specific day. Statistics, such as the average temperature, can be determined by iterating over all elements, maintaining a cumulative sum, and then dividing by the array's size.
Arrays are not natively available in Python. They are used behind the scenes as the underlying structure for various data types but are not directly supported in the language. To use arrays explicitly, one can utilize libraries such as array, which offer an array implementation. However, it's often more practical to use a list with a fixed size in situations where an array might be required. Lists offer flexibility and are a core part of Python's functionality, as we'll discuss next.
We can create a list to simulate an array of 31 elements, each initialized to None, by using [None] * 31. Here, None indicates that no temperature reading has been recorded yet.
december_temperatures = [None] * 31
To set the value at a specific index, we use december_temperatures[index], where index is a number from 0 to 30. For example, to record the temperature for the first day (stored at index 0), we would do it like this:
december_temperatures[0] = 15
Accessing a temperature is similarly straightforward, using december_temperatures[index].
print(december_temperatures[0])
Lists
Imagine now that, instead of focusing on December, we install a sensor somewhere to take periodic temperature readings over an unspecified period. In this scenario, using an array isn't the best option because we might run out of space due to its fixed size upon creation.
A more suitable data structure in this scenario would be a list. There are two kinds of lists:
Array lists
Array lists can be seen as a more flexible version of arrays. They can perform all the functions that arrays do but also append new values, so their size isn't fixed upon creation. Array lists correspond to using list() in Python.
Their implementation relies on using an array that's expanded when space runs out, hence the name array list. However, as we learned earlier, arrays cannot grow, so how is this possible?
When the underlying array of an array list is full, and we want to append a new value, a larger array is created under the hood. All the previous values are copied into this new, bigger array. Then, the new value is added at the first available position in the new array.
Imagine we want to append the value 71 to this array:

This can be accomplished like so:

The amount of new space allocated whenever we perform this operation is crucial to the performance of the array list. If, at each append, we created an array with just one new position for the new value being appended, it would mean that each append operation would require copying the entirety of the pre-existing data. This would be extremely inefficient—imagine having to copy millions of records simply to add a new one.
Instead, the common strategy is to double the array size each time more space is needed. This approach can be shown to nullify the effect of having these extra copy steps over time.
To add elements to a Python list, we use the .append() method. Here is an example of how to create an empty list and add a temperature reading to it:
temperatures = []
temperatures.append(35)
Linked lists
To structure data in a computer, we need a way to relate values to one another. Arrays accomplish this by allocating contiguous memory locations – meaning memory locations directly next to each other – and storing values sequentially. Think of it as a row of houses on a street: each house has a unique address (index), and they are physically located next to one another.
However, this is not the sole method for organizing data. An alternative involves using a node-based structure.
A node is an object that stores a value along with references to other nodes. For instance, to create a list-like structure using nodes, we can have a node that holds both a value and a reference to the next element in the list. In Python, this can be implemented with a class:
class Node:
def __init__(self, value, next_node):
self.value = value
self.next_node = next_node
Using this approach, one can create a list by linking values together through the next_node reference. Here's a snippet of code that creates a list with the values 42, 17, and 37:
node_37 = Node(37, None)
node_17 = Node(17, node_37)
node_42 = Node(42, node_17)

Manually linking nodes in this manner is not practical. The actual implementation requires creating another class that maintains references to both the first and last nodes of the list. To append a new value, we:
- Create a node with the desired value.
- Set this new node as the next node of the current last node.
- Update the reference of the last node to this newly added node.
Imagine we want to append the value 71 to our example array:

This can be accomplished like so:

class LinkedList:
def __init__(self):
self.first_node = None
self.last_node = None
def append(self, value):
node = Node(value, None)
if self.first_node is None:
self.first_node = node
self.last_node = node
else:
self.last_node.next_node = node
self.last_node = node
Unlike in array lists, we cannot directly access values by their indices. To read a specific value at an index, we must start from the first node and sequentially move from one node to the next until we reach the desired index. This process is significantly slower than direct access. If we have millions of values stored in the list, we would need to read through millions of values in memory to reach a specific index.
The advantage of a linked list lies in the fact that we can instantly add and remove elements from either the front or the back of the list. This capability opens up the possibility of implementing two new data structures: queues and stacks, which we'll discuss next.
Queues
Imagine you're developing a restaurant app that logs customer orders and forwards them to the kitchen. When customers arrive at the restaurant, they will queue up to place their orders, expecting to be served in the sequence of their arrival. This means that the first customer in line should receive their order first, and the last customer in line should receive their order last.
In the kitchen, the chef prefers to focus on one order at a time, so the app should only display the current order. Once an order is prepared and dispatched, the next order in the queue should be displayed.

We can interpret the above requirements as needing a data structure that supports the following operations:
- Adding elements.
- Viewing the element that has been added first.
- Removing the element that has been added first.
These operations are precisely what a queue offers. A queue can be implemented using a linked list, where elements are added by appending them to the list. Since elements are ordered by their arrival time, the first node is always the one that should be served next.
Here's how the orders above would be stored in the queue:

Once an order is ready, it can be removed by updating the first element to its next_node, assuming there is a subsequent node. The new first node becomes the second node:

Queues are described as a first-in, first-out (FIFO) data structure because the first element to be added is also the first to be removed. In our restaurant example, the first customer to arrive is also the first to be served (and removed from the chef’s list).
To use a queue in Python, we can utilize the deque collection from the collections module. Import this module and create an empty queue as shown below:
from collections import deque
orders = deque()
Adding a new element to the back of the queue can be achieved using the .append() method:
orders.append("burger")
orders.append("sunday")
orders.append("fries")
To retrieve and remove the next order from the front of the queue, we use the .popleft() method:
orders.append("burger")
orders.append("sunday")
orders.append("fries")
Stacks
In certain situations, we desire the opposite of a queue's behavior—we rather want to track the most recently added element.
To exemplify this, imagine you're tasked with adding an undo feature to an image editor. This requires a method to monitor the user’s actions, providing access to the most recent operations. This is because undo functionalities typically reverse actions starting from the last one performed and moving towards the first.
A stack is exactly a data structure that supports these operations:
- Adding elements.
- Viewing the element that was last added.
- Removing the element that was last added.
Like queues, stacks can also be implemented using a linked list. Adding an element is still accomplished by appending the element to the list. However, our interest shifts to the last element of the list instead of the first. To retrieve the most recent element, we look up the last element of the list. Removing the last element requires us to delete the last element.
In our node structure, we only tracked the next node. To facilitate the removal of the last element, we need to access the element that precedes it, delete its next_node, and promote that node to be the last. We can accomplish this by modifying the node structure to also track the previous node of each node. Such a linked list is referred to as a doubly linked list.

Stacks are described as a last-in, first-out (LIFO) data structure because the last element to be added is also the first to be removed.
To use a stack in Python, we can utilize the same deque collection. We use the .append() method to add new elements:
from collections import deque
actions = deque()
actions.append("crop")
actions.append("desaturate")
actions.append("resize")
To retrieve and remove the next order from the top of the stack, we use the .pop() method:
print(actions.pop())
print(actions.pop()
Data structures exist in both the digital and physical worlds. A dictionary is a physical example of a data structure where the data comprises word definitions organized in alphabetical order within a book. This organization allows for a specific query: given a word, one can look up its definition.
At its core, a data structure is a method of organizing data that facilitates specific types of queries and operations on that data.
We'll begin by covering linear data structures like arrays, lists, queues, and stacks. We'll then circle back to explain the difference between linear and non-linear structures before diving into hash tables, trees, and graphs.
If you want to learn more, check out this course on data structures and algorithms in Python.
Arrays
Arrays are fundamental data structures widely available across programming languages. They enable the storage of a fixed number (N) of values sequentially in memory.
Array elements are indexed from the first element at index (0) to the last element at index (N-1).
They allow the following operations:
Arrays are highly effective in scenarios where the number of values to be stored is known in advance, and the primary operations involve reading and writing data at specific indexes.
Consider a scenario in which you need to store daily temperature readings for the month of December. You might want to enable users to retrieve the temperature for a specific day and perform various statistical analyses on the temperatures throughout the month.
Since the number of days in December is known in advance to be 31, arrays are an excellent choice for storing the temperature readings. Initially, one would create an array with 31 empty positions. Then, after obtaining each temperature reading, the temperature for a given day would be assigned to the corresponding array index: day 1 would be stored at index 0, day 2 at index 1, and so on, until day 31, which would be stored at index 30.
Accessing the corresponding index allows retrieval of the temperature for a specific day. Statistics, such as the average temperature, can be determined by iterating over all elements, maintaining a cumulative sum, and then dividing by the array's size.
Arrays are not natively available in Python. They are used behind the scenes as the underlying structure for various data types but are not directly supported in the language. To use arrays explicitly, one can utilize libraries such as array, which offer an array implementation. However, it's often more practical to use a list with a fixed size in situations where an array might be required. Lists offer flexibility and are a core part of Python's functionality, as we'll discuss next.
We can create a list to simulate an array of 31 elements, each initialized to None, by using
[None] * 31. Here,Noneindicates that no temperature reading has been recorded yet.To set the value at a specific index, we use
december_temperatures[index], whereindexis a number from0to30. For example, to record the temperature for the first day (stored at index0), we would do it like this:Accessing a temperature is similarly straightforward, using
december_temperatures[index].Lists
Imagine now that, instead of focusing on December, we install a sensor somewhere to take periodic temperature readings over an unspecified period. In this scenario, using an array isn't the best option because we might run out of space due to its fixed size upon creation.
A more suitable data structure in this scenario would be a list. There are two kinds of lists:
Array lists
Array lists can be seen as a more flexible version of arrays. They can perform all the functions that arrays do but also append new values, so their size isn't fixed upon creation. Array lists correspond to using
list()in Python.Their implementation relies on using an array that's expanded when space runs out, hence the name array list. However, as we learned earlier, arrays cannot grow, so how is this possible?
When the underlying array of an array list is full, and we want to append a new value, a larger array is created under the hood. All the previous values are copied into this new, bigger array. Then, the new value is added at the first available position in the new array.
Imagine we want to append the value 71 to this array:
This can be accomplished like so:
The amount of new space allocated whenever we perform this operation is crucial to the performance of the array list. If, at each append, we created an array with just one new position for the new value being appended, it would mean that each append operation would require copying the entirety of the pre-existing data. This would be extremely inefficient—imagine having to copy millions of records simply to add a new one.
Instead, the common strategy is to double the array size each time more space is needed. This approach can be shown to nullify the effect of having these extra copy steps over time.
To add elements to a Python list, we use the
.append()method. Here is an example of how to create an empty list and add a temperature reading to it:Linked lists
To structure data in a computer, we need a way to relate values to one another. Arrays accomplish this by allocating contiguous memory locations – meaning memory locations directly next to each other – and storing values sequentially. Think of it as a row of houses on a street: each house has a unique address (index), and they are physically located next to one another.
However, this is not the sole method for organizing data. An alternative involves using a node-based structure.
A node is an object that stores a value along with references to other nodes. For instance, to create a list-like structure using nodes, we can have a node that holds both a value and a reference to the next element in the list. In Python, this can be implemented with a class:
Using this approach, one can create a list by linking values together through the
next_nodereference. Here's a snippet of code that creates a list with the values42,17, and37:Manually linking nodes in this manner is not practical. The actual implementation requires creating another class that maintains references to both the first and last nodes of the list. To append a new value, we:
Imagine we want to append the value
71to our example array:This can be accomplished like so:
Unlike in array lists, we cannot directly access values by their indices. To read a specific value at an index, we must start from the first node and sequentially move from one node to the next until we reach the desired index. This process is significantly slower than direct access. If we have millions of values stored in the list, we would need to read through millions of values in memory to reach a specific index.
The advantage of a linked list lies in the fact that we can instantly add and remove elements from either the front or the back of the list. This capability opens up the possibility of implementing two new data structures: queues and stacks, which we'll discuss next.
Queues
Imagine you're developing a restaurant app that logs customer orders and forwards them to the kitchen. When customers arrive at the restaurant, they will queue up to place their orders, expecting to be served in the sequence of their arrival. This means that the first customer in line should receive their order first, and the last customer in line should receive their order last.
In the kitchen, the chef prefers to focus on one order at a time, so the app should only display the current order. Once an order is prepared and dispatched, the next order in the queue should be displayed.
We can interpret the above requirements as needing a data structure that supports the following operations:
These operations are precisely what a queue offers. A queue can be implemented using a linked list, where elements are added by appending them to the list. Since elements are ordered by their arrival time, the first node is always the one that should be served next.
Here's how the orders above would be stored in the queue:
Once an order is ready, it can be removed by updating the first element to its
next_node, assuming there is a subsequent node. The new first node becomes the second node:Queues are described as a first-in, first-out (FIFO) data structure because the first element to be added is also the first to be removed. In our restaurant example, the first customer to arrive is also the first to be served (and removed from the chef’s list).
To use a queue in Python, we can utilize the
dequecollection from thecollectionsmodule. Import this module and create an empty queue as shown below:Adding a new element to the back of the queue can be achieved using the
.append()method:To retrieve and remove the next order from the front of the queue, we use the
.popleft()method:Stacks
In certain situations, we desire the opposite of a queue's behavior—we rather want to track the most recently added element.
To exemplify this, imagine you're tasked with adding an undo feature to an image editor. This requires a method to monitor the user’s actions, providing access to the most recent operations. This is because undo functionalities typically reverse actions starting from the last one performed and moving towards the first.
A stack is exactly a data structure that supports these operations:
Like queues, stacks can also be implemented using a linked list. Adding an element is still accomplished by appending the element to the list. However, our interest shifts to the last element of the list instead of the first. To retrieve the most recent element, we look up the last element of the list. Removing the last element requires us to delete the last element.
In our node structure, we only tracked the next node. To facilitate the removal of the last element, we need to access the element that precedes it, delete its next_node, and promote that node to be the last. We can accomplish this by modifying the node structure to also track the previous node of each node. Such a linked list is referred to as a doubly linked list.
Stacks are described as a last-in, first-out (LIFO) data structure because the last element to be added is also the first to be removed.
To use a stack in Python, we can utilize the same
dequecollection. We use the.append()method to add new elements:To retrieve and remove the next order from the top of the stack, we use the
.pop()method: