A data structure, taken literally is a structure made out of data that isn’t far off from the actual definition, that is a comprehensive way in which data is organized, so it can be read and understood by computers and humans alike. The idea is to make it to be able to reduce the time and space complexity by using certain algorithms on the Data Structures.
Now Data Structures is a vast topic that we can’t hope to cover even in a week worth of blogs, so today we will only cover Sequential Data Structures, i.e. Single Linked List, Doubly Linked List, Queue, and Stack. Without wasting any other time let’s jump into the Data Structure in depth.
Code
Singly Linked List
To visualize the single linked list, remember in your school days when you were made to take “one-hand distance” and leave out the first student all students pointed to the student in front of them. The teacher in turn pointed to the first student.
Now all the students are the nodes pointing to the mode in front of them, the teacher is pointing to the frontmost/head node which lets us know where the line starts from.
Following is the code for the above analogy.
Now Let’s see how to implement Singly Linked List using Python
# defining the container for the element of the linked list
class Node:
def __init__(self, data, next = None):
self.data = data
self.next = next
# defining the Singly Linked List class
class SinglyLinkedList:
def __init__(self, head=None):
self.head = head
self.size = 0
#function to show the length of the LinkedList
def __len__(self):
return self.size
#function to print the LinkedList
def __str__(self):
x = self.head
toprint = []
while x != None:
toprint.append(x.data)
x = x.next
return (‘[‘ +” .join(f’ {i} ‘ for i in toprint) + ‘]’)
#function to clear all the data in the linked list
def clear(self):
x = self.head
if self.size != 0:
while x != None:
next = x.next
x.data = None
x = next
self.size = 0
else:
raise ValueError(“The LinkedList is already empty”)
#function to check if the LinkedList is empty
def emptycheck(self):
return (self.size == 0)
#function to add an element in the beginning
def addBegin(self, data):
node = Node(data)
if self.size == 0:
self.head = node
else:
node.next = self.head
self.head = node
self.size += 1
#function to add an element in a certain position
def addAt(self, data, index):
if index == 0:
self.addBegin(data)
elif index < 0 or index > self.size:
raise IndexError(“Mention a proper valid index”)
else:
node = Node(data)
x = self.head
i = 0
while(i != index):
if (x != None):
x = x.next
i += 1
if x != None:
node.next = x.next
x.next = node
self.size += 1
#function to add an element at the end of the linked list
def addLast(self, data):
x = self.head
node = Node(data)
while x.next != None:
x = x.next
x.next = node
self.size += 1
#function to remove the first element of the list
def removeHead(self):
if self.size == 0 :
raise IndexError(“Linked List is empty”)
else:
self.head = self.head.next
self.size -= 1
#function to remove element at a certain position
def removeAt(self, index):
if index == 0:
self.removeHead()
elif index < 0 or index >= self.size:
raise IndexError(“insert a valid index to remove node”)
else:
temp1 = self.head
temp2 = self.head
i = 0
j = 0
while (i!=index):
temp1 = temp1.next
i += 1
while (j != index-1):
temp2 = temp2.next
j += 1
temp2.next = temp1.next
temp1 = None
self.size -= 1
#function to remove an element from the end of the linked list
def removeLast(self):
if self.size == 0:
raise IndexError(“LinkedList is empty”)
else:
x = self.head
i = 0
while (i != self.size -2):
x = x.next
i += 1
x.next = None
#function to check the first element
def peekHead(self):
return self.head.data
#function to display data at a certain index
def get(self, index):
if index >= self.size:
raise IndexError(“insert a valid index”)
else:
x = self.head
i = 0
while(i != index):
x = x.next
i += 1
return x.data
if __name__ == “__main__”:
sll = SinglyLinkedList()
sll.addBegin(5)
sll.addLast(7)
sll.addLast(9)
print(sll)
sll.addBegin(1)
print(sll)
print(sll.peekHead())
sll.removeHead()
print(sll)
sll.removeLast()
print(sll)
Output:
Now let’s jump to the next data structure which is Doubly Linked List
Doubly Linked List
A doubly linked list is a complex data structure that contains a pointer node to not just the node in front of it but also behind it. That does take double the memory to store the new pointers, but we get much more flexibility in traversing the list. It’s a simple trade-off, python lists are doubly linked lists.
So let’s implement a Doubly Linked List in Python
# defining the container to store the data for the element of the linked list
class Node:
def __init__(self,data,next=None):
self.data = data
self.next = next
#defining doubly linked list
class DoublyLinkedList:
def __init__(self,head=None,tail=None):
self.size = 0
self.head = head
self.tail = tail
#function to check the length of the linked list
def __len__(self):
return self.size
#function to print linked list
def __str__(self):
x = self.head
toprint=[]
while(x!=None):
toprint.append(x.data)
x = x.next
return (‘[‘+”.join(f’ {i} ‘ for i in toprint)+’]’)
#function to clear the LinkedList
def clear(self):
x = self.head
if self.size !=0:
while(x != None):
next = x.next
x.data = None
x = next
self.size = 0
elif self.size ==0:
Exception(“The LinkedList is already cleared”)
#function to check whether the linked list is empty or not
def emptyCheck(self):
if self.size == 0:
return True
return False
#function to add an element at the beginning of the linked list
def addBegin(self, data):
if self.size == 0:
node = Node(data)
self.head = node
self.tail = node
else:
node = Node(data)
node.next = self.head
self.head = node
self.size+=1
#function to add an element at a certain index
def addAfter(self,data,index):
if index == 0:
self.addBegin(data)
elif index<0:
raise IndexError(“Minimum value must be 0 referred to the beginning of the LinkedList”)
else:
node = Node(data)
x = self.head
i = 0
while(i!=index):
if(x!=None):
x = x.next
i+=1
if (x!= None):
node.next = x.next
x.next = node
self.size+=1
#function to remove node at a certain index
def removeNodeAt(self,index):
if index == 0:
self.removeHead()
elif index < 0:
raise Exception(“Please insert valid index”)
elif index == self.size-1:
self.removeTail()
else:
temp1 = self.head
temp2 = self.head
i = 0
j = 0
while(i!=index):
temp1 = temp1.next
i+=1
while(j!= index-1):
temp2 = temp2.next
j+=1
temp2.next = temp1.next
temp1 = None
self.size -= 1
#function to add an element at the end of the linked list
def addLast(self, data):
if self.size == 0:
node = Node(data)
self.head = node
self.tail = node
else:
node = Node(data)
self.tail.next = node
self.tail = self.tail.next
self.size+=1
#function to get the last element
def tailitem(self):
return self.tail.data
#function to get the first element
def headitem(self):
return self.head.data
#function to delete the first element of the linked list
def removeHead(self):
if self.size == 0:
IndexError(“LinkedList is empty!”)
else:
self.head = self.head.next
self.size -= 1
#function to delete the last element of the linked list
def removeTail(self):
if self.size == 0:
raise IndexError(“LinkedList is empty!”)
else:
x = self.head
i = 0
while(i != self.size-2):
x = x.next
i+=1
self.tail = x
x.next = None
self.size -= 1
if __name__ == “__main__”:
dll = DoublyLinkedList()
dll.addBegin(1)
dll.addLast(10)
dll.addLast(20)
print(dll)
dll.addAfter(30, 1)
print(dll)
dll.addBegin(40)
print(dll)
print(dll.headitem())
print(dll.emptyCheck())
dll.removeHead()
print(dll)
Output:
Now let’s move to the next element of our Blog which is Stack
Stack
A stack is a linear data structure that follows a specific order in which the operations are performed. Stacks are ordered through LIFO(Last In First Out) or FILO(First In Last Out). Just imagine a stack of Chapati’s, you eat them one by one picking from the top, to reach the last one will take time as you finish all above it. Here we are just following LIFO as the new chapati placed on top will be eaten first.
Let’s step away from this analogy and go into proper code.
Now as per our schema we will jump to code the stack data structures implementing stack using lists.
# Creating a Stack class
Stack:
def __init__(self, data):
self.data = data
self.top = self.data[0]
# creating push function
def push(self, data):
self.data.insert(0,data)
# creating pop function
def pop(self):
return self.data.pop(0)
# creating a function to check whether the stack is empty
def isEmpty(self):
if self.data ==None:
return True
else:
return False
# creating a function to check the length of the stack
def __len__(self):
return len(self.data)
# creating a function to print the stack
def __str__(self):
return (”.join(‘{}\n’.format(i) for i in self.data))
if __name__ == “__main__”:
stk = Stack([1])
stk.push(2)
stk.push(3)
print(stk.isEmpty())
print(stk)
stk.pop()
print(stk)
Output :
Now let’s move to our last data structure for today which is Queue
Queue
A Queue is also a linear structure that follows a specific order just like the stack but with one key difference. The order is instead First In First Out (FIFO). The simple way to visualize a queue is by just taking the word literally. You take queue at a shop, people who join last will reach the window last, and the people who joined the queue first will be out first. So the key difference is adding and removing. In a stack we remove the item the most recently added, meanwhile in a queue, we remove the item the least recently added.
Now again let’s implement a queue in python
#creating a queue class
class Queue:
def __init__(self, data):
self.data = [data]
# creating an enqueue function
def enqueue(self,data):
self.data.append(data)
# creating a dequeue function
def dequeue(self):
self.data.pop(0)
# creating a function to return the length
def __len__(self):
return len(self.data)
# creating a function to print the queue
def __str__(self):
return (”.join(‘|{}|’.format(i) for i in self.data))
# function to check the head
def head(self):
return self.data[0]
# function to check the last element
def tail(self):
return self.data[-1]
if __name__ == “__main__”:
q = Queue(5)
q.enqueue(10)
q.enqueue(20)
print(q)
print(q.head())
print(q.tail())
q.dequeue()
print(q)
Output :
Conclusion
The OOP syntax of python makes it pretty easy to create Sequential Data Structures.
The harder part is thinking up the logic of these Data Structures.
We can also create advanced Data Structures using Python all that would take is understanding the logic and Classes and Object syntax in python.
