What are Linked Lists and How Do I Make One in Python?

<< Week 6: Misc 03 | View Solution on GitHub | Week 8: Linked Lists II >>

(Image: iStock)

First, I have an announcement that I'm going to start making my articles shorter and more easier to digest. Hopefully they'll make for more light coffee reading than full-on Thanksgiving meals.

This week, we're talking about linked lists. Maybe you have heard of them? Maybe you saw them mentioned in a lesson on data structures and thought "that sounds too finicky, why wouldn't we just use an array?" Well, there are some advantages to linked lists over an array or list. They may seem complicated at first, but don't worry, I'm going to hold your hand and walk you through it.

Now that you have the image of us holding hands, you have a good idea of the structure of linked lists: a bunch of single nodes held together by links, i.e. references to other nodes. There are two kinds, singly and doubly linked lists:

(Image: Medium.com)

In singly linked lists, each node has one arrow pointing forwards, and doubly linked lists have an additional arrow pointing backwards. In general, though, most of the questions you encounter will assume singly-linked lists. Why? They're simpler to implement, and although you don't have the luxury of traversing the list backwards, let me tell you, arrows pointing in one direction are enough for your brain to keep track of.

Let's try implementing a linked list in Python. You may think to start with class Linked_list, and then make a bunch of nodes inside of it, but it's simpler than that. Imagine we're making a chain of paper clips: we get a bunch of paper clips and string them together.

(Image: iStock)

What makes the chain is the individual paperclips plus the fact that you strung them together. Instead of making a Linked_list class, we'll simply make a Node class and allow for individual nodes to be linked together.

class Node:

Next, as always when making a class in Python, we make the __init__ method. This is the method that initializes all the fields i.e. variables in the class whenever a new Node object is made. We'll take in a variable called data which is the value we want to store on the node. We also have to define the forward link, which is traditionally called next. To start, the node isn't connected to anything, so we set it to None.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

That's about all we need. We could leave it at that, but Cracking the Coding Interview also implements a method called appendToTail() which makes a new node and appends it to the end of the list, traversing the list so we don't have to do that manually. Let's take a look at it.

Start by defining it within the Node class. It will take in the value that we want to give the new node, and for Python, the self keyword.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def append(self, val):
        pass

The first thing we do is make a new node with the given value. We'll call it end.

  def append(self, val):
    end = Node(val)

Next, we make a pointer. It might sound technical, but essentially, we're making a reference to the head of our list. This is because we want to traverse the list without reassigning anything in the list. Thus, we make a reference to the first node, self, and save it with the variable n.

  def append(self, val):
    end = Node(val)
    n = self

Finally, we traverse the list. How do we do this? We only want to move to the next node if there is a next node, and if not, we know we're at the end. We'll use a simple while loop to traverse to the next-to-last node.

  def append(self, val):
    end = Node(val)
    n = self
    while (n.next):
      n = n.next

Finally, we're pointing at that last node, which has no next. We simply take end, which is our new node, and set n.next to be end.

  def append(self, val):
    end = Node(val)
    n = self
    while (n.next):
      n = n.next
    n.next = end

That's it! Here is our full class:

list_node.py

class Node:
  def __init__(self, data):
    self.next = None
    self.data = data

  def append(self, val):
    end = Node(val)
    n = self
    while (n.next):
      n = n.next
    n.next = end

Testing our Linked List

Let's try it out. Start by making a new Node object; I'm calling it ll (two lowercase Ls standing for Linked List) and giving it a value of 1.

ll = Node(1)

Now, since we added that sweet append() method, we can call it to add new nodes to our list.

ll.append(2)
ll.append(3)

How do we see what our list looks like? Theoretically, it should look kind of like this:

[1] --> [2] --> [3]

But there's no way to just print that. We have to traverse the list and print each value. But you remember how to do a list traversal, right? We just did one. To recap:

1. Make a variable to point to the head
2. While there is a next node, move to that node.

Then, we'll just print the data at each node. We start with step #1 by making a new variable and assigning it to the head of the list.

node = ll

Next, we print the first node. Why don't we start the while loop? The while loop will only iterate twice, because only two of the nodes have a next–the last node does not. In computer science, we call this a "fencepost problem", where you need to do something X times, plus one. You can think of a fence, where you have a post, then some fence, then a post, and a fence and so on.

(Image: Sawtooth Wood Products)

But you can't leave that last piece of fence hanging. You need a post on the end. So, you can either add another post on the end, or, as is more common in CS, make the first post and then build the rest of the fence. This is what we'll do.

First, we print the first node, and then we run the while loop to print out each following node.

node = ll
print(node.data)
while node.next:
    node = node.next
    print(node.data)

Running this for our previous list, we should get:

1
2
3

Printed to the console. And there we go! Our linked list works.

That's it for this week! Thanks for reading, and next week we'll look at a linked list problem, and we'll learn more about how to manipulate our linked lists, since it works a little differently than regular Python lists. As always, drop me a comment if you have any questions, or want to see more!

<< Week 6: Misc 03 | View Solution on GitHub | Week 8: Linked Lists II >>

Sheamus Heikkila is formerly a Teaching Assistant at General Assembly Seattle. This blog is not associated with GA.

Comments

[Jason C. McDonald]

Shorter technique: my_list = List() ;)

But yes, what you showed is the way you'd create your own linked list in Python! Now I'd be curious why you'd do this.

[Whiteboarding in Python]

This is a great question. There are some advantages to using a linked list over a Python list. Traditionally the question is "why would I use a linked list over an array", and the main point is that arrays in Java and other OOP languages are fixed size, so adding an element requires you to make a new array of size N + 1 and populate it with all the previous values, using O(N) space and time. By comparison, adding to the front of a linked list takes constant time. Python's list is not a true array but instead implements a dynamic array, which has its own advantages and disadvantages. The wikipedia page for dynamic arrays has a table that compares the performance for linked lists vs. arrays vs. dynamic arrays: en.wikipedia.org/wiki/Dynamic_arra...

If you're not worried about performance, then yes, it's easier to use a Python list. The reason for learning how to implement a linked list is along the lines of learning math when you can use a calculator–it's more about learning the concept. It's hotly debated in the developer community whether technical interviews that ask data structures and algorithms problem are really necessary. I don't know the answer to this. This article series is meant to prepare students who only know Python for these kinds of interview questions.

One advantage is that this simple linked list class provides a base to make our own specialized list class with custom methods, which I'll do in a future article when we use our linked list class to make a simple blockchain. So stay tuned for the DIY Bitcoin article!

[Jason C. McDonald]

Ah, okay, I was merely under the impression that List had been implemented as a linked list. (I already know the difference between fixed-length array, dynamic-length array, and linked list, but your explanation will be helpful to anyone who isn't.)

[Whiteboarding in Python]

I also was unaware how list is implemented in Python. So we both learned something :)

[Jason C. McDonald]

On nerd-level discussion of data structures (language agnostic now), another good option for a dynamic contiguous collection is a circular buffer, which is designed such that the head and tail "float". It's a bit hard to explain — basically, you don't require head to be at element 0, but implement logic for "wrapping around" from the last element to the first, as long as you haven't yet reached tail.

It makes for a time complexity of O(n/2) on insertion/deletion without reallocation, instead of the O(n) of a typical contiguous collection. Even better, head and tail operations are always Θ(1). While this is still a bit higher than the consistent O(1) of a linked list, you don't have the cache misses. It's also better-suited for random access.

No idea how you'd effectively implement this in Python, however. I always use pointer arithmetic to pull it off.

[Whiteboarding in Python]

I'm trying to imagine what this looks like implemented:

[Jason C. McDonald]

Not far off. ;)