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 node self.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 list def Insert_at_beginning(self, data): # creating a node with a data part and the pointer to the next value i.e . the now head node = 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 list def Insert_at_ending(self, data): if self.head is None: self.head = Node(data) return itr = self.head while itr.next: itr = itr.next itr.next = Node(data) # this function inserts a list of values to the linked list at the end def insert_values(self, value_list): self.head = None for 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 = 0 itr = self.head while itr: count += 1 itr = itr.next return count # the below function is used to insert a value just after an existing value in the list def insert_after_value(self, data_after, data_to_insert): if self.head is None: return if self.head.data == data_after: self.head.next = Node(data_to_insert, self.head.next) return itr = self.head while itr: if itr.data == data_after: itr.next = Node(data_to_insert, itr.next) break itr = 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: return if self.head.data == data: self.head = self.head.next return itr = self.head while itr.next: if itr.next.data == data: itr.next = itr.next.next break itr = itr.next # this function simply orints all the values present inthe list. def display(self): if self.head is None: print('list is empty') return itr = self.head llstr = '' while itr: llstr += str(itr.data) + '-->' itr = itr.next print(llstr) if __name__ == "__main__": ll = LinkedList() ll.insert_values(["banana", "mango", "grapes", "orange"]) ll.display() ll.insert_after_value("mango", "apple") # insert apple after mango ll.display() ll.remove_by_value("orange") # remove orange from linked list ll.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 = data self.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) return self.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: return temp = self.top if self.top is not None: self.top = self.top.next temp.next = None return 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 True return False # this below function is used print out the stacks. def display(self): itr = self.top sstr = ' ' while itr: sstr += str(itr.data) + '-->' itr = itr.next print(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 value self.next = next #pointer to the next value self.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) return self.rear.next = Node(data, None) self.rear.next.prev = self.rear self.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.data self.front = self.front.next if self.front is None: self.rear = None return self.front.prev = None return temp # this code is used to clear the whole queue def 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 True return False # this is used to print queues def display(self): itr = self.front sstr = ' ' while itr: sstr += str(itr.data) + '-->' itr = itr.next print(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()
RELATED TAGS
CONTRIBUTOR
View all Courses