Singly linked list (Python)

From LiteratePrograms
Jump to: navigation, search
Other implementations: C | C++ | 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>>=
class ListNode:
    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>>=
class List:
    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_node
        if self.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):
        if self.tail is None:
            new_node = ListNode(data, None)
            self.head = self.tail = new_node
        else:
            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.next
        if node.next is None:
            self.tail = node

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

<<List class>>=
    def remove_beginning(self):
        self.head = self.head.next
        if self.head is None:
            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.head
while node is not None:
    print(node.data)
    node = node.next
print()

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

<<List class>>=
    def iterate(self, func):
        node = list.head
        while node is not None:
            func(node.data)
            node = node.next

<<iteration using lambda>>=
list.iterate(lambda x: print(x))
print()

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__ import print_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.head
        while node is not None:
            if node.data == data:
                return node
            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.head
        while node is not None:
            if func(node.data):
                return node
            node = node.next

The original find_first could now be written as:

find_first_func(lambda x: 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(lambda x: 2*x + 7 == 19)
print(node.data)

[edit] Testing the list

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

<<construct test list>>=
list = List()
for x in range(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
hijacker
hijacker
hijacker
hijacker