Question

In: Computer Science

Python class DLLNode: """ Class representing a node in the doubly linked list implemented below. """...

Python

class DLLNode:
    """
    Class representing a node in the doubly linked list implemented below.
    """

    def __init__(self, value, next=None, prev=None):
        """
        Constructor
        @attribute value: the value to give this node
        @attribute next: the next node for this node
        @attribute prev: the previous node for this node
        """
        self.__next = next
        self.__prev = prev
        self.__value = value

    def __repr__(self):
        return str(self.__value)

    def __str__(self):
        return str(self.__value)

    def get_value(self):
        """
        Getter for value
        :return: the value of the node
        """
        return self.__value

    def set_value(self, value):
        """
        Setter for value
        :param value: the value to set
        """
        self.__value = value

    def get_next(self):
        """
        Getter for next node
        :return: the next node
        """
        return self.__next

    def set_next(self, node):
        """
        Setter for next node
        :param node: the node to set
        """
        self.__next = node

    def get_previous(self):
        """
        Getter for previous node
        :return: the previous node
        """
        return self.__prev

    def set_previous(self, node):
        """
        Setter for previous node
        :param node: the node to set
        """
        self.__prev = node


class DLL:
    """
    Class representing a doubly linked list.
    """

    def __init__(self):
        """
        Constructor
        @attribute head: the head of the linked list
        @attribute tail: the tail of the linked list
        @attribute size: the size of the linked list
        """
        self.head = None
        self.tail = None
        self.size = 0

    def __repr__(self):
        """
        iterates through the linked list to generate a string representation
        :return: string representation of the linked list
        """
        res = ""
        node = self.head
        while node:
            res += str(node)
            if node.get_next():
                res += " "
            node = node.get_next()
        return res

    def __str__(self):
        """
        iterates through the linked list to generate a string representation
        :return: string representation of the linked list
        """
        res = ""
        node = self.head
        while node:
            res += str(node)
            if node.get_next():
                res += " "
            node = node.get_next()
        return res

    ######### MODIFY BELOW ##########

    def get_size(self):
        """
        Gives the user the size of their linked list
        :return: [int] the size of the linked list
        """
        

    def is_empty(self):
        """
        Determines if the linked list is empty or not
        :return: [boolean] true if DLL is empty, false otherwise
        """
       
    def insert_front(self, value):
        """
        Inserts a value into the front of the list
        :param value: the value to insert
        """
       
    def insert_back(self, value):
        """
        Inserts a value into the back of the list
        :param value: the value to insert
        """
 

    def delete_front(self):
        """
        Deletes the front node of the list
        """

    def delete_back(self):
        """
        Deletes the back node of the list
        """

    def delete_value(self, value):
        """
        Deletes the first instance of the value in the list.
        :param value: The value to remove
        """



    def delete_all(self, value):
        """
        Deletes all instances of the value in the list
        :param value: the value to remove
        """
        pass

    def find_first(self, value):
        """
        Finds the first instance of the value in the list
        :param value: the value to find
        :return: [DLLNode] the first node containing the value
        """
        pass

    def find_last(self, value):
        """
        Finds the last instance of the value in the list
        :param value: the value to find
        :return: [DLLNode] the last node containing the value
        """
        pass

    def find_all(self, value):
        """
        Finds all of the instances of the value in the list
        :param value: the value to find
        :return: [List] a list of the nodes containing the value
        """
        pass

    def count(self, value):
        """
        Finds the count of times that the value occurs in the list
        :param value: the value to count
        :return: [int] the count of nodes that contain the given value
        """
        pass

    def sum(self):
        """
        Finds the sum of all nodes in the list
        :param start: the indicator of the contents of the list
        :return: the sum of all items in the list
        """
        pass


def remove_middle(LL):
    """
    Removes the middle of a given doubly linked list.
    :param DLL: The doubly linked list that must be modified
    :return: The updated linked list
    """
    pass

This is the testcases

import unittest
from DLL import DLL, DLLNode, remove_middle


class TestProject1(unittest.TestCase):

    def test_inserts(self):
        lst = DLL()
        lst.insert_front(1)
        lst.insert_front(2)
        lst.insert_front(3)
        lst.insert_back(4)
        lst.insert_back(5)

        self.assertEqual(lst.head.get_value(), 3)
        self.assertEqual(lst.tail.get_value(), 5)

        forward, backward = [], []
        head = lst.head
        while head is not None:
            forward.append(head.get_value())
            head = head.get_next()
        tail = lst.tail
        while tail is not None:
            backward.append(tail.get_value())
            tail = tail.get_previous()

        self.assertEqual(forward, [3, 2, 1, 4, 5])
        self.assertEqual(backward, [5, 4, 1, 2, 3])

    def test_accessors(self):
        lst = DLL()

        self.assertTrue(lst.is_empty())
        self.assertEqual(lst.get_size(), 0)

        for _ in range(5):
            lst.insert_front(1)

        self.assertTrue(not lst.is_empty())
        self.assertEqual(lst.get_size(), 5)

        for _ in range(3):
            lst.delete_front()

        self.assertTrue(not lst.is_empty())
        self.assertEqual(lst.get_size(), 2)

    def test_deletes(self):
        def condense(linkedlist):
            res = list()
            node = linkedlist.head
            while node is not None:
                res.append(node.get_value())
                node = node.get_next()
            return res

        lst = DLL()
        inserts = [1, 4, 0, 10, 3, 7, 9]

        for x in inserts:
            lst.insert_back(x)

        lst.delete_front()
        inserts.pop(0)

        self.assertEqual(inserts, condense(lst))

        lst.delete_back()
        inserts.pop()

        self.assertEqual(inserts, condense(lst))

    def test_delete_value_all(self):
        def condense(linkedlist):
            res = list()
            node = linkedlist.head
            while node is not None:
                res.append(node.get_value())
                node = node.get_next()
            return res

        lst = DLL()
        insert = [1, 2, 3, 4, 5, 6, 1, 1, 2, 4, 1, 9]

        for i in insert:
            lst.insert_back(i)

        lst.delete_value(1)
        self.assertEqual(condense(lst), insert[1:])

        lst.delete_all(1)
        self.assertEqual(condense(lst), [2, 3, 4, 5, 6, 2, 4, 9])

    def test_finds(self):
        lst = DLL()
        inserts = [9, 16, 5, 58, 32, 1, 4, 58, 67, 2, 4]

        for i in inserts:
            lst.insert_back(i)

        first = lst.find_first(32)

        self.assertEqual(first.get_value(), 32)
        self.assertEqual(first.get_next().get_value(), 1)
        self.assertEqual(first.get_previous().get_value(), 58)

        last = lst.find_last(2)

        self.assertEqual(last.get_value(), 2)
        self.assertEqual(last.get_next().get_value(), 4)
        self.assertEqual(last.get_previous().get_value(), 67)

        list_of_58s = lst.find_all(58)

        self.assertEqual(len(list_of_58s), 2)
        for i in list_of_58s:
            self.assertEqual(i.get_value(), 58)

        first = list_of_58s[0]
        second = list_of_58s[1]

        self.assertEqual(first.get_next().get_value(), 32)
        self.assertEqual(first.get_previous().get_value(), 5)

        self.assertEqual(second.get_next().get_value(), 67)
        self.assertEqual(second.get_previous().get_value(), 4)

    def test_count_sum(self):
        lst = DLL()
        inserts = [1, 3, 1, 4, 5, 6, 1, 3, 8]

        for i in inserts:
            lst.insert_back(i)

        self.assertEqual(lst.count(1), 3)
        self.assertEqual(lst.sum(), 32)

    def test_remove_middle(self):
        def condense(linkedlist):
            res = list()
            node = linkedlist.head
            while node is not None:
                res.append(node.get_value())
                node = node.get_next()
            return res

        lst = DLL()
        inserts = [1, 2, 3, 4, 5]

        for i in inserts:
            lst.insert_back(i)

        new = remove_middle(lst)

        self.assertEqual(condense(new), [1, 2, 4, 5])


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

Thanks a lot!

Solutions

Expert Solution

Code:

class DLLNode:

"""
Class representing a node in the doubly linked list implemented below.
"""

def __init__(self, value, next=None, prev=None):

"""
Constructor
@attribute value: the value to give this node
@attribute next: the next node for this node
@attribute prev: the previous node for this node
"""
self.__next = next
self.__prev = prev
self.__value = value

def __repr__(self):

return str(self.__value)

def __str__(self):

return str(self.__value)

def get_value(self):

"""
Getter for value
:return: the value of the node
"""
return self.__value

def set_value(self, value):

"""
Setter for value
:param value: the value to set
"""
self.__value = value

def get_next(self):

"""
Getter for next node
:return: the next node
"""
return self.__next

def set_next(self, node):

"""
Setter for next node
:param node: the node to set
"""
self.__next = node

def get_previous(self):

"""
Getter for previous node
:return: the previous node
"""
return self.__prev

def set_previous(self, node):

"""
Setter for previous node
:param node: the node to set
"""
self.__prev = node

class DLL:

"""
Class representing a doubly linked list.
"""

def __init__(self):

"""
Constructor
@attribute head: the head of the linked list
@attribute tail: the tail of the linked list
@attribute size: the size of the linked list
"""
self.head = None
self.tail = None
self.size = 0

def __repr__(self):

"""
iterates through the linked list to generate a string representation
:return: string representation of the linked list
"""
res = ""
node = self.head
while node:

res += str(node)
if node.get_next():

res += " "

node = node.get_next()

return res

def __str__(self):

"""
iterates through the linked list to generate a string representation
:return: string representation of the linked list
"""
res = ""
node = self.head
while node:

res += str(node)
if node.get_next():

res += " "

node = node.get_next()

return res

def get_size(self):

#returns the size of linked list

return self.size

def is_empty(self):

#if size is 0 then linked list is empty else no

return True if(self.get_size()==0) else False

def insert_front(self, value):

#If linked list empty then we need to update both head and tail pointers

#else only update head pointer

#increase the size by 1

newNode=DLLNode(value)
if(self.get_size()==0):

self.head=newNode
self.tail=newNode
self.size=1

else:

newNode.set_next(self.head)
self.head.set_previous(newNode)
self.head=newNode
self.size+=1

def insert_back(self, value):

#if list is empty then update both head and tail

#else update only tail

#increase size by 1

newNode=DLLNode(value)

if(self.get_size()==0):

self.head=newNode
self.tail=newNode
self.size=1

else:

newNode.set_previous(self.tail)
self.tail.set_next(newNode)
self.tail=newNode
self.size+=1

def delete_front(self):

#if list is empty then there is nothing to delete

#if only 1 element exist then make head and tail None

#else move the head pointer to head.next

#decrease size by 1

if(self.get_size()==0):

print("Sry! linkedlist is empty. Can't delete the element")

return

if(self.get_size()==1):

self.head=None
self.tail=None
self.size=0

else:

self.head=self.head.get_next();
self.head.set_previous(None)
self.size-=1

def delete_back(self):

#if list is empty then there is nothing to delete

#if only 1 element exist then make head and tail None

#else move tail pointer to tail.previous

#decrement size by 1

if(self.get_size()==0):

print("Sry! linkedlist is empty. Can't delete the element")

return

if(self.get_size()==1):

self.head=None
self.tail=None
self.size=0

else:

self.tail=self.tail.get_previous()
self.tail.set_next(None)
self.size-=1

def delete_value(self, value):

#check if 1st element is value if true then call delete_front() method

#else find the node that contains value

#if value is not present then node will point to None so nothing to delete

#elseif check node is same as tail if so call delete_back() method

#else delete the current node

if(self.get_size()==0): return

if(self.head.get_value()==value):

self.delete_front()

return

node=self.head

while(node):

if(node.get_value()==value):

break

node=node.get_next()

if(node):

if(node.get_next()==None):#value is the last element

self.delete_back()

return

temp=node
node=node.get_previous()
node.set_next(temp.get_next())
temp=temp.get_next()
temp.set_previous(node)
self.size-=1

def delete_all(self, value):

#get the current size of list then call delete_value() method

#now check whether present size is same as previous size or not

#run while loop until size of list is same before calling delete_value() method and after this method

val=self.get_size()
self.delete_value(value)
while(val!=self.get_size()):

val=self.get_size()
self.delete_value(value)

def find_first(self, value):

#Traverse from head pointer and traverse forward until we found the first instance of value

#if nothing found then return None

node=self.head
while(node):

if(node.get_value()==value):

return node

node=node.get_next()

return None

def find_last(self, value):

#traverse from tail pointer in backwards and find 1st instance and return

#if nothing found return None

node=self.tail
while(node):

if(node.get_value()==value):

return node

node=node.get_previous()

return None

def find_all(self, value):

#traverse from head pointer in forward direction

#store the nodes if node.value==value and return the list after all traversals

node=self.head
ans=[]
while(node):

if(node.get_value()==value):

ans.append(node)

node=node.get_next()

return ans

def count(self, value):

#u can simply use return len(find_all(value))

count=0
node=self.head
while(node):

if(node.get_value()==value):

count+=1

node=node.get_next()

return count

def sum(self):

total=0
node=self.head
while(node):

total+=node.get_value()
node=node.get_next()

return total

def remove_middle(LL):

#if size if odd I am removing (n+1)/2th element (1 2 3 4 5 -> 1 2 4 5)

#else n/2th element (1 2 3 4 -> 1 3 4)

if(LL.get_size()==0): return LL

if(LL.get_size()<3):

#if only 1 element then make list empty else remove 1st element

LL.delete_front()

return LL

slow=LL.head
fast=LL.head

while(fast and fast.get_next()):

fast=fast.get_next()
if(fast and fast.get_next()):

fast=fast.get_next()
slow=slow.get_next()

fast=slow.get_previous()
slow=slow.get_next()
fast.set_next(slow)
slow.set_previous(fast)
LL.size-=1
return LL

The output of the file after runnig testProject1 file is:

.......
----------------------------------------------------------------------
Ran 7 tests in 0.002s

OK

If you have any queries feel free to ask. Thank you

venereology answered 9 months ago
Next > < Previous

Related Solutions

Assume that a singly linked list is implemented with a header node, but no tail node,...
Assume that a singly linked list is implemented with a header node, but no tail node, and that it maintains only a pointer to the header node. Write a class in C++ that includes methods to a. return the size of the linked list b. print the linked list c. test if a value x is contained in the linked list d. add a value x if it is not already contained in the linked list e. remove a value...
Assume that a singly linked list is implemented with a header node, but no tail node,...
Assume that a singly linked list is implemented with a header node, but no tail node, and that it maintains only a pointer to the header node. Write a class that includes methods to a. return the size of the linked list b. print the linked list c. test if a value x is contained in the linked list d. add a value x if it is not already contained in the linked list e. remove a value x if...
This is the code what I have for doubly linked list for STACK. This is Python...
This is the code what I have for doubly linked list for STACK. This is Python language and I want anyone to help me with the following questions. Can you check for me if it is good Doubly Linked List? ####THIS IS THE ENTIRE ASSIGNMENT#### ADD the Following feature: Include a class attribute in the container class called name. In the implementation - Pod: You should ask the user to enter the name of the container and the program should...
I've provided a Node class that implements a node of a simple singly-linked list (with .value...
I've provided a Node class that implements a node of a simple singly-linked list (with .value and .next fields), and an empty LinkedList class. Your task is to implement LinkedList.sort(l), where given the node l as the head of a singly-linked list, LinkedList.sort(l) sorts the nodes in the list into ascending order according to the values in the .value field of each node. Your implementation should do an in-place update of the list. It is ok to use a simple...
Python 3 Function which takes the head Node of a linked list and sorts the list...
Python 3 Function which takes the head Node of a linked list and sorts the list into non-descending order. PARAM: head_node The head of the linked list RETURNS: The node at the head of the sorted linked list. ''' def sort(head_node): #Code goes here ''' Test code goes here '' ' if __name__ == '__main__':
Write in C++: create a Doubly Linked List class that holds a struct with an integer...
Write in C++: create a Doubly Linked List class that holds a struct with an integer and a string. It must have append, insert, remove, find, and clear.
TITLE Updating Accounts Using Doubly Linked List TOPICS Doubly Linked List DESCRIPTION General Write a program...
TITLE Updating Accounts Using Doubly Linked List TOPICS Doubly Linked List DESCRIPTION General Write a program that will update bank accounts stored in a master file using updates from a transaction file. The program will maintain accounts using a doubly linked list. The input data will consist of two text files: a master file and a transaction file. See data in Test section below.  The master file will contain only the current account data. For each account, it will contain account...
Develop a C++ "doubly" linked list class of your own that can hold a series of...
Develop a C++ "doubly" linked list class of your own that can hold a series of signed shorts Develop the following functionality: Develop a linked list node struct/class You can use it as a subclass like in the book (Class contained inside a class) You can use it as its own separate class Your choice Maintain a private pointer to a node class pointer (head) Constructor Initialize head pointer to null Destructor Make sure to properly delete every node in...
Using doubly linked list in c++ with class constructor: DNode(){    song = Song();    prev...
Using doubly linked list in c++ with class constructor: DNode(){    song = Song();    prev = NULL;    next = NULL; } DNode(string s, string a, int lenmin, int lensec){    song = Song(s,a,lenmin,lensec);    prev = NULL;    next = NULL; } for each node. Write the method: void moveUp(string t); This method moves a song up one in the playlist. For instance, if you had the following: Punching in a Dream, The Naked And Famous................3:58 Harder To...
//LinkNode is a class for storing a single node of a linked list storing integer values....
//LinkNode is a class for storing a single node of a linked list storing integer values. It has two public data fields for the data and the link to //the next node in the list and has three constructors: public class LinkNode { public int data;       public LinkNode next; // post: constructs a node with data 0 and null link public ListNode() {      this(0, null); } // post: constructs a node with given data and null link public LinkNode (int...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT