The single-linked list is a data structure which consists of a series of Node objects, which form a chain. Each node has a reference to the next node in the chain. No node will refer back to an earlier node in the chain, i.e., no cycles will exist in the single-linked list. The last node will refer to None. A special LinkedList class contains a reference to the first object in the single-linked list.

Below is an implementation of a single-linked list. The SingleLinkedList class contains a head attribute that points to the first object in the chain. Moreover, it contains a method add that adds a new object to the head of the chain, and a remove method that removes the head of the sequence.

The nodes in the sequence are implemented as instances of the SingleNode class. They only contain the object that the node represents, and a reference to the next node.

class SingleNode:
    def __init__( self, value, nextnode ):
        self.value = value
        self.nextnode = nextnode
        
class SingleLinkedList:
    def __init__( self ):
        self.head = None
    def add( self, value ):
        node = SingleNode( value, self.head )
        self.head = node
    def remove( self ):
        if self.head != None:
            self.head = self.head.nextnode
            
sll = SingleLinkedList()
sll.add( 1 )
sll.add( 2 )
sll.add( 3 )

cur = sll.head
while cur != None:
    print( cur.value )
    cur = cur.nextnode

As you can see, traversing the linked list means starting at the head, and then following the chain of nextnode references until the end.

Naturally, a better implementation of the SingleLinkedList class would include methods to traverse the chain, rather than having the programmer who uses the class access the head and nextnode attributes in the main code. I will leave that to the students as an exercise, though (see the Exercises section below).

Efficiency of a single-linked list

You might wonder why you would ever use a single-linked list, which only allows adding new values at the front of the chain, when a regular Python list can do so much more. One reason to use one might be that a single-linked list is much more efficient than a Python list. The reason is that a Python list is implemented as an array (see the chapter on sorting), which is an efficient data structure for looking up items by their index, but a very inefficient data structure for inserting or removing items, unless they reside at the end of the list. This can be demonstrated by comparing two blocks of equivalent code, which add 100,000 numbers at the front of a chain.

The first uses a regular Python list:

from datetime import datetime

COUNT = 100000
numlist = []

start = datetime.now()

for i in range( COUNT ):
    numlist.insert( 0, i )
    
end = datetime.now()

print( "{}.{} seconds needed to insert {} numbers".format( 
        (end - start).seconds, (end - start).microseconds, COUNT ) )

The second uses the SingleLinkedList class defined above.

from datetime import datetime

class SingleNode:
    def __init__( self, value, nextnode ):
        self.value = value
        self.nextnode = nextnode
        
class SingleLinkedList:
    def __init__( self ):
        self.head = None
    def add( self, value ):
        node = SingleNode( value, self.head )
        self.head = node
    def remove( self ):
        if self.head != None:
            self.head = self.head.nextnode
            
COUNT = 100000

start = datetime.now()

sll = SingleLinkedList()
for i in range( 1, COUNT ):
    sll.add( i )
    
end = datetime.now()

print( "{}.{} seconds needed to insert {} numbers".format( 
        (end - start).seconds, (end - start).microseconds, COUNT ) )

On my computer, the first block of code needs about 2 seconds to insert the 100,000 numbers, while the second needs less than 1. However, when increasing the task to inserting 1,000,000 numbers, the first block needs about 3 minutes, while the second is done in just over 1 second.

Exercise: What is the time complexity of these two blocks of code?

Answer: As I discussed in the chapter on sorting, inserting in a Python list is O(n²). For the single-linked list, insertion of one item needs constant time, since nothing needs to be moved in memory. Therefore, insertion of n items is O(n).

If you wonder why increasing the number of items 10-fold does not require 10 times as much time for the linked list, the answer is that there is always some startup time involved for creating the basic class definitions and setting up the range().

Appending to a single-linked list

The single-linked list as described above can only add new items at the front of the chain. To allow appending items at the end of the chain, a separate reference to the end of the chain is needed.

class SingleNode:
    def __init__( self, value, nextnode ):
        self.value = value
        self.nextnode = nextnode
        
class SingleLinkedList:
    def __init__( self ):
        self.head = None
        self.tail = None
    def add( self, value ):
        node = SingleNode( value, self.head )
        self.head = node
        if self.tail == None:
            self.tail = self.head
    def remove( self ):
        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.head = self.head.nextnode
    def append( self, value ):
        node = SingleNode( value, None )
        if self.tail == None:
            self.head = node
            self.tail = node
        else:
            self.tail.nextnode = node
            self.tail = node
            
sll = SingleLinkedList()
sll.add( 1 )
sll.add( 2 )
sll.add( 3 )
sll.append( 4 )
sll.append( 5 )

cur = sll.head
while cur != None:
    print( cur.value )
    cur = cur.nextnode

Note that adding a reference to the tail of the single-linked list, which allows an efficient implementation of the append() method, also impacts the implementation of the other methods. Special care must be taken when adding to an empty chain, as this influences both the head and the tail. Special care must also be taken when removing from a chain with only one item, as this will set both the head and tail to None.

Also take note of the fact that in the append() method, first the new node gets added to the tail of the chain, and only then the value of tail is adapted. It would not work the other way around, because by changing the value of tail, I no longer have access to the nextnode of the original tail.

If besides appending at the end of the list, I also want to allow inserting items in the list, I will need to add at least two methods: one to find() a particular item in the chain, after which the new item is to be inserted, and one to insert() the new item at that spot in the chain. Insertion, in pseudocode, would be something like:

spot = sll.find( location )
node = SingleNode( value, spot.nextnode )
spot.nextnode = node

Of course, I will have to deal with the special cases of having an empty chain, inserting a new node at the start of the list (which will change the head), and inserting a new node after the tail (which will change the tail). Rather than discussing this now, I will bring it up for double-linked lists.