Question

use python

In class, we've studied Singly-Linked Lists which are made of nodes that point at subsequent nodes. One of the biggest annoyances with Linked Lists is the difficulty of going backwards through a list (such as getting the previous node or traversing the list backwards). An intuitive solution to this inefficiency is the doubly-linked list, which adds pointers to previ- ous nodes. Doubly-Linked Lists are not very different from Singly-Linked Lists, but are far more common because they are easier to use. In this problem, you are to implement a Doubly-Linked List from scratch (you may use the Singly- Linked List code from class). You will have to create 2 classes (Node and Doubly_linked_list). The Node class will have the following methods: init(value, prev, next) • get_prev() • get_next • get_value() • set_prev(node) • set_next(node) • set_value(val) The Doubly_linked_list class must have the following methods: _init_0 • add_to_end(val): adds element as last • add_to_front(val): adds element to first • delete(val): deletes first occurrence of val • reverse(): reverses the list • compare(lst): check if list has the same values in the same order as the DLL • find(val): return the index(as it would be in a list) of the first occurrence of val

Answer 1

Code:

class Node():   #Node class
    def __init__(self, value, prev=None, next=None):    #constructor
        self.value = value;
        self.prev = prev;
        self.next = next;
    def get_prev(self): #returns previous node link
        return self.prev
    def get_next(self): #returns next node link 
        return self.next
    def get_value(self):    #returns value stored in current node
        return self.value
    def set_prev(self, node):   #sets new previous link
        self.prev = node
    def set_next(self, node):   #sets new next node link
        self.next = node
    def set_value(self, val):   #sets new value
        self.value = val

class Doubly_linked_list(): #Double linked list class
    def __init__(self, head = None):    #constructor
        self.head = head
    def add_to_end(self, val):  #appending node at last
        node = Node(val)
        if self.head is None:   #if head node is none then the double linked list is empty so adding node to self.head is enough
            self.head = node
        else:       #in the else condition we have to traverse to the last node and append the node there
            n = self.head   
            while n.get_next() is not None:
                n = n.get_next()
            n.set_next(node)
            node.set_prev(n)
    def add_to_front(self, val):    #adding node in the front
        node = Node(val)
        if self.head is None:   #if head node is none then the double linked list is empty so adding node to self.head is enough
            self.head = node
        else:       #in the else case added node to the front and self.head is updated
            node.set_next(self.head)
            self.head.set_prev(node)
            self.head = node
    def delete(self, val):  #deleting the first occurence of val in double linked list
        n = self.head
        while n is not None:    #traversing through all the nodes of double linked list one by one 
            if val == n.get_value():    #If value matches given value then adjusting the links and breaking the loop to delete that node
                next = n.get_next()
                prev = n.get_prev()
                if next is not None:
                    next.set_prev(prev)
                if prev is not None:
                    prev.set_next(next)
                if n == self.head:
                    self.head = next
                break
            n = n.get_next()
        if n is not None:   #if n is None then the value to be deleted is not found
            del n   #if n is not none then a node with that value is found and is to be deleted
    def reverse(self):  #reverses the double linked list
        n = self.head
        if n is None:   #if self.head is none which means that list is empty so no changes required
            return None
        while n.get_next() is not None:     #traversing to the last node of double linked list
            n = n.get_next()
        self.head = n   #updating the self.head to the last element
        while n is not None:    #traversing double linked list from last node to first node
            prev = n.get_prev() #just by simply swapping prev and next node links of current node we can reverse the double linked list
            next = n.get_next()
            n.set_prev(next)
            n.set_next(prev)
            n = n.get_next()    #as we have swapped the next node is previous node to traverse backwards
    def compare(self, lst): #compares the order of values of a list with double linked list values
        n = self.head
        flag = True #assuming they match 
        for i in lst:   #for each value in given lst
            if i != n.get_value():  #if any value is not matched to one another 
                flag = False    #then flag is turned to false and we break the loop as matching order broke
                break
            n = n.get_next()    
        if n is not None:   #if n is not none even the loop exited which means that their lenghts are not matching 
            flag = False    #so flag is turned to false
        return flag     #flag is the status whether they match or not
    def find(self, val):    #returns index of first occurence of val else returns -1
        n = self.head
        i = 0
        while n is not None:    
            if n.get_value() == val:
                return i
            i += 1
            n = n.get_next()
        return -1   #if not found returning -1
    def print(self):    #prints the values of double linked list onto the screen (extra)
        n = self.head
        if n is None:
            print("No nodes yet")
        while n.get_next() is not None:
            print("[",n.get_value(),"]",end="<->")
            n = n.get_next()
        print("[",n.get_value(),"]")

#testing code
dll = Doubly_linked_list()
dll.add_to_end(9)
dll.add_to_front(3)
dll.add_to_front(5)
dll.print()
print("1st 3 pos:",dll.find(3))
dll.delete(9)
dll.print()
dll.reverse()
dll.print()
print("Comparison with [3,5]:",dll.compare([3,5]))

Code Screenshot:

Output:

I have added print() method to Doubly_linked_list class to print the values to the screen

Each and everything is explained in the comment section of the code.

Thank you! Hit like if you like my work.