12:17 PM AT&T; A d list is one where each node has two references: one to the ne

Question

12:17 PM AT&T; A d list is one where each node has two references: one to the next node, and another to the previous node (You would need to modify the Node class accordingly (1 pointl. The DLList class must contain areference to the head element (asisthe case for the singly linked ist) as well as a reference tail, which references the last element in the list. One advantage of having the tail reference is that it makes it more efficient to append elements to the list (there's no need to traverse the list from the beginning0 You are to implement the list methods below (22 pointsl: init. self List constructor. 1 point. def add (self item) parameter an item Inotanodel, which it inserts as the head element The method accepts as a in the list. 1 points def size (self) Returns the size of the list. 1 points. def contains (self item Given an item, the method returns True if the item is in the list, False otherwise. 2 points. def rand init(self list size list is non-empty, delete allelements first. As an example, given that dList is a to a list, the cal dList.rand init(5) would puts randomly generated values in the list. The list size after the function call should be 5. 2 points. def remove all (self item) The method removes al occurrences of item in the list. item is not in the list, the method doesnothing. For instance, if list dList has the elements 4 434 S434, then the callduistremovel4) would change the list to 353 3 points. def (self Returns a string representation of the list luse the Pythonlist format, eg, la, b, cl. 2 points. def append (self, item Append an item to the end of the list (Your method should use the tail reference) 1points def slice self end) Given two values start and end Iwhere start

Explanation / Answer

I have added few methods and test cases please execute :

class Node():
def __init__(self, next_node=None, previous_node=None, data=None):
self.next_node = next_node
self.previous_node = previous_node
self.data = data

class LinkedList():
def __init__(self, node):
assert isinstance(node, Node)
self.first_node = node
self.last_node = node

def add(self, node):
'''Pushes the node <node> at the "front" of the ll
'''
node.next_node = self.first_node
node.previous_node = None
self.first_node.previous_node = node
self.first_node = node

def pop(self):
'''Pops the last node out of the list'''
old_last_node = self.last_node
to_be_last = self.last_node.previous_node
to_be_last.next_node = None
old_last_node.previous_node = None

# Set the last node to the "to_be_last"
self.previous_node = to_be_last

return old_last_node

def remove(self, node):
'''Removes and returns node, and connects the previous and next
nicely
'''
next_node = node.next_node
previous_node = node.previous_node

previous_node.next_node = next_node
next_node.previous_node = previous_node

# Make it "free"
node.next_node = node.previous_node = None

return node
  
def append(self, data):
new_node = Node(data, None, None)
if self.head is None:
self.head = self.tail = new_node
else:
new_node.prev = self.tail
new_node.next = None
self.tail.next = new_node
self.tail = new_node
  
def is_palindrome(l):
head = l
prev = None
while l.next:
l.prev = prev
prev = l
l = l.next
tail = l
tail.prev = prev
while head is not tail and head.data == tail.data:
head = head.next
tail = tail.prev
if head is tail:
return True
elif head.data == tail.data:
return True
else:
return False

def __str__(self):
next_node = self.first_node
s = ""
while next_node:
s += "--({:0>2d})-- ".format(next_node.data)
next_node = next_node.next_node

return s
  
# Function reverse a Doubly Linked List
def reverse(self):
temp = None
current = self.head

# Swap next and prev for all nodes of
# doubly linked list
while current is not None:
temp = current.prev
current.prev = current.next
current.next = temp
current = current.prev

# Before changing head, check for the cases like
# empty list and list with only one node
if temp is not None:
self.head = temp.prev

return

node1 = Node(data=1)

linked_list = LinkedList(node1)

for i in xrange(10):
if i == 5:
node5 = Node(data=5)
linked_list.add(node5)
else:
linked_list.add(Node(data=i))

print linked_list

print "popping"
print linked_list.pop().data

print " "
print linked_list

print " "
linked_list.add(Node(data=10))

print " "
print linked_list

linked_list.remove(node5)

print " "
print linked_list

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.