# Singly linked list (Python)

This is a simple implementation of a singly-linked list in Python.

Note that in Python it is more idiomatic and efficient to use the built-in list data structure. This is only an exercise to demonstrate how singly-linked lists are constructed, and should not be used in production code.

## Contents |

## [edit] Creating and manipulating a list

### [edit] Nodes

A linked list is made up of nodes. Each node contains a single piece of data and a reference to the next node. We will represent each node using an object of class ListNode:

<<ListNode class>>=classListNode:def __init__(self, data, next):self.data = data self.next = next

The ListNode constructor is similar to the "car" construct in Lisp. It allows us to manually build up a list in reverse order as follows:

node3 = ListNode(3, None) node2 = ListNode(2, node3) node1 = ListNode(1, node2)

Because Python is dynamically typed, nodes can hold data of any type; however, next should only point to another ListNode, or to `None`

if there isn't one.

### [edit] Inserting a node

In a singly-linked list, there is no efficient way to insert a node before a given node, but we can insert a node after a given node or at the beginning or end of the list. Our list class will keep track of the first node in the list in its "head" instance variable, and the last node of the list in its "tail" instance variable, both initially set to None for an empty list:

<<List class>>=classList:def __init__(self):self.head = None self.tail = None

The following code creates and inserts a new node after an existing node, taking care to update tail when inserting at the end:

<<List class>>=def insert(self, node, data):new_node = ListNode(data, node.next) node.next = new_nodeifself.tail == node: self.tail = new_node

For example, suppose we are inserting B after A and before C. Initially, A is first and A.next refers to C. The first line creates the node for B and points B.next to C. The second line sets A.next to B instead of C. Inserting at the end is now easy - we just have to deal with the empty list specially:

<<List class>>=def insert_end(self, data):ifself.tailisNone: new_node = ListNode(data, None) self.head = self.tail = new_nodeelse: self.insert(self.tail, data)

The above code cannot insert at the beginning of the list, so we have a separate function for this. This code must update self.head:

<<List class>>=def insert_beginning(self, data):new_node = ListNode(data, self.head) self.head = new_node

### [edit] Removing a node

Removing a node is easy given access to the previous node, by modifying the next pointer to "skip" over the removed node, taking care to update tail as needed:

<<List class>>=def remove_after(self, node):node.next = node.next.nextifnode.nextisNone: self.tail = node

Again, a special method is required to remove the first node:

<<List class>>=def remove_beginning(self):self.head = self.head.nextifself.headisNone: self.tail = None

## [edit] Operating on the entire list

### [edit] Traversing a list

We can iterate over the list using a simple loop, which starts at `list.head`

and traverses all the next pointers to visit every node:

<<iteration using a loop>>=node = list.headwhilenodeisnotNone:

Using anonymous (lambda) functions, we can create a method on List to facilitate this common pattern:

<<List class>>=def iterate(self, func):node = list.headwhilenodeisnotNone: func(node.data) node = node.next<<iteration using lambda>>=list.iterate(lambdax:

Note that in order to use print inside a lambda, we must import the Python 3 print function, since lambda can only accept expressions and not statements:

<<imported symbols>>=from__future__importprint_function

### [edit] Searching a list

A common operation is to identify the first node with a given data value:

<<List class>>=def find_first(self, data):node = list.headwhilenodeisnotNone:ifnode.data == data:returnnode node = node.next

More generally, we can have the user supply a predicate (function returning a boolean) and return the first node for which it returns true:

<<List class>>=def find_first_func(self, func):node = list.headwhilenodeisnotNone:iffunc(node.data):returnnode node = node.next

The original `find_first`

could now be written as:

find_first_func(lambdax: x == data)

Given a list of candidate solutions to an equation, find_first_func can be used to search them for the answer:

<<find solution to equation>>=node = list.find_first_func(lambdax: 2*x + 7 == 19)

## [edit] Testing the list

We will need to construct a list to test our methods with:

<<construct test list>>=list = List()forxinrange(1,10): list.insert_end(x)

We can now build a complete program using all the methods of the List class:

<<list.py>>=imported symbols ListNode class List class construct test list iteration using a loop iteration using lambda list.insert(list.find_first(7), 13) iteration using lambda list.remove_after(list.find_first(7)) iteration using lambda list.insert_beginning(-5) iteration using lambda list.remove_beginning() iteration using lambda find solution to equation

Download code |