# How to Implement a Linked List in Python

Need a quick run down on a classic data structure? Look no further.

**Click here for the full LinkedList source code. Also, here is the test code.**

A linked list is an ordered collection of elements. The thing that makes it special is how it stores data. Behind the scenes, each number, string, object, or other value you may need to keep track of is stored in a Node. Each Node references its successor.

The advantage to this approach is the dynamic nature of the list. Unless you run out of memory, **you can't run out of space in a linked list**, because the last Node in the list always has room to reference another Node. Conversely, when you run out of space in a flat array, you need to create a new, larger array and fill it with the data from the original, which can be inefficient.

In this case, we will be talking about a **singly linked list**, meaning that each Node only has one reference, which belongs to the **next** Node. For a **doubly linked list**, there would be an additional reference to the **previous** Node.

##

Nodes and RopesThe concept of a **Node** is central to linked lists. A linked list Node contains two important fields:

and`next_node`

data

. The field next_node

refers to another Node object, the next element in the list. The data

field refers to whatever you are actually storing in the list, which could be anything from a name or phone number to the result of a computation.
An easy way to visualize a linked list is by picturing each Node as a box. The box has space for you to hold your

. It also has a hole with a rope coming out - this rope is the`data`

next_node

reference. When you create your list and add elements, you are essentially tying each Node

's rope to the next one in line.
Putting this idea into code will yield the following

object:`Node`

class Node(object): def __init__(self, d): self.next_node = None self.data = d

##

List Setup - Heads and TailsUnlike a regular flat array, we can't access each list item by index. Instead, we must iterate from one of two points of reference: the

and the`head`

tail

of the list, each of which contain a Node object. Think of these as the only two "handles" we have to grab the list by. From the head

, we can work our way down the list by following next_node

references unitl we reach the tail

.
Keep in mind that while the

and`head`

tail

hold Node objects, they are set to None

when the list is created. This is because the list starts out empty, so we don't have any Node objects to use for them.
class LinkedList(object): def __init__(self): self.head = None self.tail = None self.size = 0

##

Adding elementsAdding an element to a list involves updating the

references of surrounding Nodes to integrate it into the list, "tying" all the ropes in their proper places. The simplest situation to consider is when a node is added to the end of a list. In this case, simply update`next_node`

tail.next_node

to point to your new node. At this point, the new node is the last element in the list, so you should update tail

to reflect this.
Note that if the list is empty, you only need to set

and`head`

tail

to your new list node. In either case, increment the list's size by one. Adding a node to the end of the list is completed in O(1) time.
# Add d to tail of list def add(self, d): new_node = Node(d) if self.tail: self.tail.next_node = new_node self.tail = new_node else: self.head = new_node self.tail = new_node self.size += 1

Adding a node at a specific index in the list is a more complex operation. To do this, you need to iterate the list to find the

at the index you will be inserting the new data, as well as the`current_node`

previous

node. Once you have these references, tie the previous node to the new node, and the new node to the rest of the list. In code, this would mean setting previous.next_node = new_node

and new_node.next_node = current_node

.
# Return True if d is in list, false otherwise def find(self, d): current_node = self.head while current_node: if current_node.data == d: return True current_node = current_node.next_node return False

##

Removing elementsRemoving an element is fairly straightforward, though it may seem counterintuitive at first. You need two references:

, the node`previous`

**before**the one you are deleting, and

node

, the one you are deleting. Once you have checked and found the data

you need in node

, simply set previous.next_node = node.next_node

. This snippet of code reassigns the previous node from pointing to the node we are deleting to the node beyond it. In this way, the node

we are deleting is not set as the next_node

of any other node. Since nothing references it, it is as good as gone - Garbage collection will see that it gets deleted.
Once you have the

and`previous`

node

references, the remove operation has a time complexity of O(1).
# Remove d; return True if successful, false otherwise def remove(self, d): previous_node = None current_node = self.head while current_node: if current_node.data == d: if previous_node: previous_node.next_node = current_node.next_node else: self.head = current_node.next_node self.size -= 1 return True previous_node = current_node current_node = current_node.next_node return False

##

Finding elementsFinding an element in your linked list is not as simple as jumping to the index you would like to access. The only way we can interact with the list is through the

node,`head`

tail

node, and the links between them. The find operation will make use of a scratch variable, current_node

, to keep track of which element of the list we are currently interacting with. To begin the find operation, set current_node = self.head

.
Next, begin a loop. For each iteration, check if you found the data you are

ing. If you found it, great - return either`find`

True

, the data, or the Node; what you return depends on how you plan to use the Linked List. If you did not find it, set current_node = current_node.next_node

, and begin the next iteration. This assignment moves your current_node

pointer onto the next list element, allowing you to perform your check on every item in the list.
The find operation has a time complexity of O(n).

# Return True if d is in list, false otherwise def find(self, d): current_node = self.head while current_node: if current_node.data == d: return True current_node = current_node.next_node return False

##

TestingTyping

on the command prompt will bring up an interactive shell in which you can interact with your new Linked List. Just make sure that you import it. If your linked list is stored in`python3`

linked_list.py

, then simply type from linked_list import LinkedList

. Create a new LinkedList object with something like l = LinkedList()

.
Personally, I find it tiresome to constantly run through all the methods to make sure they work and that a small change didn't break them. For this reason, I use python's

framework to run a series of tests over and over on my list until I get it right. You can use the tests I wrote as a template if you want to get started with unit testing in Python. To run the tests, open a terminal and type`unittest`

python3 -m unittest test_linked_list.py

. To run any files with the name prefix test_

, type python3 -m unittest discover

to automatically detect them.
##

ChallengesUp for a challenge? Given our completed LinkedList code, I have two more methods for you to try implementing:

`find_at(self, index):`

- Return the

found atdata

. If there is noindex

atNode

, returnindexNone

`remove_at(self, index):`

**Remove**and return the

found atdata

. If there is noindex

atNode

, returnindexNone

When you're done, leave a comment with a link to your completed challenges and any tests that go with them!

##

Full SourceIf you want to see all of the code for our finished LinkedList, check out the source on Github.