There is a lot of chatter amongst the tech community as to whether or not being able to build or understand a linked list is necessary in this day and age. Arrays, lists, objects and dictionary type data structures are built into higher level languages, even JavaScript, and we as developers don’t necessarily need to understand what is under the hood, just how to manipulate it.
I’m a believer in understanding at least some of what drives your vehicle. If you think you need blinker fluid, and really your antifreeze is empty, it can cause serious problems. Now if you have a mechanic on hand that constantly checks for these things, it may not be an issue, but I think it’s helpful knowledge, and can’t hurt to understand a little of how these structures work deep beneath the surface.
A reminder, I share all my code so you can learn from it. Feel free to copy and paste, destroy it, dissect it, manipulate it, and have fun. I would suggest having an intermediate understanding of Python if you wanted to attempt the Linked List without my starter code.
The Object
Python is considered an Object Oriented Language. Without going into a deep dive in this subject, think of an Object as a piece of Tupperware, or a blueprint. When it is created, and assigned values, Python wraps it all up into a neat little dictionary or it’s own data structure, and places all those values and contents at an address in memory. Once the object is created, it will remain while the code is being run. Once Python decides the object is no longer needed, it releases the memory space that object once occupied.
Items to look up:
- Python Class
- Python Object
- Python Garbage Collection
- Python self
For now, just think of these objects as blueprints, and when we build them and use them, python manages all the memory space they need and occupy. A neat little Tupperware bowl filled and labeled with whatever we want. The node is an Object, as well as the Double Linked List. You can play with the nodes, without the list to get a feel for what they are, and what data they are holding.
Think of the (self) as a way for Python to keep track of what belongs to what object. A way of deciding which things the class is allowed to alter within itself, or that other classes(objects) can access to alter inside of it. If the class has an attribute self.hat = ‘big blue hat’ we’re stamping that hat with a label that says it belongs to the object it was declared in.
Once they are created inside the list object, they are stored as objects in the Linked List. So one container holding another container. Or if you build a massive pile of nodes, think of the List as a cupboard, and the nodes neatly organized containers inside the cupboard. The class itself is how Python builds the objects, the containers, and they don’t exist except for as blueprints until we’ve told Python to go ahead and build them.
Then we have an accessible cupboard full of little Tupperware's we can use as we go.
What’s inside the nodes is data, what they are labeled with is an address that Python assigns to it once it is created from the blueprint.
The Node
You can think of the node as a data container. It will hold some kind of value, or even object, and the computer can look it up for you by way of your linked list. The node has two attributes that help make this possible. The previous, and the next links. These items, when the node is initiated, can be set to point to the next item in the linked list, and the one previous to it. Think of the next and previous as pointers, or directions for the computer. These links serve as a location getter as your machine needs to traverse the list, from back to front, or front to back.
A binary tree starts in the middle, and uses a similar system, but the items are placed in a value system instead of when they are entered by the human driver. In a binary tree the computer places the nodes in their new homes as the human enters them
based on how their data/or name ranks in the value system. The python binary tree will be in a future post.*
class DLLNode(object):
def __init__(self, prev, value, nxt):
# the first node will have no next or previous
self.value = value
self.next = nxt
self.prev = prev
def __repr__(self): #[ <--- prev , DATA , next ---> ]
nval = self.next and self.next.value or None
pval = self.prev and self.prev.value or None
## previous node, assigned value, link to next node
in list ##
return f"[{repr(pval)}, {self.value}, {repr(nval)}]"
#SEE NOTE
NOTE: if you are not in a python 3+ version, the f-string will
error in anything below 3.
The f-string exists in 3+ but not in 2.7. If you can, always
run experimental code in a python virtual environment in case
things go horribly south, and to keep your running version in
check.Python language in particular has a habit of introducing new
capabilities that are not backwards compatible. If you keep
having errors from code, and have checked everything else, see
if you’re using a new feature of a new version. Your older
version may not know what to do with it.
We start the list by giving it two attributes, and some functionality.
For a data structure, the most simple things to focus on:
How to add data to it : push
How to check it’s size: count
How to get a piece of data: get
The Push
The push will add new nodes to the list. There’s a little required knowledge to this process.
The list starts with an empty start(head) and end(tail) point. As nodes are added, the nodes will be placed on the end of the list. In order for this to happen, we have to change that end node, so it now points to our new data node.
In the very beginning, the empty place of the start node will be taken by our very first node. I’ve set my list up a bit differently than the directions given by the Learn More Python the Hard Way. I decided that in order to keep the list as decipherable, and tangible as possible, we should never have the end node, and the begin node be the same position, or address in memory.
The node being stored in memory is an object. It has an address that looks something like 0xp464739osdo000 (completely made up random digits). When python looks for that node, it looks for an address, and at that address is where our memory has our node stored away for future use.
I’ll give you some code, then explain in more detail.
NOTE: if you accidentally type
__inti__
instead of
__init__
Python will not error, but your code will not do what you think it should. At least in 3.6 and 3.7 I found this to be true.
class DLList(object):
def __init__(self):
# end holds the last node, and after the list is
# greater than 1 the whole list
# through it's previous links
self.end = None
# begin holds the first node, and the whole list
# through it's next links
self.begin = None
self._length = 0
def push(self, obj):
# if there is an empty list, create the first node
# with no next or prev.
if self.end == None and self.begin == None:
newnode = DLLNode(None, obj, None)
self.begin = newnode
self._length += 1
## if the list has contents, I never want the begin and
# end to be the same node or address.
elif self.end == None and self.begin != None:
# get the address of the original node
node = self.begin
# create address for new node
newnode = DLLNode(node, obj, None)
self.end = newnode
self.begin.next = self.end
self._length += 1
else:
#[ <--- , DATA, (/) ]
node = self.end
# list: [<-node---, DATA, (/) ] ,
# [self.end, obj, None]
newnode = DLLNode(node, obj, None)
# at this point the list has at least 2 items...
# the begin is pointing to the next item
# which if with 2 items is the end node.
# We only need to change the end node. Begin node
# does not need to be altered.
# change self.end next
# [ <--*old link---, DATA, -- newnode --> ]
# * old link* it doesn't matter what this link
# is. It was set a long time ago.
self.end.next = newnode
# Now I set the end = to the newnode that is
# pushed on
# self.end = [ <--- old self.end, DATA, (/) ]
self.end = newnode
self._length += 1
assert self.end != self.begin
Explanation (Push):
One of the things I had trouble wrapping my head around when I started this project, was how the list kept track of all the nodes, when only the end, and begin were listed as class attributes.
Here’s the magic of the Linked Lists:
When we create a new node, and tell the other nodes where it’s address is, or link them to it, they are all a part of the structure now of the object, although not clearly visible, they are there, stored away in memory as much as if we said, x = ‘42bananas’ and stored that in the object never to be used again. The reason it’s not lost, is the begin node, and the end node, from the when we first push a node into our DLList, are holding a reference to the next, and previous item. (it’s location in memory).
The begin node and the end node are stored as attributes in the Python object’s dictionary, and as such, their links can be used to retrieve whatever they point to, the address or the variable or the object that is stored there. And since the next address is in there, so is the address it stores, so on and so forth until we get to the end node, the last node which also references all the nodes before it.
The doubly linked list is different from a single linked list, because you can start from the beginning (head) or the end(tail) and work your way through the data nodes. In a single linked list, depending on the direction it is built to store the nodes as they are added into the structure, can either be a Stack, or a Queue. Single linked lists only unpack, and retrieve the data in one direction. Either from the first to last, or last to first.
I have links to my old blog if you’d like to see the code for a single linked list. I’ll add that at the end.
The count
This method can be used in various ways, and in the end I decided to add the _length attribute to the list so time wasn’t lost by iterating through the entire node phone book just to count it’s contents. (Phone books were once used in antiquated times for looking up a person’s name, phone number and address. The names were listed in alphabetical order, and a person had to pay a special fee to be ‘unlisted’ in a phone book.) I found a use for this though, and a challenge you can set up for yourself is to use something like this count method, to print off the nodes in the list. It’s very useful for debugging and for my fellow visual learners, it helps a lot to see what’s going on.
def count(self):
count = 0
node = self.begin
while node:
count += 1
node = node.next
return count
Explanation (Count):
The count method, which belongs to the DLList object, accesses the begin node by assigning it to a value,( node = self.begin).
The while loop will check it’s condition on each run. Python, if an object is None, will stop the loop. It’s equivalent to saying while true. Once that true becomes a false, the loop exits. Because our end node has a ‘next’ of None, when the node value finally reaches the end of the list, the while loop shuts down. So each loop, we add to our count, change the node to the next one in the list by grabbing it’s address, (node = node.next) and continue until we get to the end where next = None on that end node.
The reason this method is more expensive for running instead of keeping a _length count as you add or subtract nodes from the list, is every time we need a count, it will have to go through every node to evaluate the number of nodes. This could also be seen as O^n. If you have 300 nodes in your list, it will have to touch each item one time. With the _length, to get the size of our list, we access the self._length attribute once, and receive back our count.
The Get
Remembering we have a _length on this list, we can use this number for indexing objects in the list. While the get still loops through every item, it stops once it reaches the desired location, and we can have it check to make sure the index exists before executing the loop.
def get(self, index):
index = int(index)
length = self._length
count = 0
if length == 0:
return None
elif index >= (length):
print(" index out of range! ")
# this should be an error for the real thing
# raise IndexError
return None
else:
count = 0
node = self.begin
while node:
#print(f"while loop.{count}")
if count == index:
#print('get return value:')
#print(node.value)
return node.value
node = node.next
count += 1
Explanation (Get):
It’s very similar to the count method. It still has to possibly go through the entire list to get the value and return it. If for instance, someone was looking for the last item in the list, it would have to go through the entire list, comparing the index the user asked for to the current count value. Once it finds the match, it returns the value of that node, or the data we decided to store within our Node(object).
That’s all for the Double Linked list for now. The next post we’ll go over pop(), remove(), and shift().
I'm working with learning WordPress to create a site to hold my blog posts and migrate them from my old coding blog on blogger.
This post was originally mostly code, and little explanation in blogger. A rewrite was in order, and I hope to contribute more soon, but hopefully to the new site.
As promised:
Want to play a silly simple game with nodes?
(Drag and drop is not available on Internet Explorer)
https://nelliesnoodles.github.io/LinkedListGAME/
This one will also get a re-write and explanation if there is enough interest in it.
A Python Single Linked List:
https://camelcasenoodles.blogspot.com/2017/12/new-single-linked-list-python.html
Top comments (0)