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.
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.
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.
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.
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.
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
I’ll move down there and create that
.__repr__() method. What we want to do here is traverse through the entire
Node at a time, storing the
.data item in each
Node in a new Python
list—that is, just a regular old list.
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
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.
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
third_node. To create the links, do
first_node.next = second_node
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.
Become a Member to join the conversation.