Part B: Implement a Sorted Doubly Linked list $(10$ marks$)$

The class declarations have been created in the a$1\_$partb.py starter file. You are responsible to write all the listed functions.

You are allowed to add data members and helper functions to both Node and DoublyLInked classes.

You are not allowed to remove$/$change the interfaces of the listed functions

Only the listed functions will be called directly by the tester, thus any helper functions you add must be called from those listed below

Node

The Node class is declared within SortedList. It stores:

a piece of data

a reference to the next Node in the SortedList $($None if Node is last node$)$

a reference to the previous Node in the SortedList $($None if Node is first node$)$

When a Node is initialized, it is passed a data value. Optionally it is also passed a reference to the next node and a reference to the previous node $($in that order$).$ If the data values are not passed in$,$ they are defaulted to None.

The Node function has the following member functions:

def get$\_$data$($self$)$

function returns data stored in node

def get$\_$next$($self$)$

function returns reference to next node in SortedList

def get$\_$previous$($self$)$

function returns reference to previous node in SortedList

SortedList

A SortedList is a sorted doubly linked list.

A sorted linked list is a linked list where values stay sorted from smallest to biggest with the smallest node at the front of the list and the largest node at the back.

When the SortedList is first created it is empty.

The SortedList has the following member functions

def get$\_$front$($self$)$

This function returns a reference to the first data node in the list. If list is empty, function returns None

def get$\_$back$($self$)$

This function returns a reference to the last data node in the list. If list is empty, function returns None

def is$\_$empty$($self$)$

This function returns True if the list is empty, False otherwise

def $\_\_$len$\_\_($self$)$

This function returns the number of values stored in the list

def insert$($self$,$data$)$

this function inserts data into the list such that the list stays sorted. You may assume that the data being added can be compared using comparison operators. Function returns reference to newly added node.

def erase$($self$,$ node$)$

This function removes the node referred to by the node argument. This function returns nothing. If node is None, function does not alter list and will raise the ValueError with this statement:

raise ValueError$(\text{'}$Cannot erase node referred to by None'$)$

def search$($self$,$ data$)$

This function returns a reference to the node containing data if it exists within the list, None if no node contains data