Write a class LinkedList that holds a linked list of values. Your class should be in a source file named linked_list.py, and should support the following operations:
LinkedList(list) - create a LinkedList that initially holds the values in the given Python list
l.to_list() - return a Python list containing the values in this LinkedList
l.len() - return the number of nodes in a LinkedList
l.get(n) - return the value in the nth node, where nodes are numbered from 0. You may assume that 0 <= n < l.len().
l.has(x) - true if the list includes the value x
l.delete(x) - delete the first occurrence (if any) of the value x
l.rotate() - move the last node in the list to the head of the list; does nothing if the list is empty
l.starts_with(m) - true if the elements of the LinkedList m appear at the beginning of l
l.contains(m) - true if the elements of the LinkedList m appear in succession anywhere in l
l.ends_with(m) - true if the elements of the LinkedList m appear in succession at the end of l
Important: You may not use Python lists anywhere, except in the initializer and the to_list() method. Your LinkedList class may not store a Python list in any attribute. Also, generators (which we will study later in Programming 1) are not allowed in this assignment.
You do not need to read any input or write any output; simply submit a file linked_list.py containing the class described above.
Sample usage #1:
>>> l = LinkedList([2, 7, 4, 9, 18, 19, 22])
>>> l.to_list()
[2, 7, 4, 9, 18, 19, 22]
>>> l.len()
7
>>> l.get(3)
9
>>> l.has(17)
False
>>> o = LinkedList([7])
>>> o.to_list()
[7]
>>> o.len()
1
>>> e = LinkedList([])
>>> e.to_list()
[]
>>> e.len()
0
Sample usage #2:
>>> l = LinkedList([2, 7, 6, 4])
>>> l.delete(2)
>>> l.delete(5)
>>> l.delete(4)
>>> l.to_list()
[7, 6]
>>> l.delete(6)
>>> l.delete(7)
>>> l.to_list()
[]
>>> l.delete(8)
>>> l.to_list()
[]
What I have tried:
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self, values):
self.head = None
self.length = 0 # Track the length of the linked list
for value in values:
self.append(value)
def append(self, value):
new_node = Node(value)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
self.length += 1
def to_list(self):
result = []
current = self.head
while current:
result.append(current.value)
current = current.next
return result
def len(self):
return self.length
def get(self, n):
if n < 0 or n >= self.length:
raise IndexError("Index out of range")
current = self.head
for _ in range(n):
current = current.next
return current.value
def has(self, x):
current = self.head
while current:
if current.value == x:
return True
current = current.next
return False
def delete(self, x):
if not self.head:
return
if self.head.value == x:
self.head = self.head.next
self.length -= 1
return
current = self.head
while current.next:
if current.next.value == x:
current.next = current.next.next
self.length -= 1
return
current = current.next
def rotate(self):
if not self.head or not self.head.next:
return
current = self.head
while current.next.next:
current = current.next
current.next.next = self.head
self.head = current.next
current.next = None
def starts_with(self, m):
current_l = self.head
current_m = m.head
while current_l and current_m:
if current_l.value != current_m.value:
return False
current_l = current_l.next
current_m = current_m.next
return not current_m
def contains(self, m):
current_l = self.head
while current_l:
if self.starts_with_helper(current_l, m):
return True
current_l = current_l.next
return False
def starts_with_helper(self, l, m):
current_l = l
current_m = m.head
while current_l and current_m:
if current_l.value != current_m.value:
return False
current_l = current_l.next
current_m = current_m.next
return not current_m
def ends_with(self, m):
current_l = self.head
current_m = m.head
if not current_m:
return True
while current_l.next:
current_l = current_l.next
while current_m.next:
current_m = current_m.next
while current_l and current_m:
if current_l.value != current_m.value:
return False
current_l = current_l.next
current_m = current_m.next
return not current_m