Recently in my computer science course I implemented a singly linked list for an assignement. To solidify the concepts, I'm going to rebuild it in python. And for your benefit, I'm going to write about it.
A singly linked list is composed of nodes, each of which points to another node. The only exception is the last node, which instead points to None. The nodes also contain a value. This can be just about anything, but for this demonstration I'll just use integers.
The first thing to do is define a class.
class SLLNode:
"""
A node in a singly linked list.
Attributes:
value - the value to be stored and displayed, integer
next - a reference to the next Node in the list
"""
Here I've defined the class and sketched out my plans for it. But I still need to implement it. To do that we need an initialization method. At least, we need the initialization method to do it neatly.
# indented with class SLLNode:
def __init__(self, value=None, next_node=None):
self.value = value
self.next_node = next_node
There's a bit to unpack here, but first let's check and see what it does. We'll do this by using the following code:
node = SLLNode(7, None)
print("Node with value {} and next node {}.".format(node.value, node.next_node))
And the output from that is:
Node with value 7 and next node None.
So what happened?
When I called SLLNode(7, None), it ran the __init__() method with the arguments 7 and None. This stored 7 to the attribute value and None to the attribute next_node.
What do we have so far? We have a way to create a node, and a convenient way to print the key information about that node, which will be helpful for debugging going forward. That's a pretty basic start, but it's where I'll end it for now.
More to come in this series as I build out the list.
The code for this project is available here on GitHub. I'll be updating it gradually as I write this series. I'll be sure to commit at least as often as I post, so you can back up and see that code as it was when I published a given post.
EDIT: The next post is now available here.
Top comments (6)
Not clear where you will go from here. You have defined a Link, but you have not defined a List, and it is in the List that all the real behaviors would reside -- or so it seems to me. Insert(link), Append(link), Delete(Link), Exists(Value)->Link/None, all these are behaviors of a List, not of a Link.
You might think, well, a "list" could be any reference to a Link, so the Link class could offer insert, append, delete, exists methods, and they simply mean, do that action to the list that begins with this link.
One problem with that is, it is not possible to have an empty list, i.e. a list with no links in it. You might rule that an empty list is just a reference to None, but in that case, an attempt to call a method like insert (to add the first link to an empty list) would produce the dreaded "NoneType has no method named insert()".
But also, if the Link is the only class, doing all the work of being a list, that's error prone, because it is easy to treat any old reference to a link as if it were the head of a list -- but is it? If you use a link that exists half-way along a list, as the head of a list, things will go wrong. So at the least, you would need to distinguish a special list-head-link class that can only be the head link in a list -- so you can test a link and ask it, "are you a head or just some random link?" But if you do that, what happens to the list if you delete the first link? How does the previously-second link graduate to head link? (And again, what's an empty list?)
Thanks for the comment!
These are all good points. I was in fact planning on adding a List class, and may do that in the next post in the series.
Although, it's an interesting thought exercise to imagine implementing a linked list with only a Node class. For the reasons you've stated, I'm not sure if it's even possible, but it is interesting to think about.
If you would just leave the node class like that, it would function like a type of graph where the connections are in one direction and no more is aware of the nodes that point to it.
Thank for you the comment!
That's an interesting observation about the graph. But there's one thing about that I don't understand. Wouldn't the code still need some mechanism to keep track of the first node? It seem to me that, without a pointer to the first node, that node would get lost and none of the other nodes could be accessed.
From what I've learned, it seems sensible to make that pointer to the first node be part of another class, perhaps a class called Graph. Is there another approach I could consider?
In this case, whatever the calling code was would need to save the head pointer in the calling function and pass it around. This isn't exactly an antipattern as we do need to pass around both a string and its length in some languages like C, but it obviously isn't preferable.
Thanks for explaining that for me.