Problem Solving with Algorithms and Data Structures - Lists http://interactivepython.org/runestone/static/pythonds/BasicDS/Lists.html

Node.py

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

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self,newdata):
        self.data = newdata

    def setNext(self,newnext):
        self.next = newnext

OrderedList.py

from Node import Node

class OrderedList:

    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def add(self,item):
        current = self.head
        previous = None
        stop = False
        while current != None and not stop:
            if current.getData() > item:
                stop = True
            else:
                previous = current
                current = current.getNext()
        temp = Node(item)
        if previous == None:
            temp.setNext(self.head)
            self.head = temp
        else:
            temp.setNext(current)
            previous.setNext(temp)

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

    def search(self,item):
        if self.index(item) != None:
            return True
        else:
            return False

    def remove(self,item):
        index = self.index(item)
        if index != None:
            self.pop(index)

    def index(self,item):
        current = self.head
        found = False
        stop = False
        index = -1
        while current != None and not found and not stop:
            index += 1
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    stop = True
                else:
                    current = current.getNext()
        if found:
            return index
        else:
            return None

    def pop(self,pos = None):
        size = self.size()
        if pos == None or pos >= size:
            pos = size-1
        current = self.head
        previous = None
        index = 0
        while index != pos:
            index += 1
            previous = current
            current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())
        return current.getData()

OrderedList_Test.py

from OrderedList import OrderedList

if __name__ == '__main__':
    mylist = OrderedList()
    mylist.add(31)
    mylist.add(77)
    mylist.add(17)
    mylist.add(93)
    mylist.add(26)
    mylist.add(54)

    print(mylist.size())
    print(mylist.search(93))
    print(mylist.search(100))

OrderedList_UnitTest.py

import unittest
from OrderedList import OrderedList

class TestOrderedList(unittest.TestCase):

    def setUp(self):
        self.mylist = OrderedList()
        self.mylist.add(31)
        self.mylist.add(77)
        self.mylist.add(17)
        self.mylist.add(93)
        self.mylist.add(26)
        self.mylist.add(54)

    def test_isEmpty(self):
        newlist = OrderedList()
        self.assertTrue(newlist.isEmpty())

    def test_add(self):
        newlist = OrderedList()
        self.assertTrue(newlist.isEmpty())
        newlist.add(31)
        newlist.add(77)
        newlist.add(17)
        newlist.add(93)
        newlist.add(26)
        newlist.add(54)
        self.assertFalse(newlist.isEmpty())

    def test_size(self):
        self.assertEqual(self.mylist.size(), 6)

    def test_search(self):
        self.assertTrue(self.mylist.search(77))
        self.assertFalse(self.mylist.search(76))

    def test_remove(self):
        self.mylist.remove(76)
        self.assertEqual(self.mylist.size(), 6)
        self.mylist.remove(77)
        self.assertEqual(self.mylist.size(), 5)

    def test_index(self):
        self.assertEqual(self.mylist.index(17), 0)
        self.assertEqual(self.mylist.index(26), 1)
        self.assertEqual(self.mylist.index(31), 2)
        self.assertEqual(self.mylist.index(54), 3)
        self.assertEqual(self.mylist.index(77), 4)
        self.assertEqual(self.mylist.index(93), 5)

    def test_pop(self):
        self.assertEqual(self.mylist.size(), 6)
        self.assertEqual(self.mylist.pop(), 93)
        self.assertEqual(self.mylist.size(), 5)
        self.assertEqual(self.mylist.pop(2), 31)
        self.assertEqual(self.mylist.size(), 4)

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

UnorderedList.py

from Node import Node

class UnorderedList:

    def __init__(self):
        self.head = None
        self.tail = None

    def isEmpty(self):
        return self.head == None

    def add(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
        if temp.getNext() == None:
            self.tail = temp

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count

    def search(self,item):
        if self.index(item) != None:
            return True
        else:
            return False

    def remove(self,item):
        index = self.index(item)
        if index != None:
            self.pop(index)

    def append(self,item):
        temp = Node(item)
        if self.tail == None:
            self.head = temp
        else:
            self.tail.setNext(temp)
        self.tail = temp

    def index(self,item):
        current = self.head
        found = False
        index = -1
        while current != None and not found:
            index += 1
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        if found:
            return index
        else:
            return None

    def insert(self,pos,item):
        temp = Node(item)
        size = self.size()
        if pos > size:
            pos = size
        current = self.head
        index = 0
        while index != pos-1:
            index += 1
            current = current.getNext()
        temp.setNext(current.getNext())
        current.setNext(temp)
        if temp.getNext() == None:
            self.tail = temp

    def pop(self,pos = None):
        size = self.size()
        if pos == None or pos >= size:
            pos = size-1
        current = self.head
        previous = None
        index = 0
        while index != pos:
            index += 1
            previous = current
            current = current.getNext()
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())
        if previous.getNext() == None:
            self.tail = previous
        return current.getData()

UnorderedList_Test.py

from UnorderedList import UnorderedList

if __name__ == '__main__':
    mylist = UnorderedList()

    mylist.add(31)
    mylist.add(77)
    mylist.add(17)
    mylist.add(93)
    mylist.add(26)
    mylist.add(54)

    print(mylist.size())
    print(mylist.search(93))
    print(mylist.search(100))

    mylist.add(100)
    print(mylist.search(100))
    print(mylist.size())

    mylist.remove(54)
    print(mylist.size())
    mylist.remove(93)
    print(mylist.size())
    mylist.remove(31)
    print(mylist.size())
    print(mylist.search(93))

UnorderedList_UnitTest.py

import unittest
from UnorderedList import UnorderedList

class TestUnorderedList(unittest.TestCase):

    def setUp(self):
        self.mylist = UnorderedList()
        self.mylist.add(17)
        self.mylist.add(77)
        self.mylist.add(31)
        self.mylist.add(93)
        self.mylist.add(26)
        self.mylist.add(54)

    def test_isEmpty(self):
        newlist = UnorderedList()
        self.assertTrue(newlist.isEmpty())

    def test_add(self):
        newlist = UnorderedList()
        self.assertTrue(newlist.isEmpty())
        newlist.add(17)
        newlist.add(77)
        newlist.add(31)
        newlist.add(93)
        newlist.add(26)
        newlist.add(54)
        self.assertFalse(newlist.isEmpty())

    def test_size(self):
        self.assertEqual(self.mylist.size(), 6)

    def test_search(self):
        self.assertTrue(self.mylist.search(77))
        self.assertFalse(self.mylist.search(76))

    def test_remove(self):
        self.mylist.remove(76)
        self.assertEqual(self.mylist.size(), 6)
        self.mylist.remove(77)
        self.assertEqual(self.mylist.size(), 5)

    def test_append(self):
        self.assertEqual(self.mylist.size(), 6)
        self.mylist.append(66)
        self.assertEqual(self.mylist.size(), 7)
        self.assertEqual(self.mylist.index(66), 6)

    def test_index(self):
        self.assertEqual(self.mylist.index(17), 5)
        self.assertEqual(self.mylist.index(77), 4)
        self.assertEqual(self.mylist.index(31), 3)
        self.assertEqual(self.mylist.index(93), 2)
        self.assertEqual(self.mylist.index(26), 1)
        self.assertEqual(self.mylist.index(54), 0)

    def test_insert(self):
        self.assertEqual(self.mylist.size(), 6)
        self.mylist.insert(2, 66)
        self.assertEqual(self.mylist.size(), 7)
        self.assertEqual(self.mylist.index(66), 2)

    def test_pop(self):
        self.assertEqual(self.mylist.size(), 6)
        self.assertEqual(self.mylist.pop(), 17)
        self.assertEqual(self.mylist.size(), 5)
        self.assertEqual(self.mylist.pop(2), 93)
        self.assertEqual(self.mylist.size(), 4)

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