While developing software we all look for the best ways to structure our data.Today I want to explore one the ways in which we can better structure our data. In my own experience when I know the pieces to put together I use whatever method available to complete the puzzle. That can often lead to sloppy code and poor execution of a task. Thinking like a computer scientist is easier when you know all the techniques and utilizing linked lists as a way to organize our data is one of those.
Lets first explore what a linked list is. When writing code it’s often good practice to create lists of data using arrays. However there are alternative ways, that may work better depending on the situation you find yourself in. Using a linked list to organize your data can actually help to save memory and utilize your stack a little better. The biggest difference between an array of data or a linked list is that when you create your array you are using a static amount of memory bits in a row. Whereas with a linked list each piece of data, or node, contains references to the next node in the sequence allowing the data to be scattered among your available memory for execution.
Red VS Black Shirts
The difference lies in the physical and logical location of your data. You can think about it a little like this; There are two groups of eight people each, and they both enter a large dining hall full of other people. The first group are all wearing red shirts and they are lead by the head of the group. They are all holding hands with the next person in line. So they all know where they should be because they are holding the hand of the next person ahead of them, and they are in one contiguous box. The other group is wearing all black shirts and they are headed by the first node. They have signs attached to their backs referencing which order they are in for their block of data.
The black shirts don’t need to hold hands and can roam around the room freely. All one node has to do is look up and look for the sign with the next node attached to the back of a black shirt. The red shirts must stay one contiguous block holding hands as they attempt to navigate the room full of people.
Types of Linked Lists
Singularly-linked lists:
A singularly linked list is a list in which each node references only the next link in the list. The ending node not referencing anything signalling the end of the list. To extend our shirts metaphor each person (node) in black shirts has the sign referencing the next person ahead of them in line.
Doubly-linked lists:
A doubly-linked list is a list in which each node references the next node in the line and the previous node in the line. So our black shirted friends would have a sign that indicated the next person (node) ahead of them, and the person that’s supposed to be behind them. With the head person (node) not having anything as a previous reference and the last person (node) not having anything to reference ahead of them.
Linked Lists in Python
Linked lists can be tricky to remember, but once you figure it out you it’s a great way to organize data and is something you see come up in technical or coding interviews. In fact knowing heaps, other data structures can help a great deal in those coding interviews. A little bit of math too I find. For myself knowing this stuff is great however I also need to be able to think about these techniques from a coding standpoint. I can look at all the pictures and think about all the metaphors I want; However until I can code it out and explain it to someone, I find that I still have issues.
Lets create a new file called list.py and type out a new class called Node and put in our attributes for node creation.
class Node:
def __init__(self, data=None, next=None):
self. data = data
self.next = next
def __str__(self):
return str(self.data)
Now each Node is made up of two parts. The piece of data that we’ll just call data and the next reference that we’ll make. Each node will have their respective piece of data and the reference to the next node in the list. We also put in a str method so we can actually see our data. So that we don’t have issues at runtime we set the methods to equal None so that we can fill in our data.
Now if we go ahead and run the Python interpreter and put in our import statement, we can import our list file.
>>> from list import Node
Then we can start creating our nodes.
>>> node1 = Node(23)
>>> node2 = Node(25)
>>> node3 = Node(45)
>>> node4 = Node(77)
Now we have some nodes that are in a list but not necessarily linked. If we wanted to print our data we just need to call the node.
>>> print(node2)
25
Now we can go through and set our nodes’ next method to reference the next node in the list.
>>> node1.next = node2
>>> node2.next = node3
>>> node3.next = node4
So each of our nodes now has a reference to the next node and we have ourselves a singularly-linked list. There’s another method we can add in here as well to print out our list in full.
def print_list(node):
while node:
print(node),
node = node.next
print
So then we import our print_list method so we can print out our list.
>>> from test import print_list
>>> print_list(node1)
23
25
45
77
Then we get a print out of our list, which can also be called a collection.
To do the same thing as above but with a doubly-linked list we can easily add in another attribute into our Node class called before.
class Node:
def __init__(self, data=None, before=None, next=None):
self. data = data
self.next = next
self.before = before
def __str__(self):
return str(self.data)
Creating the references to our previous nodes is as simple as creating the next references.
>>> node2.before = node1
>>> node3.before = node2
>>> node4.before = node3
That is exploring linked lists through Python. I hope that this was somewhat helpful in the understanding of linked lists. There are textbooks of information about this stuff online and through schools. Getting more in heaps and different data structures also helps to understand how some of this stuff is helpful in developing software. The one caveat in creating these lists in Python is that Python is a high level language subject to a few different layers of abstraction before running. However it serves as a good example on how these lists are structured.
Below are some great links in helping to understand more about linked lists and other computer science lessons.
http://www.openbookproject.net/thinkcs/python/english2e/ch18.html
http://www.necessaryandsufficient.net/2008/05/differences-between-arrays-and-linked-lists/
https://medium.com/basecs/whats-a-linked-list-anyway-part-1-d8b7e6508b9d
https://medium.com/basecs/whats-a-linked-list-anyway-part-2-131d96f71996
Top comments (1)
It was nice to read this blog.
I maintain a repository that contains popular data structures and algorithms and we have an implementation of linked list there. I think that printing strategy used in the code might be of your interest.
Cheers!