Notes
A linked list is a linear data structure where each element (node) is a separate object that has two components: the data and a reference to the next node.
Node Class
class node:
def __init__(self, new_data):
self.data = new_data
self.next = None
def __str__(self):
return str(self.data)
def getdata(self):
return self.data
def getnext(self):
return self.next
def setdata(self, new_data):
self.data = new_data
def setnext(self, next_node):
self.next = next_node
Linked List Class
class linked_list:
def __init__(self):
self.head = None
def __str__(self):
result = ""
current = self.head
while(current != None):
result = result + str(current) + ", "
current = current.getnext()
return result[:-2]
def sethead(self, new_head):
self.head = new_head
def getfirst(self): #Get the first element
return self.head.getdata()
def dataat(self, index): #Get data at a specific index
current = self.head
for i in range(index):
if current == None:
break
else:
current = current.getnext()
return current.getdata()
def getlast(self): #Get the last element
current = self.head
previous = None
while current != None:
previous = current
current = current.getnext()
return previous.getdata()
def getsize(self): #Get the number of elements
result = 0
current = self.head
while current != None:
current = current.getnext()
result +=1
return result
def append(self, new_data): #Add an element to the end of the linked list
new_node = node(new_data)
current = self.head
previous = None
while current != None:
previous = current
current = current.getnext()
if previous == None:
self.head = new_node
else:
previous.setnext(new_node)
def prepend(self, new_data): #Add an element to the front of the linked list
new_node = node(new_data)
new_node.setnext(self.head)
self.head = new_node
def insert(self, new_data, index): #Add an element at a specific index
new_node = node(new_data)
if index == 0:
self.prepend(new_data)
elif index == self.getsize() - 1:
self.append(new_data)
else:
current = self.head
previous = None
for i in range(index):
previous = current
current = current.getnext()
previous.setnext(new_node)
new_node.setnext(current)
def clear(self): #Remove all elements
self.head = None
def contain(self, check_data): #Check whether the linked list contains a specific data
current = self.head
while current != None:
if check_data == current.getdata():
return True
else:
current = current.getnext()
return False
def remove(self, remove_data): #Remove the first element that match the given data, return true when returned, return false when item not found
current = self.head
previous = None
while current != None:
if current.getdata() == remove_data:
if previous == None:
self.head = current.getnext()
else:
previous.setnext(current.getnext())
return True
else:
previous = current
current = current.getnext()
return False
def removefirst(self): #Remove the first element, return the removed data when successful, return None when the list was empty
if self.head == None:
return None
else:
temp = self.head
self.sethead(self.head.getnext())
return temp.getdata()
def removelast(self): #Remove the last element, return the removed data when successful, return None when the list was empty
if self.head == None:
return None
else:
current = self.head
previous = None
while current != None:
previous = current
current = current.getnext()
temp = previous
previous.setnext(None)
return temp.getdata()
def removeat(self, index): #Remove an element at a specific index, return the removed data when successful, return None when the list was empty, error occurs when out of range.
if self.head == None:
return None
else:
if index == 0:
self.removefirst()
elif index == self.getsize() - 1:
self.removelast()
else:
current = self.head
previous = None
for i in range(index):
previous = current
current = current.getnext()
previous.setnext(current.getnext())
return current.getdata()