Data Structures are used to store large amounts of data in an efficient and categorical manner. For example in lists, arrays, tuples, dictionaries, and sets.
We are now gonna look into Linear Data Structures:
A linked list consists of nodes/elements where each element contains a data field and a reference to the next node in the list.
# the node class is used to create an element holder and the respective reference pointers.class Node:def __init__(self, data=None, next=None):self.data = data # the value part of the nodeself.next = next # the pointer part of the node# this is the main class that that is used to create the linked list data struture which contains many functions.class LinkedList:def __init__(self):self.head = None # creating an empty linked list# the below function is used to insert the nodes/element holders at the begining of the listdef Insert_at_beginning(self, data):# creating a node with a data part and the pointer to the next value i.e . the now headnode = Node(data, self.head)self.head = node # now the head points towards the new inserted element pushing the previous element behind# the below function is used to insert the nodes/element holders at the ending of the listdef Insert_at_ending(self, data):if self.head is None:self.head = Node(data)returnitr = self.headwhile itr.next:itr = itr.nextitr.next = Node(data)# this function inserts a list of values to the linked list at the enddef insert_values(self, value_list):self.head = Nonefor value in value_list:self.Insert_at_ending(value)# this function is used to get the length of the linked list.def get_length(self):count = 0itr = self.headwhile itr:count += 1itr = itr.nextreturn count# the below function is used to insert a value just after an existing value in the listdef insert_after_value(self, data_after, data_to_insert):if self.head is None:returnif self.head.data == data_after:self.head.next = Node(data_to_insert, self.head.next)returnitr = self.headwhile itr:if itr.data == data_after:itr.next = Node(data_to_insert, itr.next)breakitr = itr.next# the below function is used to remove a particular value which in present in the list.def remove_by_value(self, data):if self.head is None:returnif self.head.data == data:self.head = self.head.nextreturnitr = self.headwhile itr.next:if itr.next.data == data:itr.next = itr.next.nextbreakitr = itr.next# this function simply orints all the values present inthe list.def display(self):if self.head is None:print('list is empty')returnitr = self.headllstr = ''while itr:llstr += str(itr.data) + '-->'itr = itr.nextprint(llstr)if __name__ == "__main__":ll = LinkedList()ll.insert_values(["banana", "mango", "grapes", "orange"])ll.display()ll.insert_after_value("mango", "apple") # insert apple after mangoll.display()ll.remove_by_value("orange") # remove orange from linked listll.display()ll.remove_by_value("figs")ll.display()ll.remove_by_value("banana")ll.remove_by_value("mango")ll.remove_by_value("apple")ll.remove_by_value("grapes")ll.display()
A stack is a linear data structure that follows a specific order.
The order may be:
Here, you can only retrieve whichever element you enter first at the end and not in between.
There are many ways to implement a stack data structure, but we are gonna do it using a linked list.
# the node class is used to create an element holder and the respective reference pointers.class Node:def __init__(self, data=None, next=None):self.data = dataself.next = next# this is the main class that that is used to create queues data struture which contains many functions.class Stack:# this is automatically class when an instance of the class is called.def __init__(self):self.top = None# the below function is used to append an value on the top of the stack.def push(self, data):if self.top is None:self.top = Node(data, None)returnself.top = Node(data, self.top)# the below function is used to remove an value from the top of the stack.def pop(self):if self.top is None:returntemp = self.topif self.top is not None:self.top = self.top.nexttemp.next = Nonereturn temp.data# the below function returns the value on the top of the stack.def peek(self):return self.top.data# this function simply clears the whole stack.def clearstack(self):self.top = None# the below tells us if the stack is empty.def emptystack(self):if self.top is None:return Truereturn False# this below function is used print out the stacks.def display(self):itr = self.topsstr = ' 'while itr:sstr += str(itr.data) + '-->'itr = itr.nextprint(sstr)if __name__ == "__main__":stack = Stack()stack.push(10)stack.push(20)stack.push(40)stack.peek()stack.display()stack.pop()stack.push(30)stack.display()stack.clearstack()stack.display()
A queue is also a linear structure that follows a specific order.
The order is:
The difference between stacks and queues is how they are removed. In a stack, we remove the item most recently added; in a queue, we remove the item least recently added.
There are many ways to implement a queue data structure, but we are going to do it using a linked list.
# the node class is used to create an element holder and the respective reference pointers.class Node:def __init__(self, data=None, next=None, prev=None):self.data = data #creating a storage for assigning valueself.next = next #pointer to the next valueself.prev = prev #pointer to the already existing previous value.# this is the main class that that is used to create queues data struture which contains many functions.class Queue:# this is automatically class when an instance of the class is called.def __init__(self):self.front = self.rear = None# this below function is used to append a value at the end of the queue which is similar to a late comer joins at the end.def enqueue(self, data):if self.rear is None:self.front = self.rear = Node(data, None)returnself.rear.next = Node(data, None)self.rear.next.prev = self.rearself.rear = self.rear.next# this below function is used remove a value from the start of the queue.def dequeue(self):if self.front is None:raise Exception('empty queue')temp = self.front.dataself.front = self.front.nextif self.front is None:self.rear = Nonereturnself.front.prev = Nonereturn temp# this code is used to clear the whole queuedef clearqueue(self):self.front = self.rear = None# this is used to check idf the queue in empty or not.def emptyqueue(self):if self.front is None:return Truereturn False# this is used to print queuesdef display(self):itr = self.frontsstr = ' 'while itr:sstr += str(itr.data) + '-->'itr = itr.nextprint(sstr)if __name__ == "__main__":queue = Queue()queue.enqueue(10)queue.enqueue(20)queue.enqueue(30)queue.display()queue.dequeue()queue.dequeue()queue.dequeue()queue.display()queue.enqueue(40)queue.enqueue(50)queue.enqueue(60)queue.display()queue.clearqueue()queue.display()