PYTHON -------------------------------------------------------- class LinkedList
ID: 3913670 • Letter: P
Question
PYTHON
--------------------------------------------------------
class LinkedList:
def __init__(self):
self.__head = None
self.__tail = None
self.__size = 0
# Return the head element in the list
def getFirst(self):
if self.__size == 0:
return None
else:
return self.__head.element
# Return the last element in the list
def getLast(self):
if self.__size == 0:
return None
else:
return self.__tail.element
# Add an element to the beginning of the list
def addFirst(self, e):
newNode = Node(e) # Create a new node
newNode.next = self.__head # link the new node with the head
self.__head = newNode # head points to the new node
self.__size += 1 # Increase list size
if self.__tail == None: # the new node is the only node in list
self.__tail = self.__head
# Add an element to the end of the list
def addLast(self, e):
newNode = Node(e) # Create a new node for e
if self.__tail == None:
self.__head = self.__tail = newNode # The only node in list
else:
self.__tail.next = newNode # Link the new with the last node
self.__tail = self.__tail.next # tail now points to the last node
self.__size += 1 # Increase size
# Same as addLast
def add(self, e):
self.addLast(e)
# Insert a new element at the specified index in this list
# The index of the head element is 0
def insert(self, index, e):
if index == 0:
self.addFirst(e) # Insert first
elif index >= self.__size:
self.addLast(e) # Insert last
else: # Insert in the middle
current = self.__head
for i in range(1, index):
current = current.next
temp = current.next
current.next = Node(e)
(current.next).next = temp
self.__size += 1
# Remove the head node and
# return the object that is contained in the removed node.
def removeFirst(self):
if self.__size == 0:
return None # Nothing to delete
else:
temp = self.__head # Keep the first node temporarily
self.__head = self.__head.next # Move head to point the next node
self.__size -= 1 # Reduce size by 1
if self.__head == None:
self.__tail = None # List becomes empty
return temp.element # Return the deleted element
# Remove the last node and
# return the object that is contained in the removed node
def removeLast(self):
if self.__size == 0:
return None # Nothing to remove
elif self.__size == 1: # Only one element in the list
temp = self.__head
self.__head = self.__tail = None # list becomes empty
self.__size = 0
return temp.element
else:
current = self.__head
for i in range(self.__size - 2):
current = current.next
temp = self.__tail
self.__tail = current
self.__tail.next = None
self.__size -= 1
return temp.element
# Remove the element at the specified position in this list.
# Return the element that was removed from the list.
def removeAt(self, index):
if index < 0 or index >= self.__size:
return None # Out of range
elif index == 0:
return self.removeFirst() # Remove first
elif index == self.__size - 1:
return self.removeLast() # Remove last
else:
previous = self.__head
for i in range(1, index):
previous = previous.next
current = previous.next
previous.next = current.next
self.__size -= 1
return current.element
# Return true if the list is empty
def isEmpty(self):
return self.__size == 0
# Return the size of the list
def getSize(self):
return self.__size
def __str__(self):
result = "["
current = self.__head
for i in range(self.__size):
result += str(current.element)
current = current.next
if current != None:
result += ", " # Separate two elements with a comma
else:
result += "]" # Insert the closing ] in the string
return result
# Clear the list */
def clear(self):
self.__head = self.__tail = None
# Return true if this list contains the element o
def contains(self, e):
print("Implementation left as an exercise")
return True
# Remove the element and return true if the element is in the list
def remove(self, e):
print("Implementation left as an exercise")
return True
# Return the element from this list at the specified index
def get(self, index):
print("Implementation left as an exercise")
return None
# Return the index of the head matching element in this list.
# Return -1 if no match.
def indexOf(self, e):
print("Implementation left as an exercise")
return 0
# Return the index of the last matching element in this list
# Return -1 if no match.
def lastIndexOf(self, e):
print("Implementation left as an exercise")
return 0
# Replace the element at the specified position in this list
# with the specified element. */
def set(self, index, e):
print("Implementation left as an exercise")
return None
# Return elements via indexer
def __getitem__(self, index):
return self.get(index)
# Return an iterator for a linked list
def __iter__(self):
return LinkedListIterator(self.__head)
# The Node class
class Node:
def __init__(self, element):
self.element = element
self.next = None
class LinkedListIterator:
def __init__(self, head):
self.current = head
def __next__(self):
if self.current == None:
raise StopIteration
else:
element = self.current.element
self.current = self.current.next
return element
Explanation / Answer
Please find below the completed code:
I have tested also and its working expected, if u want me to post the test code also please comment i will do it
# please do let me know if u have any concern...
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.