Linked Lists
Working with linked lists:
First: What is a 'linked list'?
In very short, a linked list is comprised of nodes
that are linked together to create a collection of nodes, in other words a list. The nodes reside anywhere in the memory, not necessarily one right after the other as they do in an array.
So what's a node? You can think of it as a nugget of data that contains 2 sections:
1 – the data, the value, the cargo (different words for the same thing).
2 – the pointer, the reference, the 'next' which points to the next node in the linked list. (Technically, it really holds the address of where the next node resides in memory. But for our discussion here, we will refer to it as the 'pointer' or the 'next'.)
To kind of visualize it ...
| val | next | ----> |val |
None
|Here, the first node points to the second node. And since there is no third node, the second node doesn't have a next or pointer, so it is
None
. Of course, there can be many nodes (with pointers pointing the next node) in a linked list.
or:
| val | address | ----> |val |
None
|Technically, the first node holds the value and the address of where the second node lives. The second node holds the value, but since it is not linked to anything, there is no address; it holds a
None
.
and as an example:
| 1 | 300 | ----> |2 |
None
|The first node lives at an address (not shown here) - see more about this below. The first node holds the value
1
and the address of its next node, here we made up the address as300
. The second node resides at the address300
- which is what the first node was storing.
Technically, we need a reference to the address of the first node. That will be called the head.
To simplify for our discussion and in general, the first node is generally called the head of the linked list. The rest is referred to as the tail. The entire linked list is referenced by its head. In most cases, the head doesn't change too often, but the tail might. (The head would change if that first node is deleted or changed.)
How to set up a linked list?
We first set up a Node Class and instantiate the val
and the next
.
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
def __str__(self):
return str(self.val)
So, a simple node can be set up:
>>node = Node(4)
This creates an instance of the Node class.
- The val
is 4
. And next
is still at the default of None
-
node.val
= 4 -
node.next
= None
There are several ways to actually set up the nodes and the whole list. And add or delete or modify the nodes. Here's my preferred way, several methods in the LinkedList class.
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
Start off by instantiating the list itself – defining the head
and the tail
. Both start off as None
.
Here's the method for adding nodes.
def add_node(self, val):
new_node = Node(val)
if self.head == None:
self.head = new_node
if self.tail != None:
self.tail.next = new_node
self.tail = new_node
In this add_node
method, we will set the head
of the list- when adding the first node. If the new node doesn't yet point to anywhere, the next
remains as the default None
.
With each new node, we set the next
of the previous node – because only now we know where it will point to. And we add that new node – only the value; the next
will remain None
until it knows where to point to.
-
new_node
is an instance of Node. (ex: if Node(6) thennew_node
is 6.) -
Then, we see if we need to set the
head
or if it was already set. Ifhead
is stillNone
, then thisnew_node
is the head. If it is already set to something, then the head remains the same. -
Next, we check if there is anything in the tail. If there is something other than
None
- meaning that there is a 'previous node' that is waiting to find out what it will point to - then thetail.next
should be set tonew_node
. In other words, we now know where it should point to - to the new node. -
Lastly, we add the
new_node
to the tail of the list.
In other words …
node # | new_node | head | next | tail |
---|---|---|---|---|
When we first instantiate – Node #0, there is no new_node
yet, the head and tail are set to None
.
Adding Node #1 = Node(6)
-
the
new_node
= 6 -
We check if the
head
(here shown as row above) isNone
and since it is the first added node, it is indeedNone
. Then we set thehead
to6
. Which it will be from hereon until we change that first node. -
We check if the
tail
(here shown as row above) is notNone
. When adding this first node, it is stillNone
. So we leave thenext
asNone
. When we will add the next node, we will change it (hence the arrow indicating that it was firstnone
and then when adding the next node, we change thenext
to point to it. -
We add the
6
to thetail
.
When we add the second node (the 8), the head
remains the same. We see that the previous tail
now is not equal to None. So we need to add the 8
to next
to that previous node.
And so it goes!
The last node has a value, and its next
is None
.
Now onto searching for something in that linked list
The basic idea is that we'll traverse through the linked list until we find what we are looking for. I've created it as another method of the LinkedList class.
def search(self, item):
node = self.head
while node != None:
if node.val == item:
return node.val
else:
node = node.next
return 'not found'
-
We start off by setting the node to the 'head' of the list.
-
And use a 'while loop' to loop through the list.
-
If the
node.val
matches the searchitem, return thatnode.val
-
And if that
node.val
is not the search item, then move to the next node – by setting the node to thenode.next
. -
And if after it goes through all nodes (when it does equal
None
) and it still has not been found, return 'not found'.
Pretty straight forward. We'll use this as the base for removing nodes.
Removing Nodes
An important point to remember as we think about removing nodes.
-
When nothing points to a node, it simply hangs about until Python's 'garbage collection' just throws it out. So removing the pointer that points to that node is part of the way we remove a node.
-
If we simply remove the
next
from a node, then anything after that is also disconnected from the first part of the list and thus lost. Like those long linked Xmas lights. -
The best way to remove a node is to have the pointer that was pointing to it just point to something else, to the next node on the link. So for example if node 4 points to 5, and 5 points to 7, and 7 points to 8. If we want to remove node 7, we can change the pointer of 5 (which currently points to 7) to point to 8. And then nothing points to 7 and it's gone to garbage collection.
So we traverse the list searching for that node and then point the previous node – that was pointing to the one we want to remove – the next one. That's the idea.
But once we pass the previous node, we can't reference it anymore. So we have to keep track of the current node and the previous node.
Here's the code and then I'll explain:
def remove(self, item):
node = self.head
previous = None
while node != None:
current = node
if node.val == item:
previous.next = current.next
return 'removed {}'.format(node.val)
else:
previous = current
node = node.next
return 'not found'
We set the node to the head and previous
to None
. We will use this previous
to keep track of the previous node.
Use a while loop to traverse through the list.
We set the current
to the current node.
Next, we check if the node.val
is the item we are searching for.
-
And if it is, then
next
of the previous node is now set to thnext
of what is the current node. -
And if it is not, then we move both the previous and the current along the traversal of the list. The previous gets the value of the current one. And the
current
gets the value from thenext
. Until it is found. Or not.
This works great for searching any item in the list, or even something not in the list. But if the search item is the very first node – the head, then there is no previous
as there simply is no previous. And also we set it to None
. So the line previous.next = current.next
won't work since previous
is None, it can't have the next
attribute. You'll get this error: AttributeError: 'NoneType' object has no attribute 'next'
Here's a solution. Add these lines before the while
if self.head.val == item:
self.head = node.next
return 'removed {}'.format(node.val)
If the item == the self.head.val
(the val of the first node), then we have found the node to be removed. But before we remove it, we need to set the new head. So the node.next
of that node, of the self.head
will be the new self.head
. And we jump out of the method. (Read it slowly a second time, it does make sense.)