I was reading about data structures this evening and I worked out simple singly linked list. The neat thing about this implementation is that a I made it iterable, also. I’d originally wanted to provide a minimal working singly linked list, and then add features and testing with explanations, but it’s been a long day. This example assumes that you’re using Python2.7; version 3 provides a __next__ class method.

Another neat thing about this implementation is that you get Stack and Queue data structures for free. You can turn this into a Stack by deleting the popLast() and addLast() methods, or Queue by deleting the popFirst() and addLast(). If you can manage with the awkward names, then you should be fine.

class SinglyLinkedList:
    
    class Node:
        def __init__( self, data, nextNode ):
            self.nextNode = nextNode
            self.data = data
        
    def __init__( self ):
        self.first = None
        self.last = None
        self.count = 0
        self.current = None
    def addFirst( self, data ):
        if self.count == 0:
            self.first = self.Node( data, None )
            self.last = self.first
        elif self.count > 0:
            self.first = self.Node( data, self.first )
        self.current= self.first
        self.count += 1
    def addLast( self, data ):
        if self.count == 0:
            self.addFirst( data )
        elif self.count > 0:
            self.last.nextNode = self.Node( data, None )
            self.last = self.last.nextNode
            self.count += 1
    def popLast( self ):
        cursor = self.first
        if self.count == 0:
            raise RuntimeError("Cannot pop from an empty linked list")
        elif self.count == 1:
            result = cursor.data
            self.first = None
            self.last = None
            self.current = None
        else:
            for i in range( self.count-2 ):
                cursor = cursor.nextNode
            result = cursor.nextNode.data
            self.last = cursor
            self.last.nextNode = None
        self.count -= 1
        return result
    def popFirst( self ):
        if self.count == 0:
            raise RuntimeError("Cannot pop from an empty linked list")
        result = self.first.data
        if self.count == 1:
            self.first = None
            self.last = None
        else:
            self.first = self.first.nextNode
        self.current = self.first
        self.count -= 1
        return result
    def __repr__( self ):
        result = ""
        if self.count == 0:
            return "..."
        cursor = self.first
        for i in range( self.count ):
            result += "{}".format(cursor.data)
            cursor = cursor.nextNode
            if cursor is not None:
                result += " -> "
        return result
    def __iter__( self ):
        # lets Python know this class is iterable
        return self
    def next( self ):
        # provides things iterating over class with next element
        if self.current is None:
            # allows us to re-iterate
            self.current = self.first
            raise StopIteration
        else:
            result = self.current.data
            self.current = self.current.nextNode
            return result
    def __len__( self ):
        return self.count

sll = SinglyLinkedList()
sll.addLast("!!")
sll.addFirst("pls")
sll.addFirst("me")
sll.addFirst("halp")
sll.addLast("!!!")

assert sll.count > 0
assert len( sll ) == 5
assert list( sll ) == ["halp","me","pls","!!", "!!!"]
assert sll.popLast() == "!!!"
assert list( sll ) == ["halp","me","pls","!!"]