The goal of this exercise is to create a doubly linked list. You have to use the
ID: 3906858 • Letter: T
Question
The goal of this exercise is to create a doubly linked list. You have to use the file d_linked_node.py and the d_linked_list.py .The d_linked_node is ready. You need to complete the d_linked_list.py. Please note that item is the value in the d_linked_node and not the next and previous.
Methods given in the d_linked_list.py file
• search(self, item) – Returns true if the item is inside the list false otherwise
• index(self,item) – Returns the index of the item or -1 if the item is not in the list
Methods to be completed in the d_linked_list.py file
• add(self, item) – Adds a new item to the front of the list
• remove(self,item) – Removes the first element that is equal to item from the list. If that doesn’t exist it changes nothing
• append(self, item) – Adds item to the end of the list
• insert(self, pos, item) – Add item to the given position in the list (i.e if pos is 0 then item goes to the beginning of the list)
• pop1(self) – Removes and returns the last item in the list
• pop(self, pos) – Removes and returns the item in the given position
• search_larger(self, item) – Returns the position of the first item that is larger than item, -1 if there is no item larger
• get_size(self) – Returns the size of the list
• get_item(self, pos) – Returns the item that exists at pos, Raises exception if pos doesn’t exist – pos can be negative which means the position from the end of the list. (- 1 is the last item, -2 the second from last etc.)
• __str__(self) – Returns a string that is the elements of the DLinkedList with spaces in between
Once you have completed the method d_linked_list.py file, you can run the test function in provided in the d_linked_list.py file to determine if the methods have been implemented correctly or not.
outline:
lass d_linked_node:
def __init__(self, initData, initNext, initPrevious):
# constructs a new node and initializes it to contain
# the given object (initData) and links to the given next
# and previous nodes.
self.__data = initData
self.__next = initNext
self.__previous = initPrevious
if (initPrevious != None):
initPrevious.__next = self
if (initNext != None):
initNext.__previous = self
def getData(self):
return self.__data
def getNext(self):
return self.__next
def getPrevious(self):
return self.__previous
def setData(self, newData):
self.__data = newData
def setNext(self, newNext):
self.__next= newNext
def setPrevious(self, newPrevious):
self.__previous= newPrevious
outline:
from d_linked_node import d_linked_node
class d_linked_list:
def __init__(self):
self.__head=None
self.__tail=None
self.__size=0
def search(self, item):
current = self.__head
found = False
while current != None and not found:
if current.getData() == item:
found= True
else:
current = current.getNext()
return found
def index(self, item):
current = self.__head
found = False
index = 0
while current != None and not found:
if current.getData() == item:
found= True
else:
current = current.getNext()
index = index + 1
if not found:
index = -1
return index
def add(self, item):
# TODO:
def remove(self, item):
# TODO:
def append(self, item):
# TODO:
def insert(self, pos, item):
# TODO:
def pop1(self):
# TODO:
def pop(self, pos):
# TODO:
def search_larger(self, item):
# TODO:
def get_size(self):
# TODO:
def get_item(self, pos):
# TODO:
def __str__(self):
# TODO:
def test():
linked_list = d_linked_list()
is_pass = (linked_list.get_size() == 0)
assert is_pass == True, "fail the test"
linked_list.add("World")
linked_list.add("Hello")
is_pass = (str(linked_list) == "Hello World")
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_size() == 2)
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_item(0) == "Hello")
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_item(1) == "World")
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_item(0) == "Hello" and linked_list.get_size() == 2)
assert is_pass == True, "fail the test"
is_pass = (linked_list.pop(1) == "World")
assert is_pass == True, "fail the test"
is_pass = (linked_list.pop1() == "Hello")
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_size() == 0)
assert is_pass == True, "fail the test"
int_list2 = d_linked_list()
for i in range(0, 10):
int_list2.add(i)
int_list2.remove(1)
int_list2.remove(3)
int_list2.remove(2)
int_list2.remove(0)
is_pass = (str(int_list2) == "9 8 7 6 5 4")
assert is_pass == True, "fail the test"
for i in range(11, 13):
int_list2.append(i)
is_pass = (str(int_list2) == "9 8 7 6 5 4 11 12")
assert is_pass == True, "fail the test"
for i in range(21, 23):
int_list2.insert(0,i)
is_pass = (str(int_list2) == "22 21 9 8 7 6 5 4 11 12")
assert is_pass == True, "fail the test"
is_pass = (int_list2.get_size() == 10)
assert is_pass == True, "fail the test"
int_list = d_linked_list()
is_pass = (int_list.get_size() == 0)
assert is_pass == True, "fail the test"
for i in range(0, 1000):
int_list.append(i)
correctOrder = True
is_pass = (int_list.get_size() == 1000)
assert is_pass == True, "fail the test"
for i in range(0, 200):
if int_list.pop1() != 999 - i:
correctOrder = False
is_pass = correctOrder
assert is_pass == True, "fail the test"
is_pass = (int_list.search_larger(200) == 201)
assert is_pass == True, "fail the test"
int_list.insert(7,801)
is_pass = (int_list.search_larger(800) == 7)
assert is_pass == True, "fail the test"
is_pass = (int_list.get_item(-1) == 799)
assert is_pass == True, "fail the test"
is_pass = (int_list.get_item(-4) == 796)
assert is_pass == True, "fail the test"
if is_pass == True:
print ("=========== Congratulations! Your have finished exercise 1! ============")
if __name__ == '__main__':
test()
Explanation / Answer
class d_linked_node:
def __init__(self, initData, initNext, initPrevious):
# constructs a new node and initializes it to contain
# the given object (initData) and links to the given next
# and previous nodes.
self.__data = initData
self.__next = initNext
self.__previous = initPrevious
if (initPrevious != None):
initPrevious.__next = self
if (initNext != None):
initNext.__previous = self
def getData(self):
return self.__data
def getNext(self):
return self.__next
def getPrevious(self):
return self.__previous
def setData(self, newData):
self.__data = newData
def setNext(self, newNext):
self.__next= newNext
def setPrevious(self, newPrevious):
self.__previous= newPrevious
# end of d_linked_node
from d_linked_node import d_linked_node
class d_linked_list:
def __init__(self):
self.__head=None
self.__tail=None
self.__size=0
def search(self, item):
current = self.__head
found = False
while current != None and not found:
if current.getData() == item:
found= True
else:
current = current.getNext()
return found
def index(self, item):
current = self.__head
found = False
index = 0
while current != None and not found:
if current.getData() == item:
found= True
else:
current = current.getNext()
index = index + 1
if not found:
index = -1
return index
def add(self, item):
# adds an item to list at the beginning
temp = d_linked_node(item, self.__head, None)
if self.__head != None:
self.__head.setPrevious(temp)
else:
self.__tail=temp
self.__head = temp
self.__size += 1
def remove(self, item):
# search for the item and remove it
# the method assumes the item exists
current = self.__head
previous=None
found = False
while not found:
if current.getData() == item:
found = True
else:
previous = current
current = current.getNext()
if previous == None:
self.__head = current.getNext()
else:
previous.setNext(current.getNext())
if (current.getNext() != None):
current.getNext().setPrevious(previous)
else:
self.__tail=previous
self.__size -= 1
def append(self, item):
# adds the item to the end of the list
# must traverse the list to the end and add item
temp = d_linked_node(item, None, None)
if (self.__head == None):
self.__head=temp
else:
self.__tail.setNext(temp)
temp.setPrevious(self.__tail)
self.__tail=temp
self.__size +=1
def insert(self, pos, item):
# insert an element in index pos
current = self.__head
temp = d_linked_node(item, None, None)
index = 0
while current != None:
if index == pos:
if(current.getPrevious() != None):
temp.setPrevious(current.getPrevious())
current.getPrevious().setNext(temp)
temp.setNext(current)
current.setPrevious(temp)
self.__size = self.__size + 1
return
else:
self.add(item)
return
index = index + 1
current = current.getNext()
if index == pos:
self.append(item)
self.__size = self.__size + 1
def pop1(self):
# pop the last element from the list
if(self.get_size() == 0):
return None
if(self.get_size() == 1):
element = self.__head.getData()
self.__head = self.__tail = None
self.__size = self.__size - 1
return element
temp = self.__head
while(temp.getNext() != None):
temp = temp.getNext()
element = temp.getData()
temp.getPrevious().setNext(None)
self.__tail = temp.getPrevious()
self.__size = self.__size - 1
return element
def pop(self, pos):
# pop the element at pos
current = self.__head
index = 0
found = False
if pos == 0:
return pop1()
while current != None and not found:
if index == pos:
element = current.getData()
current.getPrevious().setNext(current.getNext())
if current.getNext() != None:
current.getNext().setPrevious(current.getPrevious())
self.__size = self.__size - 1
return element
current = current.getNext()
index = index + 1
return None
def search_larger(self, item):
# search and return the first item larger than the input item
current = self.__head
index = 0
while current != None:
if current.getData() > item:
return index
current = current.getNext()
index = index + 1
return None
def get_size(self):
# return the size of the lined list
return self.__size
def get_item(self, pos):
# get the item at pos
if pos >= 0:
index = 0
current = self.__head
while current != None:
if index == pos:
return current.getData()
current = current.getNext()
index = index + 1
else:
index = -1
current = self.__tail
while current != None:
if index == pos:
return current.getData()
current = current.getPrevious()
index = index - 1
return None
def __str__(self):
# return string representation of linked list
if(self.get_size() == 0):
return "Empty list"
current = self.__head
nodeList = ""
while(current.getNext() != None):
nodeList = nodeList + str(current.getData())+" "
current = current.getNext()
nodeList = nodeList + str(current.getData())
return nodeList
def test():
linked_list = d_linked_list()
is_pass = (linked_list.get_size() == 0)
assert is_pass == True, "fail the test"
linked_list.add("World")
linked_list.add("Hello")
is_pass = (str(linked_list) == "Hello World")
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_size() == 2)
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_item(0) == "Hello")
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_item(1) == "World")
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_item(0) == "Hello" and linked_list.get_size() == 2)
assert is_pass == True, "fail the test"
is_pass = (linked_list.pop(1) == "World")
assert is_pass == True, "fail the test"
is_pass = (linked_list.pop1() == "Hello")
assert is_pass == True, "fail the test"
is_pass = (linked_list.get_size() == 0)
assert is_pass == True, "fail the test"
int_list2 = d_linked_list()
for i in range(0, 10):
int_list2.add(i)
int_list2.remove(1)
int_list2.remove(3)
int_list2.remove(2)
int_list2.remove(0)
is_pass = (str(int_list2) == "9 8 7 6 5 4")
assert is_pass == True, "fail the test"
for i in range(11, 13):
int_list2.append(i)
is_pass = (str(int_list2) == "9 8 7 6 5 4 11 12")
assert is_pass == True, "fail the test"
for i in range(21, 23):
int_list2.insert(0,i)
is_pass = (str(int_list2) == "22 21 9 8 7 6 5 4 11 12")
assert is_pass == True, "fail the test"
is_pass = (int_list2.get_size() == 10)
assert is_pass == True, "fail the test"
int_list = d_linked_list()
is_pass = (int_list.get_size() == 0)
assert is_pass == True, "fail the test"
for i in range(0, 1000):
int_list.append(i)
correctOrder = True
is_pass = (int_list.get_size() == 1000)
assert is_pass == True, "fail the test"
for i in range(0, 200):
if int_list.pop1() != 999 - i:
correctOrder = False
is_pass = correctOrder
assert is_pass == True, "fail the test"
is_pass = (int_list.search_larger(200) == 201)
assert is_pass == True, "fail the test"
int_list.insert(7,801)
is_pass = (int_list.search_larger(800) == 7)
assert is_pass == True, "fail the test"
is_pass = (int_list.get_item(-1) == 799)
assert is_pass == True, "fail the test"
is_pass = (int_list.get_item(-4) == 796)
assert is_pass == True, "fail the test"
if is_pass == True:
print ("=========== Congratulations! Your have finished exercise 1! ============")
if __name__ == '__main__' :
test()
# end of d_linked_list
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.