The Self-Taught Computer Scientist

Figure 10.7: Linked list operation run times

---

Data Structures
104
Conceptually, a linked list is the same as a Python list or array, and you can use a linked list in any 
situation you would use them. As you know, adding or removing data from an array is O(
n), so you 
should consider using one if you’re writing an algorithm that adds and removes data often because 
adding data to a linked list is O(1). Memory management systems in operating systems use linked 
lists extensively, as do databases, and business systems for accounting, financial transactions, and sales 
transactions. You can also use a linked list to create other data structures. For example, you can use 
a linked list to create two data structures you will learn about in later chapters: stacks and queues. 
Finally, linked lists are essential to the blockchain technology behind the web 3.0 movement, which 
powers cryptocurrency. Blockchains themselves are similar to linked lists, and some blockchains use 
linked lists in their technology.
While linked lists are useful in some situations, they also have several disadvantages. The first dis-
advantage of a linked list is that each node must carry a pointer to the next node. A linked list’s pointers 
require system resources, so linked lists require more memory than arrays. If the size of the data you 
are storing in a single node is small, such as a single integer, the size of a linked list can be twice the 
size of an array holding the same data.
The second disadvantage of a linked list is that it does not allow random access. In computer sci-
ence, random access is when you can access data randomly in constant time. For example, there is 
no way to jump to the third element in a linked list like you could in an array. Instead, you have to 
start at the head of the list and follow each pointer until you reach the third element. While this can 
be a disadvantage, there are some more advanced versions of linked lists that overcome this problem.
Create a Linked List
There are many different ways to implement a linked list in Python. One way to create a linked list 
is to define classes representing the linked list and its nodes. Here is how you define a class to repre-
sent a node:
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
Your class has two variables: the first, 
data
, holds a piece of data, and the second, 
next
, contains 
the next node in the list. In Python, you don’t have to deal directly with memory addresses (like in the 
programming language C) because it handles that for you. When you create an object, like an instance 
of a class called 
Node
, Python returns a pointer (or reference) to the object. This pointer is, essentially, 
an address of where the actual data resides in the computer’s memory. When you assign objects to var-
iables in Python, you are dealing with pointers (references), so you can easily link objects together 
because Python is doing all the underlying work for you.

---