PYTHON DS
General Data Structures
The various data structures in computer science are divided
broadly into two categories shown below. We will discuss about each of the
below data structures in detail in subsequent chapters.
Liner Data Structures
These are the data structures which store the data elements in a
sequential manner.
·
Array − It is a sequential arrangement of data
elements paired with the index of the data element.
·
Linked
List − Each data
element contains a link to another element along with the data present in it.
·
Stack − It is a data structure which follows
only to specific order of operation. LIFO(last in First Out) or FILO(First in
Last Out).
·
Queue − It is similar to Stack but the order of
operation is only FIFO(First In First Out).
·
Matrix − It is two dimensional data structure in
which the data element is referred by a pair of indices.
Non-Liner Data Structures
These are the data structures in which there is no sequential
linking of data elements. Any pair or group of data elements can be linked to
each other and can be accessed without a strict sequence.
·
Binary
Tree − It is a data
structure where each data element can be connected to maximum two other data
elements and it starts with a root node.
·
Heap − It is a special case of Tree data
structure where the data in the parent node is either strictly greater than/
equal to the child nodes or strictly less than it’s child nodes.
·
Hash
Table − It is a data
structure which is made of arrays associated with each other using a hash
function. It retrieves values using keys rather than index from a data element.
·
Graph − It is an arrangement of vertices and
nodes where some of the nodes are connected to each other through links.
Python Specific Data Structures
These data structures are specific to python language and they
give greater flexibility in storing different types of data and faster
processing in python environment.
·
List − It is similar to array with the
exception that the data elements can be of different data types. You can have
both numeric and string data in a python list.
·
Tuple − Tuples are similar to lists but they are
immutable which means the values in a tuple cannot be modified they can only be
read.
·
Dictionary − The dictionary contains Key-value pairs
as its data elements.
A linked list is a sequence of data elements, which are connected
together via links. Each data element contains a connection to another data
element in form of a pointer. Python does not have linked lists in its standard
library. We implement the concept of linked lists using the concept of nodes as
discussed in the previous chapter.
We have already seen how we create a node class and how to
traverse the elements of a node.In this chapter we are going to study the types
of linked lists known as singly linked lists. In this type of data structure
there is only one link between any two data elements. We create such a list and
create additional methods to insert, update and remove elements from the list.
Creation of Linked list
We create a Node object and create another class to use this ode
object. We pass the appropriate values through the node object to point the to
the next data elements. The below program creates the linked list with three
data elements. In the next section we will see how to traverse the linked list.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
Traversing a Linked List
Singly linked lists can be traversed in only forward direction
starting form the first data element. We simply print the value of the next
data element by assigning the pointer of the next node to the current data
element.
Example
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
list.listprint()
Output
When the above code is executed, it produces the following result
−
Mon
Tue
Wed
Insertion in a Linked List
Inserting element in the linked list involves reassigning the
pointers from the existing nodes to the newly inserted node. Depending on
whether the new data element is getting inserted at the beginning or at the
middle or at the end of the linked list, we have the below scenarios.
Inserting at the Beginning
This involves pointing the next pointer of the new data node to
the current head of the linked list. So the current head of the linked list
becomes the second data element and the new node becomes the head of the linked
list.
Example
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
def AtBegining(self,newdata):
NewNode = Node(newdata)
# Update the new nodes next val to existing node
NewNode.nextval = self.headval
self.headval = NewNode
list = SLinkedList()
list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")
list.headval.nextval = e2
e2.nextval = e3
list.AtBegining("Sun")list.listprint()
Output
When the above code is executed, it produces the following result
−
Sun
Mon
Tue
Wed
Inserting at the End
This involves pointing the next pointer of the the current last
node of the linked list to the new data node. So the current last node of the
linked list becomes the second last data node and the new node becomes the last
node of the linked list.
Example
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Function to add newnode
def AtEnd(self, newdata):
NewNode = Node(newdata)
if self.headval is None:
self.headval = NewNode
return
laste = self.headval
while(laste.nextval):
laste = laste.nextval
laste.nextval=NewNode
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")
list.headval.nextval = e2
e2.nextval = e3
list.AtEnd("Thu")
list.listprint()
Output
When the above code is executed, it produces the following result
−
Mon
Tue
Wed
Thu
Inserting in between two
Data Nodes
This involves changing the pointer of a specific node to point to
the new node. That is possible by passing in both the new node and the existing
node after which the new node will be inserted. So we define an additional
class which will change the next pointer of the new node to the next pointer of
middle node. Then assign the new node to next pointer of the middle node.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
# Function to add node
def Inbetween(self,middle_node,newdata):
if middle_node is None:
print("The mentioned node is absent") return
NewNode = Node(newdata)
NewNode.nextval = middle_node.nextval
middle_node.nextval = NewNode
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Thu")
list.headval.nextval = e2
e2.nextval = e3
list.Inbetween(list.headval.nextval,"Fri")
list.listprint()
Output
When the above code is executed, it produces the following result
−
Mon
Tue
Fri
Thu
Removing an Item
We can remove an existing node using the key for that node. In the
below program we locate the previous node of the node which is to be
deleted.Then, point the next pointer of this node to the next node of the node
to be deleted.
Example
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class SLinkedList:
def __init__(self):
self.head = None
def Atbegining(self, data_in):
NewNode = Node(data_in)
NewNode.next = self.head
self.head = NewNode
# Function to remove node
def RemoveNode(self, Removekey):
HeadVal = self.head
if (HeadVal is not None):
if (HeadVal.data == Removekey):
self.head = HeadVal.next
HeadVal = None
return
while (HeadVal is not None):
if HeadVal.data == Removekey:
break
prev = HeadVal
HeadVal = HeadVal.next
if (HeadVal == None):
return
prev.next = HeadVal.next
HeadVal = None
def LListprint(self):
printval = self.head
while (printval):
print(printval.data),
printval = printval.next
llist = SLinkedList()
llist.Atbegining("Mon")llist.Atbegining("Tue")llist.Atbegining("Wed")llist.Atbegining("Thu")llist.RemoveNode("Tue")llist.LListprint()
Output
When the above code is executed, it produces the following result
−
Thu
Wed
Mon
LINKED LIST (OWN SIMPLE EXAMPLE)
class Node:
def __init__(self,data=None):
self.data=data
self.next=None
class LinkList:
def __init__(self):
self.head=None
def printnodes(self):
curr=self.head
while curr!=None:
print(curr.data,' ')
curr=curr.next
def
insertbeg(self,node):
node.next=self.head
self.head=node
def insertend(self,node):
prev=self.head
curr=self.head
while curr!=None:
prev=curr
curr=curr.next
prev.next=node
l=LinkList()
first=Node("mon")
l.head=first
n1=Node("tue")
first.next=n1
n2=Node("wed")
n1.next=n2
l.printnodes()
print("-----")
l.insertbeg(Node("Sun"))
l.printnodes()
print("-----")
l.insertend(Node("Over"))
l.printnodes()
output
mon
tue
wed
-----
Sun
mon
tue
wed
-----
Sun
mon
tue
wed
Over
Python - Stack
In the english dictionary the word stack means arranging objects
on over another. It is the same way memory is allocated in this data structure.
It stores the data elements in a similar fashion as a bunch of plates are
stored one above another in the kitchen. So stack data strcuture allows
operations at one end wich can be called top of the stack.We can add elements
or remove elements only form this en dof the stack.
In a stack the element insreted last in sequence will come out
first as we can remove only from the top of the stack. Such feature is known as
Last in First Out(LIFO) feature. The operations of adding and removing the
elements is known as PUSH and POP. In the following program we implement
it as add and and remove functions. We declare an empty list
and use the append() and pop() methods to add and remove the data elements.
PUSH into a
Stack
Let us understand, how to use PUSH in Stack. Refer the program
mentioned program below −
Example
class Stack:
def __init__(self):
self.stack = []
def add(self, dataval):
# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False
# Use peek to look at the top of the stack
def peek(self):
return self.stack[-1]
AStack = Stack()
AStack.add("Mon")AStack.add("Tue")AStack.peek()
print(AStack.peek())
AStack.add("Wed")AStack.add("Thu")print(AStack.peek())
Output
When the above code is executed, it produces the following result
−
Tue
Thu
POP from a
Stack
As we know we can remove only the top most data element from the
stack, we implement a python program which does that. The remove function in
the following program returns the top most element. we check the top element by
calculating the size of the stack first and then use the in-built pop() method
to find out the top most element.
class Stack:
def __init__(self):
self.stack = []
def add(self, dataval):
# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False
# Use list pop method to remove element
def remove(self):
if len(self.stack) <= 0:
return ("No element in the Stack") else:
return self.stack.pop()
AStack = Stack()
AStack.add("Mon")AStack.add("Tue")AStack.add("Wed")AStack.add("Thu")print(AStack.remove())
print(AStack.remove())
Output
When the above code is executed, it produces the following result
−
Thu
Wed
STACK PUSH,POP Example
class Stack:
def __init__(self):
self.stack = []
def add(self, dataval):
# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False
# Use peek to look at the top of the stack
def peek(self):
return self.stack[-1]
def printall(self):
print(self.stack)
def remove(self):
if len(self.stack)<=0:
print("Stack is emp[ty") else:
return self.stack.pop()
AStack = Stack()
AStack.add("Mon")AStack.add("Tue")AStack.add('Mon')AStack.add("Wed")AStack.add("Thu")AStack.add('Fri')AStack.printall()
print(AStack.peek())
AStack.remove()
AStack.printall()
Output:
['Mon', 'Tue', 'Wed', 'Thu', 'Fri']
Fri
['Mon', 'Tue', 'Wed', 'Thu']
QUEUE :
class Queue:
def __init__(self):
self.queue = []
def add(self, dataval):
# Use list append method to add element
if dataval not in self.queue:
self.queue.append(dataval)
return True
else:
return False
# Use peek to look at the top of the queue
def peek(self):
return self.queue[-1]
def printall(self):
print(self.queue)
def remove(self):
if len(self.queue)<=0:
print("queue is emp[ty")
else:
return self.queue.pop(0)
def addbeg(self,wd):
self.queue.insert(0, wd)
Queue = Queue()
Queue.add("Mon")
Queue.add("Tue")
Queue.add('Mon')
Queue.add("Wed")
Queue.add("Thu")
Queue.add('Fri')
Queue.addbeg('Sunday')
Queue.printall()
print(Queue.peek())
Queue.remove()
Queue.printall()
Output:
['Sunday', 'Mon', 'Tue', 'Wed', 'Thu', 'Fri']
Fri
['Mon', 'Tue', 'Wed', 'Thu', 'Fri']
