Linked Lists/Python/Single

Notes

Interface

Linked list class implements the following interface:

• length
• is empty
• to string
• addFront
• addBack
• removeFront

Implementation

Basic implementation, nothing fancy: https://git.charlesreid1.com/cs/python/src/master/lists/linked-lists/LinkedList.py

Exceptions

class Empty(Exception):
    pass

Linked list nodes

class Node:
    """
    Linked List Node class.
    """
    def __init__(self,data,next_node=None):
        self.data = data
        self.next_node = next_node

    def __str__(self):
        return str(self.data)
    def get_next(self):
        return self.next_node
    def set_next(self,new_next):
        self.next_node = new_next
    def get_data(self):
        return self.data

Core class

class LinkedList:
    """
    Linked list class.

    Exposes the following interface:
    - size
    - is empty
    - addFront
    - addBack
    - removeFront
    """
    def __init__(self): 
        self.size = 0
        self.head = None

    def __len__(self):
        return self.size

    def __str__(self):
        if(self.is_empty()):
            return str([])

        sb = []
        runner = self.head 
        while(runner!=None):
            sb.append(str(runner))
            runner = runner.get_next()

        return str(sb)

    def is_empty(self):
        return self.size==0

    def add_front(self,e):
        n = Node(e)

        # point to old head:
        oldhead = self.head
        n.set_next(oldhead)

        # set new head:
        self.head = n

        self.size += 1

    def add_rear(self,e):
        if(self.is_empty()):
            add_front(e)
            return
        # make next tail
        n = Node(e)

        # find old tail
        runner = head
        while(runner.get_next()!=None):
            runner = runner.get_next()

        # set old tail to point to new tail
        runner.set_next(n)

        self.size += 1

    def remove_front(self): 
        if(self.is_empty()):
            raise Empty

        # save old and new
        oldhead = self.head
        newhead = self.head.get_next()

        # set new head
        self.head = newhead

        # return old head data
        return oldhead.get_data()

driver unit test

Simple driver unit test to ensure this thing works as expected:

if __name__=="__main__":
    z = LinkedList()

    print("Is it empty?")
    print(z.is_empty())

    z.add_front(10)
    print("Added to front:")
    print(len(z))

    z.add_front(20)
    print("Added to front:")
    print(len(z))

    z.add_front(30)
    z.add_front(40)
    z.add_front(50)
    z.add_front(60)
    print("Added to front:")
    print(len(z))

    print("Is it empty?")
    print(z.is_empty())

    print("About to remove from front:")
    print(z)
    z.remove_front()
    z.remove_front()
    z.remove_front()
    z.remove_front()
    print("Removed from front:")
    print(z)

    print("Here is the list:")
    print(z)