DATA STRUCTURES QUESTION a) Suppose you have a sentineled, doubly-linked list cl

ID: 3850065 • Letter: D

Question

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 < 0:
raise IndexError
else:
new_node = self.__Node(val)
cur = self.__header.__next
for i in range(index):
cur = cur.__next
new_node.__next = cur
new_node.__prev = cur.__prev
cur.__prev.__next = new_node
cur.__prev = new_node
self.__size += 1

def remove_element_at(self, index):
if index < 0:
raise IndexError
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 < 0:
raise IndexError
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

Explanation / Answer

at third blank:

insert_element_at( get_element_at(j+1), j+2):

at last blank:

insert_element_at(curr, j+1):

In generally timecomplextity for insertion sort is : O ( n2 )

but for this code if we observe

for k in range(1,len(numbers)):
   curr=number.get_element_at(k)
   j=k
   while j>0 and number.get_element_at(j) > curr:

for runs n times

j loop runs n-j times

in each j loop we are trying to find number.get_element_at(j) it takes o(n) times

so total time complexity is O (n x (n-j) x n) nearly O( n3 )

Time Complexity : O( n3 )