A doubly linked list is one where each node has two references: one to the next

Question

A doubly linked 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). The DList class must contain a reference to the head element (as is the case for the singly linked list) as well as a reference tall, 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 beginning) You are to implement the list methods below _int_(self): list constructor. 1 point. def add(self, item): The method accepts as a parameter an item (not a node), which it inserts as the head element as the def size (self): Returns the we 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): Fill the lilt with list_size number of randomly generated integers in the range 1-100(inclusive), if the list is non-empty, delete ail elements first. As an example, given that dList is a reference to a list the cat dList. rand_init (5) would put S randomly generated values in the list. The list we after the function call should be 5. def remove_all(self, item): The method removes all occurrences of item in the list. If item is not in the list, the method does nothing for instance, if a list dList has the elements 4 4 3 4 5 4 3 4, then the call dList removed) would change the list to 3 5 3 3 points def _str_(self): Returns a string representation of the list (use the Python list format, e g. (a, b, c) def append(self, item): Append an item to the end of the list (Your method should use the tail reference) def slice(self, start, and): Given two values start and end (where start list size 3 point def swap (self, i, j) Given i and j, swap the list values at those positions. If either position is not valid, do nothing. As an example, if a list dList has the elements 1 2 3 4 5 6 7, then the call dList, swap, (0, 3) would rearrange the list to 4 2 3 1 5 6 7 2 points def shuffle(self): Shuffle the contents of the list def iw_ palindrome(self): Returns True if the elements in the list form a palindrome, false otherwise 2 points Additionally, write a test program that demonstrates that the functions work correctly Make sure you test each function using valid and invalid inputs. For example, to test remove_all, the following tests would be necessary: Remove element from an empty list Remove element that occurs multiple times in the fast Remove an element that's not in the list Remove an element that occurs as the first element in the list Remove an element that occurs as the last element in the list

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 A
• Subjects

---

---

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