Python Linked List

Test file

Create file linked_list_test.py:

import unittest
import linked_list


class LinkedListTest(unittest.TestCase):
    def test_insert_node_at_head(self):
        base = linked_list.Node(2)
        assess = [
            {
                "init": linked_list.LinkedList(),
                "input": linked_list.Node(8),
                "expectedLen": 1,
                "expectedData": 8,
                "expectedNext": None,
            },
            {
                "init": linked_list.LinkedList(base),
                "input": linked_list.Node(8),
                "expectedLen": 2,
                "expectedData": 8,
                "expectedNext": base,
            },
        ]
        for test in assess:
            test["init"].insertFirst(test["input"])
            # assert expected length
            self.assertEqual(test["init"].size, test["expectedLen"])
            # assert first el is the input Node
            self.assertEqual(test["init"].head, test["input"])
            # Assert data at head == Node data
            self.assertEqual(test["init"].head.data, test["expectedData"])
            # Assert head next == Node next
            self.assertEqual(test["init"].head.next, test["expectedNext"])

    def test_get_node_size(self):
        l = linked_list.LinkedList()
        self.assertEqual(l.getSize(), 0)

        n1 = linked_list.Node(2)
        l.insertFirst(n1)
        self.assertEqual(l.getSize(), 1)

        n2 = linked_list.Node(10)
        l.insertFirst(n2)
        self.assertEqual(l.getSize(), 2)

    def test_get_first(self):
        l = linked_list.LinkedList()
        self.assertEqual(l.getSize(), 0)

        n1 = linked_list.Node(2)
        l.insertFirst(n1)
        self.assertEqual(l.getFirst(), n1)

        n2 = linked_list.Node(10)
        l.insertFirst(n2)
        self.assertEqual(l.getFirst(), n2)

    def test_get_last(self):
        l = linked_list.LinkedList()
        self.assertEqual(l.getSize(), 0)

        n1 = linked_list.Node(2)
        l.insertFirst(n1)
        self.assertEqual(l.getLast(), n1)

        n2 = linked_list.Node(10)
        l.insertLast(n2)
        self.assertEqual(l.getLast(), n2)

    def test_insert_last(self):
        l = linked_list.LinkedList()

        n1 = linked_list.Node(2)
        l.insertLast(n1)
        self.assertEqual(l.getLast(), n1)

        n2 = linked_list.Node(10)
        l.insertLast(n2)
        self.assertEqual(l.getLast(), n2)

    def test_clear(self):
        l = linked_list.LinkedList()
        n1 = linked_list.Node(2)
        n2 = linked_list.Node(10)
        l.insertLast(n1)
        l.insertLast(n2)
        self.assertEqual(l.getSize(), 2)
        l.clear()
        self.assertEqual(l.getSize(), 0)

    def test_remove_first(self):
        l = linked_list.LinkedList()
        n1 = linked_list.Node(2)
        n2 = linked_list.Node(10)
        l.insertLast(n1)
        l.insertFirst(n2)
        self.assertEqual(l.getSize(), 2)
        l.removeFirst()
        self.assertEqual(l.getFirst(), n1)

    def test_remove_last(self):
        l = linked_list.LinkedList()
        n1 = linked_list.Node(2)
        n2 = linked_list.Node(10)
        n3 = linked_list.Node(11)
        n4 = linked_list.Node(29)
        l.insertLast(n1)
        l.insertLast(n2)
        l.insertLast(n3)
        l.insertLast(n4)
        self.assertEqual(l.getSize(), 4)
        l.removeLast()
        self.assertEqual(l.getLast(), n3)
        l.removeLast()
        self.assertEqual(l.getLast(), n2)

    def test_remove_last(self):
        l = linked_list.LinkedList()
        n1 = linked_list.Node(2)
        n2 = linked_list.Node(10)
        n3 = linked_list.Node(11)
        n4 = linked_list.Node(29)
        l.insertLast(n1)
        l.insertLast(n2)
        l.insertLast(n3)
        l.insertLast(n4)
        self.assertEqual(l.getSize(), 4)
        l.removeLast()
        self.assertEqual(l.getLast(), n3)
        l.removeLast()
        self.assertEqual(l.getLast(), n2)

    def test_get_at(self):
        l = linked_list.LinkedList()
        n1 = linked_list.Node(2)
        n2 = linked_list.Node(10)
        n3 = linked_list.Node(11)
        n4 = linked_list.Node(29)
        l.insertLast(n1)
        l.insertLast(n2)
        l.insertLast(n3)
        l.insertLast(n4)
        self.assertEqual(l.getAt(1), n2)
        self.assertEqual(l.getAt(2), n3)
        self.assertEqual(l.getAt(3), n4)

    def test_insert_at(self):
        l = linked_list.LinkedList()
        n1 = linked_list.Node(2)
        n2 = linked_list.Node(10)
        n3 = linked_list.Node(11)
        n4 = linked_list.Node(29)
        n5 = linked_list.Node(31)
        l.insertFirst(n1)
        l.insertFirst(n2)
        l.insertAt(1, n3)
        l.insertAt(2, n4)
        l.insertAt(4, n5)
        self.assertEqual(l.getAt(1), n3)
        self.assertEqual(l.getAt(2), n4)
        self.assertEqual(l.getAt(4), n5)


if __name__ == '__main__':
    unittest.main()
copy

Linked Lists

Create file trees.py.

"""
Methods:

1. insertFirst: Insert at the head of list
2. size: Fetch size
3. getFirst: Fetch the first node
4. getLast: Fetch the last node
5. clear: Remove all node
6. removeFirst: Remove head of list
7. removeLast: Remove last node
8. insertLast: Insert at end of list
9. getAt: Fetch node at index
10. removeAt: Remove node at index
11. insertAt: Insert at index
12. forEach: Iterate through list and run function on list
"""


class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


class LinkedList:
    def __init__(self, head=None):
        self.head = head
        if head:
            self.size = 1
        else:
            self.size = 0

    def insertFirst(self, node):
        if self.head:
            tmp = self.head
            self.head = node
            node.next = tmp
        else:
            self.head = node
        self.size += 1

    def getSize(self):
        return self.size

    def getFirst(self):
        return self.head

    def getLast(self):
        # check if head
        if self.head == None:
            raise Exception("No head of list")

        node = self.head
        # if head, iterate until node next is None
        while node.next != None:
            node = node.next
        return node

    def insertLast(self, node):
        if self.head == None:
            self.head = node
            self.size += 1
            return

        n = self.head
        while n.next != None:
            n = n.next
        n.next = node
        self.size += 1

    def clear(self):
        self.head = None
        self.size = 0

    def removeFirst(self):
        if self.head == None:
            raise Exception("No head of list")

        tmp = self.head.next
        self.head = tmp
        self.size -= 1

    def removeLast(self):
        if self.head == None:
            raise Exception("No list length")

        if self.head.next == None:
            self.head = None
            self.size -= 1
            return

        n = self.head
        while n.next.next:
            n = n.next
        n.next = None
        self.size -= 1

    def getAt(self, index):
        count = 0
        if self.head == None:
            raise Exception("No items in list")

        n = self.head
        while count != index:
            if n.next == None:
                raise Exception("Out of bounds")
            n = n.next
            count += 1

        return n

    def insertAt(self, index, node):
        count = 0

        if self.head == None and index > 0:
            raise Exception("Out of bounds")
        elif self.head == None and index == 0:
            self.head = node
            self.size += 1
            return
        elif self.head != None and index == 0:
            tmp = self.head
            self.head = node
            node.next = tmp
            self.size += 1
            return

        prev = self.head
        n = self.head.next
        while count != index - 1:
            if prev.next == None:
                raise Exception("Out of bounds")
            prev = n
            n = n.next
            count += 1
        prev.next = node
        node.next = n
        self.size += 1
copy

Running tests

Change into directory and run python3 -m pytest -v linked_list_test.py.