Join us and get access to thousands of tutorials and a community of expert Pythonistas.
This lesson is for members only. Join us and get access to thousands of tutorials and a community of expert Pythonistas.
Implementing Your Own Linked List
00:00 There are a few reasons why you might want to implement your own linked list in Python. For one, implementing linked lists is a great way to practice your Python algorithm and data structure skills.
00:13 Since we’re dealing with self-referential objects—aka nodes that point to other nodes—we have to be careful about the order in which we do things so we can avoid accidentally losing the entire list. After all, if we lose reference to one node, all the nodes that follow it are lost too. Linked lists are also very commonly asked about in technical interviews, so having hands-on experience working with them might just help you to land your next developer job, even if you never touch them again.
00:47 In languages that support object-oriented architectures—such as Python—linked lists are often implemented with objects called nodes that store references, or pointers, to other nodes.
01:01 Things work similarly in non-object-oriented languages like C, except there, you’d represent nodes with structs that are often dynamically allocated on the heap. Fortunately, this is a course on Python, so we won’t need to worry about allocating memory manually. The CPython interpreter will do that for us.
01:24
Before we start coding, let’s plan out what classes we’ll need to build. The first class is aptly called LinkedList. There will only ever be one LinkedList object in our program, and it will store an instance attribute called head that will point to a node object.
01:42 And of course, that node object will point to another, and another, and another—
01:49
until we have an entire linked list. Really, the LinkedList object is just a container that stores the head of our linked list in memory. Storing the linked list in this object has other benefits too, one of which being that we can create a method that will print out the contents of the internal linked list with little helpful arrows to show the links between nodes. In fact, we’ll create a bunch of methods to operate on the linked list. As for the Node class, that one is pretty small too. We’ll have two instance attributes, one for the data stored at this node, and another called next that points to the next node in the linked list.
02:34 Let’s head over to Visual Studio Code and try this out for ourselves.
02:39
I’m here in a new file called linked_lists.py, and the first thing I want to do is create the LinkedList and Node classes.
02:48
Nothing too special here—just two classes with some instance attributes. This is honestly all we need to get up and running with linked lists, but there’s one problem: this LinkedList type is not iterable, meaning that we can’t use it in a for loop to quickly print out its elements.
03:09
Instead, let’s override the default .__repr__() (dunder repr) method of both of these classes so that we can quickly get a string representation of them whenever we want.
03:20
This will allow us to see a visual representation of the nodes in the linked list, as well as the links between them. I’ll start with the Node class. To override the .__repr__() method, all we need to say is def __repr__(self):, and now we can just return the .data in this Node.
03:42
This means that whenever we try to print the value of a Node, it’ll print the items stored in the .data attribute. Things are a little more complex for the LinkedList class.
03:54
I’ll move down there and create that .__repr__() method. What we want to do here is traverse through the entire LinkedList one Node at a time, storing the .data item in each Node in a new Python list—that is, just a regular old list.
04:12
Then, we can use Python’s fancy .join() method to join the elements together, separating them with an arrow. To start, I’ll create a new variable called node that points to the .head of the internal LinkedList.
04:27
I’ll also need to create a list for the node data. We want to traverse as long as the current node is not None—that would indicate that we’re at the end of the list, so we should stop. Inside here, I’ll append the .data item of the current Node to our nodes collection. Then, so we don’t get stuck in an infinite loop, I’ll make sure to set the node variable equal to the next node in the linked list.
04:56
Once we’ve traversed the entire list, we should append None to the end to show that the last node points to no others.
05:06
Finally, I’ll return " -> ".join(nodes).
05:12 Let’s try out our new linked list in the interactive shell.
05:16
We can create a new linked list by instantiating the LinkedList class.
05:23
To test out our .__repr__() method, let’s inspect the value of this new list. As expected, we get None, because no nodes were traversed.
05:35
Now, let’s create a node called first_node, and that will equal a new Node object with a data value of "a". That right there is enough to be a linked list.
05:47
After all, linked lists can have only one node. All that’s left to do is point the .head of the llist object to the first_node object, and then we can inspect llist again.
06:02
And, as you can see, our Node is there. One thing to note is that we didn’t have to explicitly tell first_node to point to None for its .next attribute.
06:13
That’s because we never assign the .next attribute to anything, and so it just takes on the default value of None. We keep adding as many new nodes as we want.
06:25
Whichever one is never assigned the .next value will be treated as the last node in the linked list. I’ll create two new nodes called second_node and third_node. To create the links, do first_node.next = second_node
06:45
and second_node.next = third_node.
06:52
We’ve just manually built a linked list by setting each node to point to another one. If you’re following along then congratulations, because you’ve just implemented your very first linked list in Python. You’re well on your way to being able to implement more advanced data structures such as stacks, queues, and graphs. In the next video, we’ll make instantiating new LinkedList objects easier by adding a constructor.
Austin Cepalia RP Team on Oct. 8, 2020
@Stan Taov Inheritance doesn’t come into play here, only composition. LinkedList is composed of a single Node object, referred to as the head. Each Node is composed of another Node object, or in the case that it is the last node in the list, None. This composition creates the links between all the nodes. Is that what you’re asking?
Bartosz Zaczyński RP Team on Oct. 8, 2020
The LinkedList class represents a container for the Node instances. Inheritance would only make sense if one of them were a subtype of the other. That’s not the case because neither list is a subtype of node nor is the latter a subtype of the former. In fact, the list is composed of nodes.
The node variable in the LinkedList class initially refers to the list’s head and is updated by the while loop. It’ll point to the next node on the list in each iteration until there are no more nodes.
Data is stored within the individual nodes, so there’s no direct access to it from the list. A list only knows about the nodes, so you need the .data attribute on the current node to access that data.
Stan Taov on Oct. 8, 2020
Hi Bartosz,
Thanks a lot for your reply, I need some clarification here (It’ll point to the next node on the list)can you please tell me how it gets to that list, I don’t see it. Data is located in each node. Node has only .head attribute, how it gets access to .data if we didn’t assign Node class to it?
Stan Taov on Oct. 8, 2020
Hi there,
I think I figured it out, we get the list from node since we assigned an object/instance first_node (Node class) to .head of LinkedList and can assess all its attributes.
Anurag Gupta on Dec. 21, 2021
I am confused as to how node = node.next will take us to next node? Is .next a built-in method or an attribute defined in Node class? How does this line work?
Bartosz Zaczyński RP Team on Jan. 3, 2022
@Anurag Gupta .next is a custom attribute of the Node class that holds the reference to the following node “linked” to it. The line of code you mentioned should be read from right to left. First, you take the current node and read the address of its immediate neighbor. Then, you reuse the same node variable in a loop by assigning the next node to it, so the current node becomes different on the next iteration.
Become a Member to join the conversation.
Stan Taov on Oct. 7, 2020
Hi there,
I am a little bit confused here, how does node.data in LinkedList get its data to append to an empty list? If both classes are not inherited.