Introduction to Linked Lists

Implementation in Python

Photo by JJ Ying on Unsplash

When I started this blog, I was a data science boot camp student determined to pursue a career in data analysis. My posts early on were often focused on techniques related to data analysis and visualization. Recently in my journey into tech, however, I’ve found a much deeper appreciation for coding and computer science than I have for purely data-focused applications of programming.

A few weeks ago I began shifting my focus towards better learning object-oriented programming, as you might tell from my most recent posts. This has opened many doors for me including one leading into the world of data structures, since their implementation is most easily achieved with OOP.

Data Structures

Data structures in computing refer to particular ways of organizing data for efficient use. Python users should be familiar with some of these simple data structures inherent in the language:

• Lists

[1, 2, 3]

• Tuples

(1, 2, 3)

• Sets

{1, 2, 3}

• Dictionaries

{'first': 1, 'second': 2, 'third': 3}

We have different data structures because each one can offer unique advantages over others in terms of different tasks like inserting elements, removing elements, searching, sorting, etc.

The data structure I’d like to discuss today is one that does not come standard in Python, the linked list. Why it’s standard in some other languages but not Python is a completely different discussion.

Linked Lists

A linked list is a linear collection of data elements. Each element points to the next, defining their ordering in the sequence. They can be used for many things like implementing stacks and queues, performing arithmetic operations on long integers, etc. See here for more examples!

There are many flavors of linked lists, but I’m going to introduce just the singly linked list. Let’s see an example and introduce some terminology.

1 -> 5 -> -2 -> None

We have three elements in the linked list above. Each element is called a node. Each node has two properties: a value and a reference to the next node in the sequence. By “reference” I mean the arrow pointing to the next value. You can think of the above linked list as the following with each box representing a node.

+------+ +------+ +-------+ 
| 1 -> | | 5 -> | | -2 -> | None
+------+ +------+ +-------+ 

I’m going to use the notation from the former example above, but just know that each node encompasses both a value and a reference to another node.

Notice how the third node references None. This is how we know we’ve found the end of the linked list because we eventually come to a point where there are no more nodes! Unlike Python lists, there are no indexes with which to reference each element in the linked list.

The first node of the linked list is called the head. We always start with the head when building our linked lists. In the example above, our head is a node with value 1 and pointing to a node with value 5.

So what? Let’s look at some things we can do with linked lists.

Insertion

We can insert elements at the beginning, middle, or end of our linked list. All we have to do is adjust how the nodes reference each other. Let’s add a node with value 0 into multiple places as an example.

At the beginning:

0 -> 1 -> 5 -> -2 -> None

This is the easiest and fastest. We just assign a new head of our list and make sure it references the old head.

In the middle after node with value 5:

1 -> 5 -> 0 -> -2 -> None

This is slower because the computer has no idea where the node with value 5 is until we iterate through to find it. Thus, we look at the head. Is that value 5? No, so we look at the next node whose value is conveniently 5. Now we just insert a new node and make sure it continues the chain of references

At the end:

1 -> 5 -> -2 -> 0 -> None

Another simple case, but takes the longest because we have to iterate through the entire list to find the last node and then add a new node at the end. Again, we make sure this continues our chain of references.

The important thing in all of these examples is that not only did we add a value, but we added a reference to the next node.

Removal

Conversely, we can remove elements from different positions in our linked list. Again, all we have to do is adjust how the nodes reference each other. We start again with the list:

1 -> 5 -> -2 -> None

At the beginning:

5 -> -2 -> None

The fastest since we just take out the first node and do nothing else.

In the middle (remove node with value 5):

1 -> -2 -> None

Slower than removal at the beginning because we have to find node with value 5 to remove it.

At the end:

1 -> 5 -> None

The slowest because we have to find the last node to remove it.

Implementation in Python

Now that we have an idea of the basic building blocks of a singly linked list, let’s look at a basic implementation of this in Python.

We require two classes in order to do this: a Node class and LinkedList class that keeps track of our head and has methods to insert/remove nodes.

Node

Recall that a node keeps track of just two things: a value and a reference to another node. Thus, our __init__() method takes care of these two things for us. We assign the reference self.next later.

LinkedList

The absolute simplest implementation of this class just keeps track of the head.

We can then construct and see our linked list above with the following assignments:

The output of the while loop is

1
5
-2

Great! Let’s look at how we might insert elements.

Insertion: Beginning

Rememeber there are three ways we can insert. Let’s start at the beginning of the linked list.

Note the self parameter due to the fact that this is actually a method within LinkedList.

We follow the same logic as explained in the visual example above. Thus, if we have

llist: 1 -> 5 -> -2

and we run

llist.push(0)

we will get the structure

0 -> 1 -> 5 -> -2 -> None

Insertion: Middle

This method may be fewer steps, but you do have to already have prev_node to insert the new node. In llist_02.py we created llist, second, and third. We could insert a node with value 0 into our linked list by calling

llist.insert_after(second, 0)

giving us

llist: 1 -> 5 -> 0 -> -2 -> None

Insertion: End

To use this in practice all we do is take our linked list and append!

llist.append(0)

Gives

llist: 1 -> 5 -> -2 -> 0 -> None

Removal

This follows the same intuition as described above and will be a nice exercise for anyone following along to try themselves. If not, I’ll have code up on my GitHub with the solutions and more.

Final Thoughts

We can use insertion and removal methods to carry out all sorts of algorithms on this data structure. The repo I linked to in the previous paragraph will ultimately be updated with some examples of this as I work through more problems.

Also, as I mentioned before, there are many flavors of linked lists, not just singly linked lists! We also have doubly linked lists, circular linked lists, etc. I’d highly recommend looking more into these if you’re interested.