Deleting from Linked Lists
Let's delete an item from a linked list.
The video will introduce this visual concept:
Let's set up a Linked List and see if we can search from and delete an item from it.
First let's set up the Node class:
class Node:
def __init__(self,prev,next,item):
self.prev = prev
self.next = next
= item
Now let's define the Linked List class which is constructed with a neat array of Nodes:
class LinkedList:
def __init__(self,prev,next,item):
self.nodes = []
for i in range(10):
self.nodes[i] = Node(i-1, i+1, None)
overwrite the final Node to ensure the next pointer is -1 ie the end of the list
self.nodes[] = Node(8,-1,None)
def getNodes(self):
return
def displayNodeData(self):
for i in range(len(self.nodes)):
print(f"Node:{i}, Prev:{self.nodes[i].prev}, Next:{self.nodes[i].next}, Item:{self.nodes[i].item}")
Now let's set up some pointers. These should be initialised in the constructor:
class LinkedList:
def __init__(self,prev,next,item):
self.rootPointer = 0
#do we need a free pointer for this delete operation?
#rest of constructor code, see above
Now let's define a delete method for an ordered linked list. We will first determine if the list is empty, and if not we will search for the item to delete.
def delete(self, item):
if self.rootPointer == None:
print("List empty!")
else:
searchPointer = rootPointer
while self.nodes[searchPointer].item != item and self.nodes[searchPointer].next != -1:
prevPointer =
= self.nodes[searchPointer].next
if searchPointer == -1 and self.node[searchPointer].item != item:
print("Item not in list")
else:
self.nodes[].next = self.nodes[].next
Now let's write a program and test our design:
L = LinkedList()
L.displayNodeData()
L.delete(6)
L.displayNodeData()
L.delete(13)
L.displayNodeData()
Can this work? Is the logic correct? Code it and test it. Perform any corrective maintenance necessary.
Does the code work if you try to delete the last node in the list? Why/Why not?