Stack,queue and linked list data structure.pptx

Presentation gives brief overview of various operations on data structures

1. Stack data structure

2. Stack Linear data structure based on the LIFO principle To get to the bottom item, we must first remove all the items above it Elements can be added and removed only at one end(top of the stack) Top item is always the first item to enter as well as leave the stack Can be implemented using array and linked list

3. 3 Operations on Stacks push - place an item on the stack- function push(x) Check whether stack is full i.e. overflow – function Boolean isFull() pop - remove an item from the stack- function pop() Check whether stack is empty i.e. underflow – function Boolean isEmpty () peek - Look at the item on top of the stack, but does not remove it. function peek()

4. Implementing stack using array

5. Algorithm for push and pop Push operation Step 1 − Check if the stack is full. Step 2 − If the stack is full, then display “overflow” and exit. Step 3 − If the stack is not full, increment the top to point next empty space. Step 4 − Add data element to the stack location, where top is pointing. Step 5 − Return success. Pop operation Step 1 − Check if the stack is empty. Step 2 − If the stack is empty , then display “underflow” and exit. Step 3 − If the stack is not empty, access the data element at which top is pointing. Step 4 − Decrease the value of top by 1. Step 5 − Return success.

6. Push operation Overflow condition(if top=max-1) Push(element) Step 1:If top==max-1 then print overflow end of if Step 2: Set top=top+1 Step 3: Set stack[top]=element Step 4:end

7. Pop operation Underflow condition(if top=null) Pop() Step 1:If top==null or -1 then print underflow end of if Step 2:set val =stack[top] Step 3:set top=top-1 Return val Step 4:end

8. Peek operation Must check whether the stack is empty or contains some elements. Step 1:If top ==null then print stack is empty go to step 3 Step 2:return stack[top] Step 3:end

9. C code to implement Stack(Menu driven program) Step 1 -  Include all the  header files  which are used in the program and define a constant  'SIZE'   (size of input) with specific value. Step 2 -  Declare all the  functions  used in stack implementation. Step 3 -  Create a one dimensional array with fixed size ( int stack[SIZE] ) Step 4 -  Define an integer variable  'top'  and initialize with  '-1' . ( int top = -1 ) Step 5 -  In main method, display menu with list of operations and make suitable function calls to perform operation selected by the user on the stack.

10. Steps 1-4: # include< stdio.h > # define SIZE 10 void push( int x); void pop (); void peek(); void display(); int stack[SIZE], top = -1; Step 5: void main() { int value, choice; while(1){ printf (“\n1 . Push\n2. Pop\n3.Peek\4. Display\n5. Exit"); printf ("\ nEnter your choice: "); scanf ("% d",&choice ); switch(choice){ case 1: printf ("Enter the value to insert : "); scanf ("% d",&value ); push(value) ; break; case 2: pop(); break; case 3: peek(); break; case 4: display(); break ; case 5: exit(0); default: printf ("\ nWrong selection!!! Try again!!!"); } } }

11. Push function Push operation Step 1 − Checks if the stack is full. Step 2 − If the stack is full, then display “overflow” and exit. Step 3 − If the stack is not full, increment top to point next empty space. Step 4 − Add data element to the stack location, where top is pointing. Step 5 − Returns success. void push( int value ) { if(top == SIZE-1) printf ("\ nStack overflow"); else{ top++; stack[top] = value; printf ("\ nInsertion success!!!"); } }

12. Pop function Pop operation Step 1 − Checks if the stack is empty. Step 2 − If the stack is empty, then display “underflow” and exit. Step 3 − If the stack is not empty, access the data element at which top is pointing. Step 4 − Decrease the value of top by 1. Step 5 − Returns success. void pop () { if(top == -1) printf ("\ nStack underflow!!! "); else { printf ("\ nDeleted : %d", stack[top ] ); top--; } }

13. Peek/displaying top element Step 1 -  Check whether  stack  is  EMPTY . ( top == -1 ) Step 2 -  If it is  EMPTY , then display  "Stack is EMPTY!!!"  and terminate the function. Step 3 -  If it is  NOT EMPTY , then display top element of the stack. Step 4 -  Return success void peek() { if(top == -1) printf ("\ nStack is Empty!!!"); else{ printf ("%d\ n", stack [top] ); } }

14. displaying all the elements Step 1 -  Check whether  stack  is  EMPTY . ( top == -1 ) Step 2 -  If it is  EMPTY , then display  "Stack is EMPTY!!!"  and terminate the function. Step 3 -  If it is  NOT EMPTY , then define a variable ' i ' and initialize with top. Display  stack[ i ]  value and decrement  i  value by one ( i -- ). Step 3 -  Repeat above step until  i  value becomes '0'. void display(){ if(top == -1) printf ("\ nStack is Empty!!!"); else{ int i ; printf ("\ nStack elements are:\n"); for( i =top; i >=0; i --) printf ("%d\ n", stack [ i ] ); } }

15. Application of Stack

16. 16 Applications of Stack Reversing a string Implementing parenthesis checker Evaluation of Arithmetic notations Polish notations Infix to postfix conversion Evaluation of a postfix expression infix to prefix conversion Evaluation of a prefix expression Recursion Tower of Hanoi

17. Reversing a string The idea is to create an empty stack and push all characters of the string into it. Then pop each character one by one from the stack and put them back to the input string starting from the 0'th index . Steps of Algorithm: Create an empty stack. One by one push all characters of string to stack(array). One by one pop all characters from stack and put them back to string.

18. Reversing a string # include < stdio.h > #include < string.h > # define SIZE 100 int top=-1; Int stack[SIZE]; void push(char x){ if(top == SIZE-1 ){ printf ("stack overflow"); } else { top=top+1 stack[top ]=x; } } void pop(){ printf (“The character popped is % c ", stack [top]); top=top-1 } void main() { char str []="Krishna"; int len = strlen ( str ); int i ; for( i =0;i< len;i ++) push( str [ i ]); for( i =0;i< len;i ++) pop(); }

19. Application: Parenthesis matching Algorithmic steps: Initialize an empty stack. Set top pointer of stack to -1. Initialize the input expression as character array. Find length of input string and store it in an integer variable "length". Using a for loop, traverse input string from index 0 to length-1 . Ignore everything you find other than the opening and the closing parenthesis If the current character is a starting/opening bracket ( ‘(‘ or ‘{‘ or ‘[‘ ) then push it to stack. Case 1: If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ) then pop from stack and if the popped character is the matching starting bracket then fine else print “parenthesis mismatch”. Case 2: If stack is empty, then print “Expression is NOT BALANCED”, it means that the right parenthesis are more than left parenthesis Case 3:After complete traversal, if there is some starting bracket left in stack it means left parenthesis are more than right parenthesis then “Expression is NOT BALANCED”

20. Parenthesis matching

21. C program to check for balanced parenthesis int check(char exp [] ) { int i ; char temp; for( i =0;i< strlen ( exp ); i ++) { if( exp [ i ]=='(' || exp [ i ]=='{' || exp [ i ]=='[') push( exp [ i ]); //pushing the element if( exp [ i ]==')' || exp [ i ]=='}' || exp [ i ]==']') if(top==-1) /*stack empty */ { printf ("Right parentheses are more than left parentheses\n"); return 0 ; } else { temp=pop(); if(!match(temp, exp [ i ])) { printf ("Mismatched parentheses are : "); printf ("%c and %c\n", temp,exp [ i ]); return 0; } } } if(top==-1) /*stack empty */ { printf ("Balanced Parentheses\n"); return 1 ; } else { printf ("Left parentheses more than right arentheses \n "); return 0 ; } } #include< stdio.h > #include< string.h > #include< stdlib.h > #define MAX 30 int top=-1; int stack[MAX]; void push(char); char pop(); int match(char a , char b); int check(char []); int main() { char exp [MAX]; int valid; printf ("Enter an algebraic expression : "); scanf ("%s", exp ); valid=check( exp ); if(valid==1) printf ("Valid expression\n"); else printf ("Invalid expression\n"); return 0; }

22. C program to check for balanced parenthesis int match(char a,char b) { if(a=='[' && b==']') return 1; if(a=='{' && b=='}') return 1; if(a=='(' && b==')') return 1; else return 0; }/*End of match()*/ void push(char item ) { if(top==(MAX-1 )) { printf ("Stack Overflow\n"); } top=top+1; stack[top]=item; }/*End of push()*/ char pop() { if(top==-1 ) { printf ("Stack Underflow\n"); } return(stack[top--]); }/*End of pop()*/

23. Polish notations W ay to write arithmetic expression Consists of operand ,Operator An algebraic expression can be represented using three different notations . Infix e.g. ( A + B) * (C - D) Prefix e.g. * + A B – C D polish notation postfix e.g. A B + C D - * reverse polish notation/suffix notation OPERATOR PRECEDENCE VALUE Exponentiation, parenthesis (highest) *, /, % (Next highest) +, - ( Lowest)

24. Polish notations sr.No . Infix Notation Prefix Notation Postfix Notation 1 a + b +ab ab+ 2 (a + b) ∗ c (+ab)*c = *+ab (ab+)*c = ab+c * 3 a ∗ (b + c) a*(+ bc ) = * a+bc a*( bc +) = abc +* 4 a / b + c / d (/ab)+(/cd)=+/ab/cd (ab/)+(cd/)=ab/cd/+ 5 (a + b) ∗ (c + d) (+ab)*(+cd)=*+ ab+cd (ab+)*(cd)+ = ab+cd +* 6 ((a + b) ∗ c) - d ((+ab)*c)-d = (*+ abc )-d = -*+ abcd ((ab+)*c)-d = ( ab+c *)-d = ab+c *d-

25. Infix to postfix conversion Algorithm Create an empty Stack . Input the infix expression. Scan the infix arithmetic expression from left to right. If the scanned character is an operand, append it to the end of the output list. If the scanned character is a left parenthesis, push it on the stack . If the scanned character is a right parenthesis, pop the  stack  until the corresponding left parenthesis is removed, discard both the parenthesis(right as well as left). Append each operator to the end of the output list. If the scanned character is an operator, *, /, +, or -, push it on the  stack . However, first remove any operators already on the  stack  that have higher or equal precedence and append them to the output list. Repeat step 2 until the infix expression is scanned. Print the Stack output. Pop and output all characters, including the operator, from the Stack until it is not empty.

26. we have infix expression  (( A +B)*C+(D*E))   to convert into its equivalent postfix expression: Sr No. Symbol Scanned Stack Expression Comment 1 ( ( Push 2 ( (( Push 3 A (( A Print 4 + ((+ A Push 5 B ((+ AB Print 6 ) ( AB+ Pop 7 * (* AB+ Push 8 C (* AB+C Print 9 + (+ AB+C* Pop and push 10 ( (+( AB+C* Push 11 D (+( AB+C*D Print 12 * (+(* AB+C*D Push 13 E (+(* AB+C*DE Print 14 ) (+ AB+C*DE* Pop 15 ) AB+C*DE*+ Pop

27. Infix to prefix conversion Expression =  (A +(B^C))* D +(E^5) Step 1.  Reverse the infix expression.                 ) 5^E(+D*))C^B(+A ( Step 2.  Make Every '(' as ')' and every ')' as '('                  ( 5^E)+D*((C^B)+A ) Step 3.  Convert expression to postfix form(follow previous algorithm). 5E^DCB^A+*+ Step 4.  Reverse the expression.                  +*+ A^BCD^E5

28. Now, we have expression   ( 5^E)+D*((C^B)+A) to convert into its equivalent postfix expression: Sr No. Symbol Scanned Stack Expression Comment 1 ( ( Push 2 5 ( 5 Print 3 ^ (^ 5 Push 4 E (^ 5E Output 5 ) (^ 5E^ pop 6 + + 5E^ Push 7 D + 5E^D Print 8 * +* 5E^D Push 9 ( +* ( 5E^D push 10 ( +* ( ( 5E^D push 11 C +* (( 5E^DC Print 12 ^ +* (( ^ 5E^DC Push 13 B +* (( ^ 5E^DCB Print 14 ) +*( 5E^DCB^ pop 15 + +* (+ 5E^DCB^ push 16 A +* (+ 5E^DCB^A print 17 ) +* (+ 5E^DCB^A+ pop 18 +* 5E^DCB^A+*+ pop

29. The Queue ADT

30. 6- 30 Queues Queue : a collection whose elements are added at one end (the rear or tail of the queue) and removed from the other end (the front or head of the queue) A queue is a FIFO (first in, first out) data structure Any waiting line is a queue: The check-out line at a grocery store The cars at a stop light An assembly line

31. 6- 31 Conceptual View of a Queue Front of queue Adding an element New element is added to the rear of the queue

32. 6- 32 Conceptual View of a Queue Removing an element New front element of queue Element is removed from the front of the queue

33. 6- 33 Uses of Queues in Computing For any kind of problem involving FIFO data Printer queue Keyboard input buffer In simulation studies , where the goal is to reduce waiting time: Handling website traffic Maintaining the playlist in media players Optimize the flow of traffic at a traffic light Determine number of cashiers to have on duty at a grocery store at different times of day

34. Types of Queues   Simple/Linear Queue: M ost basic version of a queue Enqueue operation takes place at the rear end and dequeue operation takes place at the front end Circular Queue:   The element of the queue act as a circular ring Last element is connected to the first element Its advantage is that the memory is utilized in a better way Priority Queue:  Special type of queue which arranges the elements in a queue based on some priority. The priority can be something where the element with the highest value has the priority so it creates a queue with decreasing order of values. The priority can also be such that the element with the lowest value gets the highest priority so in turn it creates a queue with increasing order of values

35. 6- 35 enqueue : add an element to the tail(rear)of a queue dequeue : remove an element from the head(front) of a queue first : examine the element at the front of the queue (“peek”) Operation Description dequeue Removes an element from the front of the queue enqueue Adds an element to the rear of the queue first Examines the element at the front of the queue IsFull Determines whether the queue is full isEmpty Determines whether the queue is empty size Determines the number of elements in the queue Queue Operations

36. Enqueue operation Step 1 - Check whether queue is FULL. i.e. (rear == MAX-1) If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function . Step 2:If it is first element of queue, then set front=front+1 and rear=rear+1 Step 3 - If it is NOT first element, then increment rear value by one (rear++) Step 4 -set  queue[rear] =  value Step 5: Exit Void enqueue ( int value) Step 1:if rear==max-1 then; write overflow return end of if Step 2: If front==-1 && rear==- 1,then set front=front+1 and rear= rear+1 end of if Step 3: else set rear=rear+1 end of else Step 4:set queue(rear ) = value Step 5: Exit

37. Dequeue operation Step 1 - Check whether queue is EMPTY. (front==-1) If it is EMPTY, then display "Queue is EMPTY !!! Deletion is not possible!!!" and terminate the function. Step 2 - If it is NOT EMPTY, then print the front value i.e. queue[front] to be deleted Step 3-Check the value of front pointer. If it is equal to rear it means it is the last element of the queue. The queue will become empty after deleting this element. In this case set front and rear both pointers to -1. Step 4: Else increment the front value by one (front ++). Step 5:Exit Dequeue() Step 1:If front==-1 write underflow and return end of if Step 2: else set val = queue(front ) print(“The deleted value is %d”, val ) Step 3: if(front==rear) set front==rear==-1 Step 4: else set front=front+1 end of loop Step 5: Exit

38. Displaying a queue Step 1 -  Check whether  queue is EMPTY. (front == -1)  If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function. Step 2 - If it is NOT EMPTY, then traverse the queue from front position to rear position. Define an integer variable ' i ' and set ' i  =  front'. Display 'queue[ i ]' value and increment ' i ' value by one ( i ++). Repeat the same until ' i ' value reaches to rear ( i  <= rear ) Step 3: Exit Step 1:If front == -1 , write empty queue Step 2: else int i ; for( i =front ; i <=rear; i ++) printf ("% d", queue [ i ]); Step 3:Exit

39. Implementation of queue as array Step 1 -  Include all the  header files  which are used in the program and define a constant  'SIZE'  with specific value. Step 2 -  Declare all the  user defined functions  which are used in queue implementation. Step 3 -  Create a one dimensional array with above defined SIZE ( int queue[SIZE] ) Step 4 -  Define two integer variables  'front'  and ' rear ' and initialize both with  '-1' . ( int front = -1, rear = -1 ) Step 5 -  I mplement main method by displaying menu of operations list and make suitable function calls to perform operation selected by the user on queue.

40. Second Approach: Queue as a Circular Array Circular array is an array that conceptually loops around on itself The last index is thought to “ precede ” index 0 In an array whose last index is n , the location “ before ” index is index n ; the location “ after ” index n is index Need to keep track of where the front as well as the rear of the queue are at any given time 6- 40

41. Enqueue operation Step 1 - Check whether queue is FULL. ((rear == MAX-1 && front == 0) || (front == rear+1))   If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function . Step 2:If the inserted element is first element of the queue then set front=front+1 and rear=rear+1 Step 3 - If rear is at max index value of array ( rear == SIZE - 1), then implement queue in circular fashion set rear = 0 . Step 4 -  else, Increment  rear value by one (rear ++) Step 5 - set queue[rear] = value  Step 6: Exit Step 1:if (front==0 and rear ==MAX-1) or (front=rear+1)then ; write overflow and return Step 2: elseif front==-1 & rear==-1,then; front=front+1 and rear=rear+1 S tep 3: elseif rear ==max-1 set rear=0 else Step 4: set rear=rear+1 end of if Step 5 : set queue(rear)= num Step 6: Exit

42. Dequeue operation Step 1 - Check whether queue is EMPTY. (front == -1 ) If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the function. Step 2 - If it is NOT EMPTY, then display queue[front] as deleted element Step 3-If front is equal to rear it means that it is the only element of the queue. The queue will become empty after deleting this element. In this case set front and rear both pointers to -1. Step 4-If front is pointing to the last index value then implement queue in the circular fashion. Set front to point first index value of the array. Step 5- else increase the value of front pointer by 1 Step 6-Exit Step 1:If If front ==-1 write underflow and return Step2: else set val = queue(front ) print deleted value is val Step 3- if (front == rear) set front =rear= -1 ; Step 4- elseif (front == MAX-1) set front = 0 ; Step 5- else front = front+1; Step 6-Exit

43. Display operation S tep 1 - Check whether queue is EMPTY. ( front==- 1)  If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function. Step 2 - If it is NOT EMPTY, then define an integer variable ' i ' and set ' i  = front'. Step 3 - Check whether 'front <= rear', if it is TRUE, it means rear is right or equal to the front ,then display 'queue[ i ]' value and increment ' i ' value by one ( i ++). Repeat the same until ' i <= rear' becomes FALSE. Step 4 - If 'front <= rear' is FALSE, then display 'queue[ i ]' value and increment ' i ' value by one ( i ++). Repeat the same until'i <= SIZE - 1' becomes FALSE. Step 6 - Set  i  to 0. Step 7 - Again display ' cQueue [ i ]' value and increment  i  value by one ( i ++). Repeat the same until ' i <= rear' becomes FALSE. Step 1: if(front ==-1) write queue is empty else Step 2 - int i = front; if(front <= rear ) Step 3- while( i <= rear ) print c Queue [ i ]); i =i+1 else Step 4- while( i <= MAXSIZE - 1 ) print cQueue [ i ]); i =i+1 Step 5- i = 0; Step 6- while( i <= rear ) print cQueue [ i ]); i =i+1

44. Implementation of Circular Queue as array Step 1 -  Include all the  header files  which are used in the program and define a constant  'SIZE'  with specific value. Step 2 -  Declare all  user defined functions  used in circular queue implementation. Step 3 -  Create a one dimensional array with above defined SIZE ( int cQueue [SIZE] ) Step 4 -  Define two integer variables  'front'  and ' rear ' and initialize both with  '-1' . ( int front = -1, rear = -1 ) Step 5 -  Implement main method by displaying menu of operations list and make suitable function calls to perform operation selected by the user on circular queue.

45. Deque (Double ended queue) Generalized form of queue data structure which allows insertion and removal of elements from both the ends, i.e , front and back . I nherits the properties of both queues and stacks.

46. Types of Deque in Data Structure Input-Restricted Deque : performs deletion at both ends performs the insertion at only one end. Output-Restricted Deque : performs insertion at both ends performs the deletion of elements at only one end.

47. Operations on Deque Four basic operations are performed on deque , they are as follows: Insertion at Rear ( InsertRear ()) Insertion at Front ( InsertFront ()) Deletion at Front ( DeleteFront ()) Deletion at Rear ( DeleteRear ()) Along with these primary operations, isEmpty (), isFull () and Peek() operations can also be performed

48. Insert from Rear end Step 1 - Check whether queue is FULL. ((rear == MAX-1 && front == 0) || (front == rear+1))  If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function. Step 2:Else if inserted element is first element of the queue then set front=front+1 and rear=rear+1 Step 3 - If rear is at max value (rear == SIZE - 1), then implement queue in circular fashion set rear = 0. Step 4 - else, Increment rear value by one (rear++) Step 5 - set queue[rear] =  num   Step 6: Exit Void InsertRear ( int num ) Step 1:if (front==0 && rear==max-1) or (front=rear+1)then; write overflow Step 2: elseif front==-1 && rear==-1,then; set front=front+1 and rear=rear+1 Step 3: elseif rear ==max-1 set rear=0 else Step 4: set rear=rear+1 end of if Step 5: set queue[rear ] = num Step 6: Exit

49. Insert from Front end Step 1 - Check whether queue is FULL. ((rear == SIZE-1 && front == 0) || (front == rear+1))  If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function. Step 2:Else if inserted element is first element of the queue then set front=front+1 and rear=rear+1 Step 3 - If space is there in the array towards RHS , then implement queue in circular fashion set  front = max-1 Step 4 - else, Decrement   front  value by one (front--) Step 5 - set  queue[front]  =  num Step 6: Exit Void InsertFront ( int num ) Step 1:if (front==0 && rear==max-1) || (front=rear+1)then; write overflow Step 2: elseif front==-1 && rear==-1,then; set front=front+1 and rear=rear+1 Step 3: elseif front==0 set front=max-1 else Step 4: set front=front-1 end of if Step 5: set queue[front ] = num Step 6: Exit

50. Classwork Consider array of 5 elements and perform the following operations: InsertFront (10); InsertFront (20); InsertRear (30); InsertRear (40); InsertFront (50); InsertFront (60);

51. Delete from Rear end Step 1 - Check whether queue is EMPTY. (front ==rear== -1 ) If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the function. Step 2 - If it is NOT EMPTY, then display  queue[rear]  as deleted element Step 3-If front is equal to rear it means deleted element is the last element of the queue. The queue will become empty after deleting this element. In this case set front and rear both pointers to -1. Step 4-If rear is pointing to the first index value then set it to the max index value(circular array) Step 5- else decrease the value of rear pointer by 1 Step 6-Exit Step 1:If If front ==-1 && rear==-1 write underflow Step2: else set val = queue(rear) write deleted value is val Step 3- if (front == rear) set front =rear= -1 ; Step 4- elseif (rear==0) set rear = max-1; Step 5- else rear = rear-1; Step 6-Exit

52. Delete from Front end Step 1 - Check whether queue is EMPTY. (front == rear==-1 ) If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the function. Step 2 - If it is NOT EMPTY, then display queue[front] as deleted element Step 3-If front is equal to rear it means deleted element is the last element of the queue. The queue will become empty after deleting this element. In this case set front and rear both pointers to -1. Step 4-If front is pointing to the last index value then set it to the first index value(circular array) Step 5- else increase the value of front pointer by 1 Step 6-Exit Step 1:If If front ==-1 && rear==-1 write underflow Step2: else set val = queue(front ) write deleted value is val Step 3- if (front == rear) set front =rear= -1 ; Step 4- elseif (front == MAX-1) set front = 0 ; Step 5- else front = front+1; Step 6-Exit

53. Classwork Consider array of 5 elements and perform the following operations: InsertFront (10); InsertFront (20); InsertRear (30); InsertRear (40); InsertFront (50); InsertFront (60); DeleteFront (); DeleteFront (); DeleteRear (); DeleteFront (); DeleteRear ();

54. Display operation S tep 1 - Check whether queue is EMPTY. ( front==- 1)  If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function. Step 2 - If it is NOT EMPTY, then define an integer variable ' i ' and set ' i  = front'. Step 3 - Check whether 'front <= rear', if it is TRUE, it means rear is right or equal to the front ,then display 'queue[ i ]' value and increment ' i ' value by one ( i ++). Repeat the same until ' i <= rear' becomes FALSE. Step 4 - If 'front <= rear' is FALSE, then display 'queue[ i ]' value and increment ' i ' value by one ( i ++). Repeat the same until'i <= SIZE - 1' becomes FALSE. Step 6 - Set  i  to 0. Step 7 - Again display ' cQueue [ i ]' value and increment  i  value by one ( i ++). Repeat the same until ' i <= rear' becomes FALSE. Step 1: if(front ==-1) write queue is empty else Step 2 - int i = front; if(front <= rear ) Step 3- while( i <= rear ) print c Queue [ i ]); i =i+1 else Step 4- while( i <= MAXSIZE - 1 ) print cQueue [ i ]); i =i+1 Step 5- i = 0; Step 6- while( i <= rear ) print cQueue [ i ]); i =i+1

55. Priority queue Special type of queue  in which each element is associated with a  priority value . Elements are served on the basis of their priority. That is, higher priority elements are served first. S ame priority elements are served according to their order in the queue. A priority queue is an extension of a queue that contains the following characteristics : Every element in a priority queue has some priority associated with it. An element with the higher priority will be deleted before the deletion of the lesser priority. If two elements in a priority queue have the same priority, they will be arranged using the FIFO principle/they will be arranged according to their values.

56. Difference between Priority Queue and Normal Queue In a queue, the  first-in-first-out rule  is implemented whereas, in a priority queue, the values are removed  on the basis of priority . The element with the highest priority is removed first . When an element is popped out of the priority queue, the result will be in the sorted order of priority, it can be either increasing or decreasing. While in queue elements are popped out in the order of  FIFO (First in First out) .

57. Implementation of priority queue Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree. Among these data structures, heap data structure provides an efficient implementation of priority queues. Array Approach:  The idea is to create a structure to store the value and priority of the element and then create an  array  of that structure to store elements or create two arrays one for inserting values and another for inserting priority. Below are the functionalities that are to be implemented: enqueue ():  It is used to insert the element at the end of the queue. peek(): Traverse across the priority queue and find the element with the highest priority and return its index. In the case of multiple elements with the same priority, find the element with the highest. dequeue (): Find the index with the highest priority using the  peek()  function let’s call that position as  ind , and then shift the position of all the elements after the position  ind  one position to the left.

58. Priority queue implementation using array Create two arrays one for inserting values( array queue ) and another for inserting priority( array priority ).

59. Priority queue implementation using array Enqueue operation(Insert value and priority in queue via rear end) Step 1 - Check whether queue is FULL. i.e. (rear == MAX-1) If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function. Step 2:If queue is not full then increment  rear value by one (rear++) Step 4 -set queue[rear] =  value, priority[rear]= pri Step 5: Exit

60. Priority queue implementation using array Peek operation( Traverse across the priority queue and find the element with the highest priority and return its index) Step 1 - Check whether queue is  Empty i.e. (rear == -1) If it is  empty, then display "Queue is empty!!! search is not possible!!!" and terminate the function. Step 2 - If queue is not empty then to search the highest priority element, use a for loop to traverse priority array which starts from index 0 to rear end and return the index value(suppose idx ) of highest priority element. Step 3 - Exit

61. Priority queue implementation using array Dequeue operation Step 1 - Check whether queue is  Empty i.e. (rear == -1) If it is  empty, then display "Queue is empty!!! deletion is not possible!!!" and terminate the function. Step 2:Get the index value(suppose idx ) returned by peek function. Step 3 : If queue is not empty then use a for loop which starts from idx and goes till rear end. Print the element which is present at idx index and then shift all the elements one position left from index where the highest priority item was found. Step 4 : Exit

62. Application of queue data structure Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU. Queues are used as buffers in most of the applications like MP3 media player, CD player, etc. Queue are used to maintain the play list in media players in order to add and remove the songs from the play-list. Queues are used in operating systems for handling interrupts . It is used in traffic management to manage traffic lights . Whatsapp uses a queue to queue up the messages in the WhatsApp server if the recipient’s internet connection is turned off.

63. Linked list data structure

64. Linked List Collection of nodes  that are randomly stored in the memory. Each node stores the  data  and the  address  of the next node . We have to start somewhere, so we give the address of the first node a special name called HEAD The last node of the list contains pointer to the null. Why use linked list over array? It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the memory and linked together with the help of pointers. Sizing is no longer a problem since we do not need to define its size at the time of declaration. List grows as per the program's demand and limited to the available memory space.

65. Advantages and Disadvantages of Linked List Advantages: Linked lists are dynamic data structures : That is , they can grow or shrink during execution of a program. Efficient memory utilization : Here memory is not pre-allocated. Insertion and deletions are easier and efficient : Linked list provide flexibility in inserting a data item at a specified position and deletion of a data item from the given position. Disadvantages : Random access is not allowed . We have to access elements sequentially starting from the first node. So it is difficult to perform binary search with linked lists. It cannot be easily sorted . More complex to create than an array. Extra memory space for a pointer is required with each element of the list.

66. Operations on Linked list Creation Insertion Deletion Traversing Searching Concatenation Display

67. Types of Linked List Following are the various types of linked list. Singly Linked List  − Item navigation is forward only. Doubly Linked List  − Items can be navigated forward and backward. contains a link to the previous node Circular Linked List  − Last item contains link of the first element as next and the first element has a link to the last element as previous.

68. Structure in C (linked representation) Collection of variables (can be of different types) under a single name . To define a structure, the struct keyword is used . Syntax of structure struct structureName { dataType member1; dataType member2; ... }; Example: struct Person { char name[50]; int citNo ; float salary; };

69. Pointers in C The pointer in C language is  a variable which stores the address of another variable . This variable can be of type int , char, array, function, or any other pointer. F or example int   a  = 10;    int *  ptr  =  &a;  // Variable p of type pointer is pointing to the address of the variable n of type integer. 

70. Self Referential structure Self Referential structure is a structure which contains a pointer to a structure of the same type. Example Struct abc { int a; char b; struct abc *self; }; Self Referential structure is used to create a node of the linked list.

71. Creating a node of a linked list Creating single node struct node { int data; struct node *next; }; Each node consists: A data item An address of next node So a node can be created using structures Each struct node has a data item and a pointer to another struct node

72. Steps to create the linked list Step 1-Creating node structure Step 2- Initialize nodes Step 3- Allocate memory using malloc function Step 4-Assign data values Step 5-Connect nodes

73. Creating a node Step 1-Creating node structure struct node { int data; struct node *next; }; Step 2- /* Initialize nodes */ struct node * head=NULL; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; Step 3- /* Allocate memory */ one = malloc ( sizeof ( struct node)); two = malloc ( sizeof ( struct node)); three = malloc ( sizeof ( struct node)); Step 4- /* Assign data values */ one->data = 1; two->data = 2; three->data=3; Step 5- /* Connect nodes */ one->next = two; two->next = three; three->next = NULL ; Step 6- /* Save address of first node in head */ head = one;

74. Main program // Linked list implementation in C #include < stdio.h > #include < stdlib.h > // Creating a node struct node { int value; struct node *next; }; // print the linked list value using a temporary pointer temp void printLinkedlist ( struct node *temp) { while (temp != NULL) { printf("%d ", p->value); temp = temp-> next; }} int main() { // Initialize nodes struct node * head=NULL; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; // Allocate memory one = malloc ( sizeof ( struct node)); two = malloc ( sizeof ( struct node)); three = malloc ( sizeof ( struct node)); // Assign value values one->value = 1; two->value = 2; three->value = 3; // Connect nodes one->next = two; two->next = three; three->next = NULL; // printing node-value head = one; printLinkedlist (head); }

75. Doubly linked list Creating a node struct node { int data; struct node *next; struct node * prev ; } /* Initialize nodes */ struct node * head=NULL; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL /* Allocate memory */ one = malloc ( sizeof ( struct node)); two = malloc ( sizeof ( struct node)); three = malloc ( sizeof ( struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one-> prev = NULL; two->next = three; two-> prev = one; three->next = NULL; three-> prev = two; /* Save address of first node in head */ head = one ;

76. Circular linked list Creating a node struct node { int data; struct node *next; struct node * prev ; } * Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc ( sizeof ( struct node)); two = malloc ( sizeof ( struct node)); three = malloc ( sizeof ( struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;

77. Singly linked list Inserting a new node in a linked list Case 1:The new node is inserted at the beginning Case 2:The new node is inserted at the end Case 3:The new node is inserted after a given node Case 4:The new node is inserted before a given node

78. Insertion at the beginning Create and allocate memory for new node Store data Check if it is the first node of the linked list set next of new node to null value set head to recently created node If it is not the first node then set next of new node to head set head to recently created node Void InsertBegin ( int value) struct node * newNode =null; newNode = malloc ( sizeof ( struct node)) newNode - >data = value If (head==null) newnode -> next=null; head= newnode ; Else newNode ->next = head; head = newNode ;

79. Insertion at the end Create and allocate memory for new node Store data in newnode and set its next field as null as node is inserted at the end. Check if it is the first node of the linked list, then set next of new node to null set head to point to recently created node Else ,Traverse to last node using temp pointer which initially points to head node Change next of last(temp) node to recently created node Void InsertEnd ( int value) struct node * newNode =null; newNode = malloc ( sizeof ( struct node)) newNode ->data = value newNode ->next = NULL If(head ==null) head= newnode ; newNode - >next = NULL; Else struct node *temp = head while(temp->next != NULL) { temp = temp->next; } temp->next = newNode ; newNode - >next = NULL;

80. Inserting a node after a given node(having value NUM) Void Insertafter ( int value) 1) struct node * newNode =NULL; newNode = malloc ( sizeof ( struct node)) 2 ) set newnode -> data=value 3) set temp =head 4) Repeat step 5 while temp-> data!=NUM 5) Set temp=temp->next End of loop 6) Set newnode -> next=temp->next 7) Set temp->next= newnode 8 ) exit Create and allocate memory for new node Store data Traverse the linked list upto  the node using temp pointer after which the node has to be inserted Point the next pointer of new node to the next pointer of temp node. Point the next pointer of temp node to next pointer of newnode .

81. Inserting a node before a given node(having value NUM) Void InsertBefore ( int value) 1 ) struct node * newNode =NULL newNode = malloc ( sizeof ( struct node)) 2 ) set newnode -> data=value 3) set temp =head 4 ) Repeat steps 5 to 6 while temp-> data!=NUM 5 ) Set q=temp 6 ) Set temp=temp-> next End of while loop 7 ) newnode ->next=temp 8 ) q->next= newnode 9 ) exit Create and allocate memory for new node, Store data in newnode Traverse the linked list using temp pointer upto  the node before which the node has to be inserted. Use a q pointer which points to the node which is just behind of temp pointer. Point the next pointer of newnode to the temp node. Point the next pointer of q to the newnode node.

82. Deleting a node from a linked list Case 1:The first node is deleted Case 2:The last node is deleted Case 3:The node for a given position

83. Deleting the first node from a linked list Void DeleteBegin () 1 ) If head==null write “underflow” go to step no 5 end of if 2) Else if(head->next==null) printf (“%d”, head->data) Set head=null free(head) 3 ) Else Set temp=head printf (“%d”, head->data) Set head=head- >next 4) Free temp 5) exit Check the value of head pointer. If it is equal to null then print “underflow” Else if check next field of head. If it is equal to null, it means it is the last/only node of the link list, then print the node value and set head to null value. Else use a temp pointer .Set its value as head pointer, print the value and shift the head to the next node. Delete the node where temp is pointing free the memory used by temp pointer. End

84. Deleting the last node from a linked list Void DeleteEnd () 1 ) If head==null write “underflow” go to step no 8 end of if 2) Else if(head- >next==null ) printf (“%d”, head->data) Set head=null free(head) 3) temp=head Repeat steps 4 and 5 while temp->next!= null 4) Set q=temp Set temp=temp->next end of loop 6) printf (“%d”, temp-> data) Set q->next=null 7) Free temp 8) exit Check the value of head pointer. If it is equal to null then print “underflow” Else if check next field of head. If it is equal to null, it means it is the last/only node of the link list, then print the node value and set head to null value. Else use a temp pointer to reach to the last node of the linked list. Set its initial value as head pointer. Use a q pointer which points to the node which is just behind of temp pointer. Repeat steps 4 and 5 till next field of temp becomes null. 4) Point the next pointer q node to the temp node. Set the temp to next pointer of temp. Print the value, Set next field of q as null value as now it is the last node of the linked list. Free the memory of temp using free command. exit

85. Deleting the node of a specified position Check the value of head pointer. If it is equal to null then print “underflow” Specify the position of the node to be deleted Use a for loop to traverse to the node to be deleted Use a temp pointer to hold the address of the node to be deleted Use a q pointer which points to the node which is just behind of temp pointer Print the value, set next pointer of q as next pointer of temp Delete the temp node and free the memory Void DeleteSpos () 1) If head==null write “underflow ” and exit 2) Else temp=head For( int i=1;i< pos;i ++) q=temp temp=temp->next; q ->next=temp->next f ree(temp)

86. Algorithm printing/displaying a linked list Check the value of head pointer. If it is equal to null then print “Empty list” Else if check next field of head. If it is equal to null, it means it is the last/only node of the link list, then print the node value and set head to null value. Else use a temp pointer to traverse the linked list .Set its value as head pointer Display the values of the linked list till temp reaches to last node. End

87. Doubly linked list Variation of Linked list in which navigation is possible in both ways, either forward and backward easily. every node has a link to its previous node and next node.

88. Insertion at the beginning Step 1 -  Create a  newNode  with given value ,set   newNode → previous  as  NULL . Step 2 -  Check whether list is  Empty  ( head  ==  NULL ) Step 3 -  If it is  Empty  then, assign  NULL  to  newNode → next  and  newNode  to  head . Step 4 -  If it is  not Empty  then, assign  head  to  newNode → next  , head->previous= newNode and  newNode  to  head . C code: void insert_begin ( int value) { struct Node * newnode =NULL; newnode = malloc ( sizeof ( struct Node)); newnode -> data = value; newnode -> previous = NULL; if(head == NULL) { newnode -> next = NULL; head = newnode ; } else { newnode -> next = head; head->previous= newnode ; head = newnode ; } printf("\ nInsertion success!!!"); }

89. Insertion at the end Algorithm: Step 1 -  Create a  newNode  with given value and  newNode → next  as  NULL . Step 2 -  Check whether list is  Empty  ( head  ==  NULL ) Step 3 -  If it is  Empty , then assign  NULL  to  newNode → previous  and  newNode  to  head . Step 4 -  If it is  not Empty , then, define a node pointer  temp  and initialize with  head . Step 5 -  Keep moving the  temp  to its next node until it reaches to the last node in the list (until  temp → next  is equal to  NULL ). Step 6 -  Assign  newNode  to  temp → next  and  temp  to  newNode → previous . void insert_end ( int value) { struct Node * newnode =NULL; newnode = malloc ( sizeof ( struct Node)); newnode -> data = value; newNode -> next = NULL; if(head == NULL) { newNode -> previous = NULL; head = newNode ; } else { temp = head; while(temp -> next != NULL) { temp = temp -> next; } temp -> next = newNode ; newNode -> previous = temp; } printf ("\ nInsertion success!!!"); }

90. Insertion after an element Algorithm: Allocate memory to the new node Store data Traverse the Linked list upto  the node using temp pointer after which the node has to be inserted.(temp=temp->next) Point the previous pointer of temp->next to newnode Point the next pointer of new node to temp->next. Point the next pointer of temp to the new node. Point the previous pointer of the new node to temp. Code: void insert_afterpos ( int value) { struct Node * newnode =NULL; newnode = malloc ( sizeof ( struct Node)); newnode -> data = value; printf("Enter element after which to insert new element:"); scanf ("%d",& val ); temp=head ; while(temp>data != val ) { temp=temp->next; } temp->next-> previous= newnode ; newnode ->next = temp->next; temp->next = newnode ; newnode -> previous=temp ; }

91. Insertion before an element Algorithm: Allocate memory to the new node Store data Traverse the Linked list upto  the node using temp pointer before which the node has to be inserted. Point the previous pointer to the new node to the previous pointer of temp. Point the next pointer of temp->previous to the new node. Point the next pointer of new node to temp Point the previous pointer of temp to the new node. void insert_beforepos ( int value) { struct Node * newnode =NULL; newnode = malloc ( sizeof ( struct Node)); newnode -> data = value; printf("Enter element after which to insert new element:"); scanf ("%d",& val ); newnode ->data= num ; temp=head; while(temp- >data!= val ) { temp=temp- >next; } newnode -> previous=temp- > prev ; temp-> previous- >next= newnode ; newnode ->next=temp; temp-> previous= newnode ; return; }

92. Delete from beginning Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) Step 2 -  If it is  Empty  then, display  'List is Empty!!! Deletion is not possible'  and terminate the function. Step 3 -  If it is not Empty then check whether list is having only one node ( head → previous   ==NULL &&   head → next==NULL ) Step 5 -  If it is  TRUE , then set  head  to  NULL  and delete  head   (deallocate the memory) Step 6 -  If it is  FALSE , then define a Node pointer  'temp'  and initialize with  head , assign   head → next  to  head ,  NULL  to  head → previous  and delete  temp (deallocate the memory ). void delete_beg () { if(head==NULL) { printf("The list is empty!!"); } else if(head-> previous ==NULL && head->next==NULL) { printf ("Deleted element is % d ",head -> data); head=NULL; free(head); } else { temp=head ; head=head->next; head->previous=NULL; printf("Deleted element is % d",temp ->data); free(temp); } }

93. Deleting node from the end Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) Step 2 -  If it is  Empty  then, display  'List is Empty!!! Deletion is not possible'  and terminate the function. Step 3 -  If it is not Empty then check whether list is having only one node ( head → previous  ==NULL &&   head → next==NULL ) Step 5 -  If it is  TRUE , then set  head  to  NULL  and delete  head  (deallocate the memory Step 6 -  If it is  FALSE , then define a Node pointer  'temp'  and initialize with  head , keep moving  temp  until it reaches to the last node in the list. (until  temp → next  is equal to  NULL ) Step 7 -  Set next of temp-> prev to NULL pointer q which points to the previous node of temp .Set q->next=null and delete  temp . void delete_end () { if (head==NULL) { printf("The list is empty!!"); } else if(head- > prev == NULL && head->next==NULL ) { printf("Deleted element is % d",head ->data); head=NULL; free(head); } else { temp=head; while(temp->next!=NULL) {temp=temp- >next ; } printf("Deleted element is % d",temp ->data ); temp- > prev ->next=NULL; free(temp ); } }

94. Deleting node from a specific position Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) Step 2 -  If it is  Empty  then, display  'List is Empty!!! Deletion is not possible'  and terminate the function. Step 3 -  If it is not Empty then check whether list is having only one node ( head → previous  ==NULL &&   head → next==NULL ) Step 4 -  If it is  TRUE , then set  head  to  NULL  and delete  head  (deallocate the memory Step 5 -  If it is  FALSE , then define a Node pointer  'temp'  and initialize with  head , keep moving  temp  until it reaches to the exact node which we want to delete. Use a pointer q which points to the previous node of temp Step 6 - Set   q- >next=temp->next and temp->next-> prev =temp-> next and delete  temp  ( free(temp) ). printf("Enter position to delete:"); scanf ("%d",& pos ); int delete_pos () { int pos,i ; if(head==NULL) { printf("List is empty!!"); return 0; } Else if(head-> prev ==NULL && head->next==NULL ) { printf("Deleted element is % d",head ->data); head=NULL; free(head ); } Else { temp=head; for( i =1;i<pos-1;i++) { q=temp; temp=temp- >next ; } q->next=temp- >next; temp-> next-> prev =temp-> next; printf ("Deleted element is % d",temp ->data); free(temp); }

95. Displaying linked list Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) Step 2 -  If it is  Empty , then display  'List is Empty!!!'  and terminate the function. Step 3 -  If it is not Empty, then define a Node pointer  'temp'  and initialize with  head . Step 4 -  Keep displaying  temp → data  with an arrow ( <===> ) until  temp  reaches to the last node Step 6 -  Finally, display  temp → data  with arrow pointing to  NULL  ( temp → data ---> NULL ). void display() { if(head==NULL) { printf("List is empty!!"); } else { temp=head; printf("The linked list is:\n"); while(temp!=NULL) { printf("%d < = = >",temp->data); temp=temp->next; } } }

96. circular linked list Insertion Deletion Display Step 1 -  Include all the  header files  which are used in the program. Step 2 -  Declare all the  user defined  functions. Step 3 -  Define a  Node  structure with two members  data  and  next Step 4 -  Define a Node pointer ' head ' and set it to  NULL . Step 5 -  Implement the  main  method by displaying operations menu and make suitable function calls in the main method to perform user selected operation.

97. Insertion Inserting At Beginning of the list Inserting At End of the list Inserting At before any element in the list Inserting At after an element in the list

98. Inserting At Beginning of the list Step 1 -  Create a  newNode  with given value. Step 2 -  Check whether list is  Empty  ( head  ==  NULL ) Step 3 -  If it is  Empty  then, set  head  =  newNode  and  newNode→next  =  head  . Step 4 -  If it is  Not Empty  then, define a Node pointer ' temp ' and initialize with ' head '. Step 5 -  Keep moving the ' temp ' to its next node until it reaches to the last node (until ' temp → next  ==  head '). Step 6 -  Set ' newNode → next  = head ', ' head  =  newNode ' and ' temp → next  =  head '.

99. Inserting At End of the list Step 1 -  Create a  newNode  with given value. Step 2 -  Check whether list is  Empty  ( head  ==  NULL ). Step 3 -  If it is  Empty  then, set  head  =  newNode  and  newNode → next  =  head . Step 4 -  If it is  Not Empty  then, define a node pointer  temp  and initialize with  head . Step 5 -  Keep moving the  temp  to its next node until it reaches to the last node in the list (until  temp → next   !=   head ). Step 6 -  Set  temp → next  =  newNode  and  newNode → next  =  head .

100. Inserting a node after a given node(having value NUM) 1) struct node * newNode newNode = malloc ( sizeof ( struct node)) 2 ) set newnode ->data= val 3) set temp =head 4) Repeat step 5 while temp-> data!=NUM 5) Set temp=temp->next End of loop 6) Set newnode -> next=temp->next 7) Set temp->next= newnode 8 ) exit Create and allocate memory for new node Store data Traverse the linked list upto  the node using temp pointer after which the node has to be inserted Point the next pointer of new node to the next pointer of temp node. Point the next pointer of temp node to next pointer of newnode .

101. Inserting a node before a given node(having value NUM) 1) struct node * newNode newNode = malloc ( sizeof ( struct node)) 2 ) set newnode ->data= val 3) set temp =head 4 ) Repeat steps 5 to 6 while temp-> data!=NUM 5 ) Set q=temp 6 ) Set temp=temp-> next End of while loop 7 ) newnode ->next=temp 8 ) q->next= newnode 9 ) exit Create and allocate memory for new node, Store data in newnode Traverse the linked list using temp pointer upto  the node before which the node has to be inserted. Use a q pointer which points to the node which is just behind of temp pointer. Point the next pointer of newnode to the temp node. Point the next pointer of q to the newnode node.

102. Deletion operation Deleting from Beginning of the list Deleting from End of the list Deleting a Specific Node

103. Deleting from Beginning of the list Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) If it is  Empty  then, display  'List is Empty!!! Deletion is not possible'  and terminate the function. Step 2 - Else if check next field of head. If it is equal to head, it means it is the last/only node of the link list, then print the node value, set head to null value and free the head node. Step 3 - Else set temp=head, q=head and traverse the linked list till last node using temp. Step 4:Set head=head->next, temp->next=head . Delete the q node and free the memory.

104. Deleting from End of the list Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) Step 2 -  If it is  Empty  then, display  'List is Empty!!! Deletion is not possible'  and terminate the function .   If it is  Not Empty  then, define temp pointer and initialize ' temp ' with  head . Step 3 - Else if check next field of head. If it is equal to head, it means it is the last/only node of the link list, then print the node value and set head to null value. Step 4 -  Else define a node pointer  temp  and initialize with  head . Keep moving the  temp  to its next node until it reaches to the previous of last node in the list (until  temp → next → next  !=  head ). Use a q pointer which points to the node which is just behind of temp pointer. Step 5 -  free temp → next and se t temp->next=head

105. Deleting the node of a specified position Check the value of head pointer. If it is equal to null then print “underflow” Specify the position of the node to be deleted Use a pointer to traverse to the node to be deleted Use a temp pointer to hold the address of the node to be deleted Use a q pointer which points to the node which is just behind of temp pointer Set next pointer of q as next pointer of temp Delete the temp node and free the memory

106. Displaying a circular Linked List Step 1 -  Check whether list is  Empty  ( head  ==  NULL ) Step 2 -  If it is  Empty , then display  'List is Empty!!!'  and terminate the function. Step 3 -  If it is  Not Empty  then, define a Node pointer  'temp'  and initialize with  head . Step 4 -  Keep displaying  temp → data  with an arrow ( ---> ) until  temp  reaches to the head node Step 5 -  Finally display  temp → data  with arrow pointing to  head → data .

107. Linked representation of STACK push - place an item on the stack peek - Look at the item on top of the stack, but do not remove it pop - Look at the item on top of the stack and remove it

108. Representation of stack using linked list Why linked list representation Where to insert and delete stack elements in the linked list Prefer at the beginning of the stack

109. Push operation using linked list Step 1:create a new code, allocate memory and insert data Step 2:Check if it is the first node (top==NULL).If yes, then set newNode ->next=NULL and top= newNode Step 3:Else put the address of the top node in the next field of newNode Step 4:Update the top pointer and make it point to the new node of the linked list Void push( int value) { s truct node * newNode = NULL; Newnode = malloc ( sizeof ( struct Node )); newNode ->data = value; if(top == NULL) { newNode ->next = NULL; top= newNode ; } else { newNode ->next = top; top = newNode ; printf ("\ nInsertion is Success!!!\n"); } }

110. Pop operation Step 1 - Check whether stack is Empty (top == NULL). Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'. Step 4 - Then set 'top = top → next'. Step 5 - Finally, delete 'temp'. (free(temp)). Void pop() If(top == NULL) printf ("\ nStack is Empty!!!\n"); E lse { struct Node *temp = top; printf ("\ nDeleted element: %d", temp->data); top = temp->next; free(temp); } }

111. Peek operation Step 1 - Check whether stack is Empty (top == NULL). Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function Step 3 - If it is Not Empty, then display the top value(top->data) Void peek() { If(top == NULL) printf ("\ nStack is Empty!!!\n"); E lse { printf ("\ ntop element is: %d", top-> data); } }

112. display operation Step 1 - Check whether stack is Empty (top == NULL). Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function. Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top. Step 4 - Display 'temp → data' and move it to the next node. Repeat the same until temp reaches to the first node in the stack. (temp → next != NULL). Step 5 - Finally! Display 'temp → data ---> NULL'. if(top == NULL) printf ("\ nStack is Empty!!!\n"); else{ struct Node *temp = top; while(temp->next != NULL){ printf ("%d--->",temp->data); temp = temp -> next; } printf ("%d---> NULL",temp ->data); }

113. Representation of queue using linked list In a linked queue, each node of the queue consists of two parts i.e. data part and the next part. Each element of the queue points to its immediate next element in the memory. Operations with queue: Enqueue – Insert a node to the linked list from rear end Dequeue - - Delete a node from the front end Display – Display the data value of the nodes in the linked list

114. Representation of queue using linked list Step 1 -  Include all the  header files  which are used in the program. And declare all the  user defined functions . Step 2 -  Define a ' Node ' structure with two members  data  and  next . Step 3 -  Define two  Node  pointers ' front ' and ' rear ' and set both to  NULL . Step 4 -  Implement the  main  method by displaying Menu of list of operations and make suitable function calls in the  main  method to perform user selected operation.

115. Enqueue operation using linked list Create and allocate memory for new node Store data in newnode and set its next field as null as node is inserted at the end. Check if it is the first node of the linked list, then set front and rear to point to recently created new node Else ,set next pointer of rear to newnode . Change rear to newnode . Void enqueue ( int value) { struct node * newNode = NULL; Newnode = malloc ( sizeof ( struct Node)); newNode ->data = value; newnode - >next=NULL; if(front==NULL && rear==NULL ) { front= newnode ; rear= newnode ; } else { rear->next= newnode ; rear= newnode ; }}

116. dequeue operation using linked list Step 1 - Check whether queue is Empty (front == NULL). Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and terminate from the function Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'. Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)). Void dequque () { if(front == NULL) printf("\ nQueue is Empty!!!\n"); else { struct Node *temp = front; front = front -> next; printf("\ nDeleted element: %d\ n ",temp - >data); free(temp ); }}

117. display operation using linked list Check whether queue is Empty (front == NULL). If it is Empty then, display 'Queue is Empty!!!' and terminate the function. If it is Not Empty then, define a Node pointer 'temp' and initialize with front. Display 'temp → data --->' and move it to the next node. Repeat the same until 'temp' reaches to 'rear' (temp → next != NULL). Code: if(front == NULL) printf("\ nQueue is Empty!!!\n"); else{ struct Node *temp = front; while(temp != NULL){ printf("%d--->",temp->data); temp = temp -> next; } }

118. Applications of linked list-polynomial addition Linked list  is a data structure that stores each element as an object in a node of the list. every node contains two data parts and links to the next node. Polynomial  is a mathematical expression that consists of variables and coefficients. for example x^2 - 4x + 7 In the  Polynomial linked list , the coefficients and exponents of the polynomial are defined as the data node of the list.

119. Coefficient Field –  The coefficient field holds the value of the coefficient of a term Exponent Field –  The Exponent field contains the exponent value of the term Link Field –  The linked field contains the address of the next term in the polynomial

120. Algorithm Include libraries and create structure of the node. Initialize three head pointers head1, head2, head3, for the two input polynomials and resultant polynomial. Then, we create two linked list by inserting coefficients and exponent values to both the linked lists. When polynomials are created in sorted order, next step is to add them according to the exponent value. Consider pointer temp1 and temp2 for traversing poly1. We will consider three cases: Case 1:If exponent value of poly1 is equal to the exponent value of poly 2,then add their coefficient terms directly and output their addition. Move temp1 and temp2 to the next position. Case 2:If exponent value of poly1 is greater than the exponent value of poly 2,then output poly1 as it is. Move temp1 to the next position. Case 3:If exponent value of poly1 is less than the exponent value of poly 2,then output poly2 as it as. Move temp2 to the next position Continue to append the remaining nodes(temp1->next==temp2->next==NULL) from  or   until we finish the calculation on all nodes

121. Memory allocation and de allocation in linked list malloc() function Stands for memory allocation Used to allocate a block of memory dynamically. ptr = ( cast_type *) malloc ( byte_size ); It reserves memory space of specified size and returns the pointer pointing to the memory location. Example: ptr = ( int *) malloc (50) When this statement is successfully executed, a memory space of 50 bytes is reserved. The address of the first byte of reserved space is assigned to the pointer ptr of type int. free() function release/ deallocate memory in C.