DATA STRUCTURES QUESTION

a) Suppose you have a sentineled, doubly-linked list class and an object of that class called numbers. The code segment below correctly performs an insertion sort on that list, but the list interactions have been removed. Using no spaces at all in your answers, fill in the missing code.

You need a linked list implementation for this which I will post below:

class Linked_List:

class __Node:

def __init__(self, val): self.val = val self.next = None self.prev = None def __init__(self): self.__header = self.__Node(None) self.__trailer = self.__Node(None) self.__header.__next = self.__trailer self.__trailer.__prev = self.__header self.__size = 0 def __len__(self): return self.__size

def append_element(self, val): new_node = Linked_List.__Node(val) if self.__header.__next is self.__trailer: self.__trailer.__prev = new_node new_node.__next = self.__trailer new_node.__prev = self.__header self.__header.__next = new_node else: cur = self.__trailer.__prev self.__trailer.__prev = new_node new_node.__next = self.__trailer cur.__next = new_node new_node.__prev = cur self.__size += 1 def insert_element_at(self, val, index): if index == (self.__size): raise IndexError if index > (self.__size - 1): raise IndexError if index

def remove_element_at(self, index): if index (self.__size - 1): raise IndexError cur = self.__header.__next for i in range(index): cur = cur.__next cur.__prev.__next = cur.__next cur.__next.__prev = cur.__prev self.__size -= 1 return cur.val def get_element_at(self, index): if index (self.__size - 1): raise IndexError cur = self.__header.__next for i in range(index): cur = cur.__next return cur.val def rotate_left(self): if self.__size == 0: return None else: self.__header.__next = self.__trailer self.__trailer.__prev = self.__header

def __str__(self): if self.__size == 0: return("[ ]") else: cur = self.__header.__next printed = "[ " + str(cur.val) while cur.__next is not self.__trailer: cur = cur.__next printed += ", " + str(cur.val) printed += " ]" return(printed) def __iter__(self): self.__iter__index = self.__header.__next return self

def __next__(self): if self.__iter__index == self.__trailer: raise StopIteration bring_back = self.__iter__index.val self.__iter__index = self.__iter__index.__next return bring_back

currently I have: first blank: get_element_at(k)

second blank: get_element_at(j-1)

i am not sure of what to put for the last two blanks.

b) What is the performance of the code segment in question a?

it is not O(n^2)

a) Suppose you have a sentineled, doubly-linked list class and an object of that class called numbers. The code segment below correctly performs an insertion sort on that list, but the list interactions have been removed. Using no spaces at all in your answers, fill in the missing code. for k in range (1 len (numbers) cur numbers while j 0 and numbers cur: try numbers except numbers