Data-Structures || Notes || Sumita Arora || Class 12 || Computer science

Note:- PDF Download link given below of this Blog

-:Data-Structures:-

• The logical or mathematical model of a particular organization of data is called data structure. It is a way of storing, accessing, manipulating data.

• Types of data structure:

Data Structures
|
|-Linear
|   |-Arrays
|   |-Linked List
|   |-Stacks
|   |-Queues
|
|-Non-Linear
    |- Trees
    |- Graphs
    |- Tables
    |- Sets

• Operation on data structure:

Traversing: - Accessing each record exactly once.
Insertion: - Adding a new element to the structure.
Deletion: - Removing element from the structure.
Searching: - Search the element in a structure.
Sorting: - Arrange the elements in ascending and descending order.
Merging: - Joining two data structures of same type.

• List: - An array or list is the collection of elements in ordered way.

• There are two types of arrays:
- One dimensional list (1-D Lists)
- Multi-dimensional list (Nested Lists)

• Traversing 1-D array (List):

L = [10, 20, 30, 40, 50]
for i in L:
    print (i)

Output:

10
20
30
40
50
>>>

• Inserting Element in a list: There are two ways to insert an element in a list.
- If the array is not sorted
- If the array is sorted

• If the array is not sorted: In this case, enter the element at any position using insert() function or add the element in the last of the array using append() function.

Example:

L = [15, 8, 25, 45, 13, 19]
L.insert(3,88) # insert element at the index 3
print(L)

Output:
[15, 8, 25, 88, 45, 13, 19]

• If the array is sorted: In this case, import bisect module and use the functions bisect() and insort(). bisect(): identifies the correct index for the element and returns the index. insort(): Inserts the element in the list in its correct order.

• Deletion of an element from a List: To delete an element from a list we can use remove() or pop() method.

Example:

L= [10, 15, 35, 12, 38, 74, 12]
val=int(input("Enter the element that you want to delete: "))
print ("List Before deletion of element: ", L)
L.remove(val)
print("After deletion the element ", val," the list is: ", L)

Output:

Enter the element that you want to delete: 12
List Before deletion of element: [10, 15, 35, 12, 38, 74, 12]
After deletion the element 12 the list is: [10, 15, 35, 38, 74, 12]
>>>

• Searching in a List: There are two types of searching techniques we can use to search an element in a list. These are:
- Linear Search
-Binary Search

(i) Linear Search: It is a simple searching technique.

Program:

L = eval(input("Enter the elements: "))
n = len(L)
item = eval(input("Enter the element that you want to search: "))
count = 0
for i in range(n):
    if L[i]==item:
        print("Element found at the position :", i+1)
        count += 1
        break
if count == 0:
    print("Element not Found")

Output:

Enter the elements: 5,3,9,6,8,7,1
Enter the element that you want to search: 6
Element found at the position: 4
>>>

(ii) Binary Search:

Binary search can work for only sorted arrays whereas linear search can work for both sorted as well as unsorted arrays.

You can understand binary search method by following program: -

def bisearch (ar, key):
    low = 0
    high = len(ar)-1
    while low <= high :
        mid = int ((low+high)/2)
        if key == ar[mid]:
            return mid
        elif key < ar [mid]:
            high = mid - 1
        else :
            low = mid +1
    else :    # loop else 
        return -999
ar = [12,16,19,21,26,59,86,92,97]
item = int (input("Enter search item : " ))
res = bisearch(ar , item)
if res >= 0:
    print (item , "FOUND at index ", res+1)
else :
    print ("Sorry ! ",item ,"Not FOUND in array")

Output:

Enter search item: 19
19 FOUND at index 2
>>>

Linear Search
- Access of elements sequentially.
- Elements may or may not be in sorted order.
- Takes more time to search an element.
- Easy
- Efficient for small array.

Binary Search
- Access of elements randomly.
- Elements must be in sorted order i.e. ascending or descending order
- Takes less time to search an element.
- Tricky
- Efficient for larger array

• Sorting: To arrange the elements in ascending or descending order. There are many sorting techniques.

Program:

L = eval(input("Enter the elements:"))
n=len(L)
for p in range(0, n-1):
    for i in range(0, n-1):
        if L[i] > L[i+1]:
            L[i], L[i+1] = L[i+1], L[i]
print("The sorted list is : ", L)

Output:

Enter the elements:[5,3,26,4,9]
The sorted list is: [3, 4, 5, 9, 26]
>>>

• Stack: It is a linear data structure. Stack is a list of elements in which an element may be inserted or deleted only at one end, called the TOP of the stack. It follows the principle Last in First out (LIFO).

• There are two basic operations associated with stack: -
- Push: Insert the element in stack
- Pop: Delete the element from stack

• Menu based program for stack:

S= []
from os import system
#menu display
def menu():
    ch = 0
    while(ch<1 or ch>4):
        #print("\n" 100)
        anyvar = system("cls")
        print("\n\n\n\n\n")
        print ("\t\t\t1: PUSH")
        print ("\t\t\t2: POP")
        print ("\t\t\t3: DISPLAY")
        print("\t\t\t4: EXIT")
        ch = int(input("\n\t\tEnter a choise (1- 4):"))
    return ch

def push():
    #code to push an item
    item = int(input("\t\t\tEnter an item to push: "))
    S.append(item)
    print("\t\t\t ITEM", item," PUSHESD IN THE STACK")

def pop():
    #code to pop from stack
    if (S ==  []):
        prínt ("\t\t\t NO ITEM TO POP")
    else:
        item = S.pop()
        print ("\t\t\t ITEM ", item," POPPED FROM THE STACK") 

def display():
    #code to display stack
    if (S== []):
        print ("\t\t\tEMPTY STACK")
    else:
        print ("\t\t\t",)
        for i in S:
            print( i, '', end="")

#code to call all functions

import sys
ch = 0

while(ch != 4):
    ch=menu()
    if(ch == 1):
        push()
    elif(ch == 2):
        pop()
    elif(ch == 3):
        display()
    elif(ch == 4):
        print ("\t\t\t ABORTING PROGRAM.")
        sys.exit()
        anyvar = input("\n\t\t\tPress any key to continue... \n")

• QUEUE: Queue is a linear data structure. Queue is a list of elements in which insertion takes place at one end called REAR and deletion takes place only at the other end, called the FRONT. It follows the principle First In First Out (FIFO).

• There are two basic operations associated with stack:
- Enqueue: Insert the element in queue
- Dequeue : Delete the element from queue.

• Menu based program for queue:

Q = []
from os import system
#menu display
def menu():
    ch = 0
    while(ch<1 or ch>4):
        #print ("\n"*100)
        anyvar = system("cls")
        print ("\n\n\n\n\n")
        print ("\t\t\t1: INSERT")
        print ("\t\t\t2: DELETE")
        print ("\t\t\t3: DISPLAY")
        print ("\t\t\t4: EXIT")
        ch = int(input("\n\t\t\tEnter a choise (1-4): "))
    return ch

def insert():
    #code to insert an item
    item = int(input("\t\t\tEnter an item to insert: "))
    Q.append(item)
    print("\t\t\tITEM", item," INSERTED IN THE QUEUE")

def delete():
    #code to delete from queue
    if (Q == []):
        print ("\t\t\tNO ITEM TO DELETE")
    else:
        item = Q.pop(0)
        print ("\t\t\t ITEM", item," DELETED FROM THE QUEUE")

def display():
    #code to display stack
    if (Q == [] ):
        print ("\t\t EMPTY QUEUE")
    else:
        print ("\t\t\t",)
        for i in Q:
            print (i, '', end = " ")

#code to call all functions
import sys
ch = 0
while(ch != 4):
    ch = menu()
    if(ch == 1):
        insert()
    elif (ch == 2):
        delete()
    elif(ch == 3):
        display()
    elif(ch == 4):
        print("\t\t\tABORTING PROGRAM.")
        sys.exit()
        anyvar = input("\n\t\t\tPress any key to continue... \n")

Some important Questions

Q1. What do you mean by Data Structure?

Answer = Data Structure means organization of data. A data structure has well defined operations or behavior.

Q2. FIFO data structure is?

Answer = QUEUE

Q3. LIFO data structure is?

Answer = STACK

Q4. Can we have nested list?

Answer = Yes

Q5. Name one linear data structure.

Answer = Lists

Q6. Name one non-linear data structure.

Answer = Graphs

Q7. Name the operation for insertion in a stack.

Answer = PUSH

Q8. Name the operation for deletion from a stack.

Answer = POP

Q9. Name the function to find length of a list.

Answer = len( )

Q10. Indexing in list starts from?

Answer = 0

Q11. How is Data Structure different from Data Type?

Answer = Data Structure provides information regarding organization of data whereas Data Type provides information regarding the domain of values and operations that can be perform on data.

Q12. Define Stack and Queue.

Answer =

Stack: - A stack is a linear list also known as LIFO list with the special property that items can be added or removed from only one end called the top.
Queue: - A queue is a linear list also known as FIFO list with the special property that items can be added at one end and removed from the other.

Q13. Name some operations commonly performed on data structures?

Answer = Traversal, Insertion, Deletion, Searching, Sorting, Merging etc.

Q14. What is a list?

Answer = A list is a mutable sequence of data elements indexed by their position. A list is represented using [ ]. E.g. L= [10, 20, 30]

Q15. What is traversing? Write python code to traverse a list.

Answer = Traversing means accessing or visiting or processing each element of any data structure.

L = [10, 20, 30, 40, 50]
for i in L:
print (i)

Q16. Name the methods used for inserting and deleting elements from a list.

Answer = Various methods for inserting elements in a list are - insert(), append(), extend() and methods used for deleting items from a list are – pop() , remove(), clear()

Q17. Write some applications of stack.

Answer = Reversing a string, compilers uses stack to store previous state of program, undo mechanism in text editors and backtracking.

Q18. Write some applications of queue.

Answer = Sharing of resources, CPU uses queue, Airport authorities uses queue for runways and many computer algorithms uses queue.

Q19. Describe similarities between stack and queue.

Answer =

(i)Both are special cases of linear list.
(ii) Both can be implemented as list.

Q20. Describe differences between stack and queue.

Answer =

(i) A Stack is LIFO and Queue is FIFO
(ii) Queue can be circular whereas Stack cannot.

Q21. Write a program to implement a stack for the students(studentno, name). Just implement Push.

Answer = Program for push operation in a stack

  stk = []
top = -1
def PUSH(stk, student):
    stk.append(student)
    top = len(stk) - 1

sno = int(input("Enter student No:"))
sn = input("Enter student Name:")
data = [sno,sn]

PUSH(stk,data)

Q22. Evaluate the following Postfix expression: 4, 10, 5, +, *, 15, 3, /, -

Answer = 55

Q23. What is the difference between pop() and pop(0)?

Answer =

pop() will delete the last element of a list whereas pop(0) will delete element at index zero of a list.

Thankyou!!!!!

For Solution of ‘Sumita Arora’ visit on Path Walla

For ‘Sumita Arora Type C’ solution (Programing Question) Visit our YouTube Channel Portal Express

Path Walla