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']

RVS_SOLUTIONS

DS INTERVIEW SITE

Wednesday, August 3, 2022

PYTHON DS BASICS

Insertion in a Linked List

Inserting at the Beginning

Example

Output

Inserting at the End

Example

Output

Inserting in between two Data Nodes

Output

Removing an Item

Example

Output

Python - Stack

PUSH into a Stack

Example

Output

POP from a Stack

Output

About Me

Translate