SOLVED CSE2050 Homework 04: Double Linked List

Objectives

• Double Linked List implementation

Activities

Doubly Linked Lists (DLLs) support O(1) removal from the end of the ADT developed in Lab 4.

1. Copy and save your LinkedList.py to DoublyLinkedList.py.
2. Rename your LinkedList Class to DoublyLinkedList and expand it to implement a Doubly Linked List that will remove a node from the end of the structure remove_last()in O(1).
3. Use the same TestLinkedList.py file from the lab to test your new implementation.
4. Provide a listing of DoublyLinkedList.py below. If you needed to change your TestLinkedList.py file based on feedback from your Lab 4 submission also include a listing of TestLinkedList.py.
5. class Node:
     """"Class to define a node in a linked list"""
     def __init__(self, item, _next=None, _prev=None):
         """"Constructor of the Node, builds the item (data) and the link to the next node _next"""
         self.item = item
         self._next = _next
         self._prev = _prev
   
     def __repr__(self):
         """Returns the Node data and what it is pointing to, and wthe previous node"""
         return f"Node({self.item}, {self._next}, {self._prev} )"
   
     def __iter__(self):
         """"Allows for the iteration over Nodes"""
         yield self.item
         if self._next is not None:
             yield from self._next
   
   
   class DoublyLinkedList:
     """Class defining the Linked List ADT and her methods"""
     def __init__(self, items=None):
         """Initialise the LinkedList with a head, tail and length."""
         self._head = None
         self._tail = None
         self._length = 0
   
         if items is not None:
             for item in items:
                 self.addlast(item)
   
     def addfirst(self, item):
         """Adds a new node at the beginning of the linked list."""
         new_node = Node(item, self._head)
         if self._head is not None:
             self._head._prev = new_node
         self._head = new_node
         if self._tail is None:
             self._tail = self._head
         self._length += 1
   
     def addlast(self, item):
         """Adds a new node at the end of the linked list."""
         new_node = Node(item, None, self._tail)
         if self._tail is not None:
             self._tail._next = new_node
         self._tail = new_node
         if self._head is None:
             self._head = new_node
         self._length += 1
   
     def remove_first(self):
         """Removes the first node from the linked list."""
         if self._head is None:
             return None # or raise an exception
         item = self._head.item
       self._head = self._head._next
         if self._head is not None:
             self._head._prev = None
         else:
             self._tail = None
         self._length -= 1
         return item
   
     def remove_last(self):
         """Removes the last node from the linked list in O(1) time."""
         if self._tail is None:
             return None
         item = self._tail.item
         self._tail = self._tail._prev
         if self._tail is not None:
             self._tail._next = None
         else:
             self._head = None
         self._length -= 1
         return item
   
     def __str__(self):
         """Formats the str magic method to return human-readable representation of linked list"""
         string = 'Your linked list contains: '
         currentnode = self._head
         while currentnode is not None:
             string += str(currentnode.item)
             currentnode = currentnode._next
             if currentnode is not None:
                 string += " ~and~ "
         return string
   
     def __len__(self):
         """Returns length of the linked list"""
         return self._length
   
     def __iter__(self):
         """Modifies the iter magic method to allow for iteration on linked list"""
         if self._head is not None:
             yield from self._head
   
     def __repr__(self):
         """Returns a more basic representation of the linked list"""
         items = []
         for item in self:
             items.append(str(item))
         return f"LinkedList({items})"

import unittest

from DoublyLinkedList import DoublyLinkedList



class TestDoublyLinkedList(unittest.TestCase):



   def test_addfirst(self):

       """Test for adding a node to the beginning of a Linked List"""

       ll = DoublyLinkedList()

       ll.addfirst(1)

       self.assertEqual(repr(ll),"LinkedList(['1'])")



   def test_addlast(self):

       """Tests for adding a node to the end of a Linked List"""

       ll = DoublyLinkedList()

       ll.addlast(5)

       self.assertEqual(repr(ll), "LinkedList(['5'])")



   def test_removefirst(self):

       """Tests for removing the first node of a Linked List"""

       ll = DoublyLinkedList()

       ll.addfirst(1)

       ll.addfirst(2)

       removed_item = ll.remove_first()

       self.assertEqual(removed_item, 2)

       self.assertEqual(repr(ll), "LinkedList(['1'])")

       ll.remove_first()

       self.assertEqual(repr(ll), "LinkedList([])")

       self.assertIsNone(ll.remove_first())



   def test_removelast(self):

       """Tests removing the last node of a Linked List"""

       ll = DoublyLinkedList()

       ll.addfirst(1)

       ll.addfirst(2)

       removed_item = ll.remove_last()

       self.assertEqual(removed_item, 1)

       self.assertEqual(repr(ll), "LinkedList(['2'])")



       # Test removing from an empty list

       ll.remove_last()

       self.assertEqual(repr(ll), "LinkedList([])")

       self.assertIsNone(ll.remove_last())



   def test_length(self):

       """Tests for the length of the Linked List"""

       ll = DoublyLinkedList()

       self.assertEqual(len(ll), 0)

       ll.addfirst(1)

       self.assertEqual(len(ll), 1)

       ll.addlast(2)

       self.assertEqual(len(ll), 2)

       ll.remove_first()

       self.assertEqual(len(ll), 1)

       ll.remove_last()

       self.assertEqual(len(ll), 0)



   def test_str_and_repr_consistency(self):

       """Test to show consistent behavior of repr and str for the Linked List"""

       ll = DoublyLinkedList([1, 2, 3])

       expected_repr = "LinkedList(['1', '2', '3'])"

       self.assertEqual(repr(ll), expected_repr)

       expected_str = 'Your linked list contains: 1 ~and~ 2 ~and~ 3'

       self.assertEqual(str(ll), expected_str)





if __name__ == '__main__':

   unittest.main()