CU-BCA-SEM-III-DATA STRUCTURES- Second Draft-converted

d. All of these 4. Which of the following is not an inherent application of stack? a. Reversing a string b. Evaluation of postfix expression c. Implementation of recursion d. Job scheduling 5. The type of expression in which operator succeeds its operands is an a. Infix Expression b. Prefix Expression c. Postfix Expression d. Both Prefix and Postfix Expressions Answer 1. (d) 2. (a) 3. (a) 4. (d) 5. (c) 7.9 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ e. https://www.tutorialspoint.com 101 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 8: QUEUES Structure 8.0 Learning Objectives 8.1 Introduction 8.2 Primitive Operations: Insertion, Deletion 8.3 Summary 8.4 Keywords 8.5 Learning activity 8.6 Unit End Questions 8.7 References 8.0 LEARNING OBJECTIVES After studying this unit, the student will be able to: • Explain the concepts of Basic Queue Operations. • Evaluate how to implement the ADTs queue. • State the properties where stacks, queues, and deques are appropriate data structures. 8.1 INTRODUCTION A queue is an ordered list that permits insert operations to be performed at one end (REAR) and take away operations to be performed at the opposite end (FRONT). the primary In First Out list is mentioned as a queue. People in line for a railroad ticket, for instance, form a queue. Figure 8.1: Queue Representation 102 CU IDOL SELF LEARNING MATERIAL (SLM)

A Queue may be a FIFO (First in First Out) arrangement where the element that's added first are going to be deleted first. the essential queue operations are enqueued (insertion) and dequeue (deletion). Enqueue is completed at the front of the queue and dequeue is completed at the top of the queue. the weather during a queue is arranged sequentially and hence queues are said to be linear data structures. 8.2 PRIMITIVE OPERATIONS: INSERTION, DELETION Queue ADT: A queue is an object (an abstract arrangement - ADT) that permits the subsequent operations: 1. Enqueue: Add a component to the top of the queue 2. Dequeue: Remove a component from the front of the queue 3. IsEmpty: Check if the queue is empty 4. IsFull: Check if the queue is full 5. Peek: Get the worth of the front of the queue without removing it Figure 8.2: Queue ADT Operations Enqueue: Add an element to the end of the queue Queues have two data pointers, one in front and one in the Rear. As a result, its operations are more complex to execute than stack operations. The rear is used to insert the element into the queue Algorithm: procedure enqueue(data) if queue is full return overflow endif rear ← rear + 1 queue[rear] ← data 103 CU IDOL SELF LEARNING MATERIAL (SLM)

return true end procedure Dequeue: Remove an element from the front of the queue Queues have two data pointers, one in front and one in the Rear. As a result, its operations are more complex to execute than stack operations. The front is used to delete the element from the queue. Algorithm: procedure dequeue if queue is empty return underflow end if data = queue[front] front ← front + 1 return true end procedure IsEmpty: Check to see if the queue is empty or not. Algorithm: begin procedure isempty if front is less than MIN OR front is greater than rear return true else return false endif end procedure Example: bool isempty() { if(front < 0 || front > rear) return true; else return false; 104 CU IDOL SELF LEARNING MATERIAL (SLM)

} IsFull: Check if the queue is full. As we are using a single dimension array to implement a queue, we just check for the rear pointer to reach MAXSIZE to determine that the queue is full. Algorithm: begin procedure isfull if rear equals to MAXSIZE return true else return false endif end procedure Example: bool isfull() { if(rear == MAXSIZE - 1) return true; else return false; } Peek: Get the value of the front of the queue without removing it Algorithm: begin procedure peek return queue[front] end procedure Example: int peek() { return queue[front]; } 8.3 SUMMARY 105 CU IDOL SELF LEARNING MATERIAL (SLM)

• A Queue is a FIFO data structure where the element that is added first will be deleted first. The basic queue operations are enqueued (insertion) and dequeue (deletion). • Enqueue is done at the front of the queue and dequeue is done at the end of the queue. The elements in a queue are arranged sequentially and hence queues are said to be linear data structures. • A queue is a container that holds data. There are two types of Queue, FIFO, and LIFO. • For a FIFO (First in First out Queue), the element that goes first will be the first to come out. • For a LIFO (Last in First out Queue), the element that is entered last will be the first to come out. • An item in a queue is added using the Enqueue(item) method. ▪ To remove an item, Dequeue () method is used. 8.4 KEYWORDS • FIFO: first in first out • ADT: Abstract Data Type • Rear: add the element into the queue • Front: remove the element from the queue • Enqueue: Add an element to the end of the queue • Dequeue: Remove an element from the front of the queue • IsEmpty: Check if the queue is empty • IsFull: Check if the queue is full • Peek: Get the value of the front of the queue without removing it 8.5 LEARNING ACTIVITY 1. Think about how to implement the double-ended queue. ___________________________________________________________________________ ____________________________________________________________________ 8.6 UNIT END QUESTIONS A. Descriptive Questions Short Questions 106 CU IDOL SELF LEARNING MATERIAL (SLM)

1. What is a queue? 2. Define enqueue and dequeue 3. Why queue is called FIFO list? 4. Write an algorithm to check isempty() operation 5. List out any two ADT operation in the queue. Long Questions 1. Define Queue ADT. How is the queue implemented? Give an example. 2. Explain in details about Queue Operation 3. How does queue work? Explain the algorithm for inserting and deleting from a queue. 4. Explain the representation of the queue. 5. Write an algorithm to perform basic operations in the queue. B. Multiple choice Questions 1. A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is known as _____________ a. Queue b. Stack c. Tree d. Linked list 2. The data structure required for Breadth-First Traversal on a graph is? a. Stack b. Array c. Queue d. Tree 3. A queue follows __________ a. FIFO (First In First Out) principle b. LIFO (Last In First Out) principle c. Ordered array d. Linear tree 107 CU IDOL SELF LEARNING MATERIAL (SLM)

4. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed? a. ABCD b. DCBA c. DCAB d. ABDC 5. How many stacks are needed to implement a queue? Consider the situation where no other data structure like arrays, a linked list is available to you. a. 1 b. 2 c. 3 d. 4 Answer 1. (a) 2. (c) 3. (a) 4. (a) 5. (b) 8.7 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 108 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 9: MEMORY REPRESENTATION Structure 9.0 Learning Objective 9.1 Memory Representation Using Arrays 9.2 Memory Representation Using Linked List 9.3 Types of Queues 9.4 Applications of Queue 9.5 Summary 9.6 Keywords 9.7 Learning activity 9.8 Unit End Questions 9.9 References 9.0 LEARNING OBJECTIVE After studying this unit, the student will be able to • Analyse the representation of a queue using arrays & linked list. • Describe the concepts of various operations in the linked list. • Distinguish between the different types of queues and their uses. 9.1 MEMORY REPRESENTATION USING ARRAYS Queue ADT: A queue may be a Linear arrangement that permits the subsequent operations: 1. Enqueue: Add a component to the top of the queue 2. Dequeue: Remove a component from the front of the queue 3. IsEmpty: Check if the queue is empty 4. IsFull: Check if the queue is full 5. Peek: Get the worth of the front of the queue without removing it 109 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 9.1: Queue using Array Representation Create Queue: int Queue[size]; int Front=-1; int Rear=-1; Enqueue: Adds a component at the start of the queue. If the queue is full, then it's an overflow. 1. Check if the queue is full. 2. If the queue is full, then print \"Queue overflow\". 3. Else increment Rear by 1. 4. Assign Queue [ Rear ] = data. Example Program: int enqueue (int data) { if (isfull ()) return 0; Rear = Rear + 1; Queue [Rear] = data; return 1; } Dequeue: Deletes a component at the top of the queue. If the queue is empty, then it's an underflow. 1. Check if the queue is empty. 2. If the queue is empty, the print \"Queue underflow\". 110 CU IDOL SELF LEARNING MATERIAL (SLM)

3. Copy the element at the front of the queue to some temporary variable, TEMP = Queue [ Front ]. 4. Increment Front by 1. 5. Print temp and delete it. Example: int dequeue () { if (isempty ()) return 0; int data = Queue [Front]; Front = Front + 1; return data; } Example Program: #include<stdio.h> #include<conio.h> #define SIZE 10 void EnQueue(int); void EeQueue(); void display(); int Queue[SIZE], front = -1, rear = -1; int main() { int value, choice; while(1){ printf(\"\\n\\n***** MENU *****\\n\"); printf(\"1. Insertion\\n2. Deletion\\n3. Display\\n4.Exit\"); printf(\"\\nEnter your choice: \"); 111 CU IDOL SELF LEARNING MATERIAL (SLM)

scanf(\"%d\",&choice); switch(choice){ case 1: printf(\"Enter the value to be insert: \"); scanf(\"%d\",&value); EnQueue(value); break; case 2: DeQueue(); break; case 3: Display(); break; case 4: exit(0); default: printf(\"\\n Try again!!!\"); } } return 0; } void EnQueue(int value){ if(Rear == SIZE-1) printf(\"\\nQueue is Full\"); else{ if(Front == -1) Front = 0; Rear++; Queue[Rear] = value; printf(\"\\nInsertion success\"); } } void DeQueue(){ if(Front == Rear) printf(\"\\nQueue is Empty\"); 112 CU IDOL SELF LEARNING MATERIAL (SLM)

else{ printf(\"\\nDeleted : %d\", Queue[Front]); Front++; if(Front == Rear) Front = Rear = -1; } } void Display(){ if(Rear == -1) printf(\"\\nQueue is Empty\"); else{ int i; printf(\"\\nQueue elements are:\\n\"); for(i=Front; i<=Rear; i++) printf(\"%d\\t\",Queue[i]); } } 9.2 MEMORY REPRESENTATION USING LINKED LIST Queue ADT: The array implementation is incompatible with queue implementations within the application of the large-scale system. The related Linked List implementation of the queue is one among the array implementation alternatives. The storage requirement of linked representation of a queue with n elements is o(n) while the time required for operations is o(1). In a linked queue, each node of the queue consists of two parts i.e. data part and therefore the linked part. Each element of the queue points to its immediate next element within the memory. 113 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 9.2: Queue Using List Representation Create Queue: Struct Node { int data; struct Node * Next; }; struct Node * Front, *Rear; Enqueue: Adds an element at the beginning of the queue. If the queue is full, then it is an overflow. 1. Create a newNode with the given value and set the node's pointer to NULL. 2. Check whether the queue is EMPTY. 3. If it is EMPTY, set FRONT and REAR to newNode. 4. Else, set the pointer of REAR to newNode and make REAR as the newNode. Algorithm: begin procedure EnQueue newNode -> data = data newNode -> next = NULL if ( REAR == NULL) FRONT = REAR = newNode end if else REAR -> next = newNode REAR = newNode end procedure Example: void EnQueue(int data) { 114 CU IDOL SELF LEARNING MATERIAL (SLM)

newNode = (struct node*) malloc(sizeof(struct Node)); newNode -> data = data; newNode -> next = NULL; if(Rear != NULL) { Rear -> next = newNode; Rear = newNode; // Make the new node as REAR } else Front = Rear = newNode; // In a Empty Queue } Dequeue: Deletes an element at the end of the queue. If the queue is empty, then it is an underflow. 1. Check if the queue is EMPTY. 2. If it is EMPTY, then display \"EMPTY QUEUE\" and exit. 3. Else, create a temporary node and set it to FRONT. 4. Make the next node as FRONT and delete the temporary node. Algorithm: begin procedure DeQueue if(FRONT == NULL) print \"EMPTY QUEUE\" and exit. end if else temp = FRONT FRONT = FRONT -> NEXT free(temp) end else end procedure 115 CU IDOL SELF LEARNING MATERIAL (SLM)

Example: int DeQueue() { int data; data = Front -> data; temp = Front; // Copy FRONT to a temporary node Front = Front -> next; // Move FRONT to the next node free(temp); // Delete the temporary node if(Front == NULL) Rear = NULL; return data; } Program: #include <stdio.h> struct Node { int data; struct Node *next; } *Rear,*Front,*temp,*newNode; /* Initialising front and rear in empty list */ void create() { Front = Rear = NULL; } /* Function to insert elements in the queue */ void EnQueue(int data) { newNode = (struct node*) malloc(sizeof(struct Node)); newNode -> data = data; newNode -> Next = NULL; 116 CU IDOL SELF LEARNING MATERIAL (SLM)

if(rear != NULL) { Rear -> Next = newNode; Rear = newNode; // Make the new node as REAR } else Front = Rear = newNode; // In a empty queue, the inserted element becomes FRONT and REAR } /* Function to dequeue elements in a queue */ int DeQueue() { int data; data = Front -> data; temp = Front; // Copy FRONT to a temporary node Front = Front -> next; // Move FRONT to the next node free(temp); // Delete the temporary node if(Front == NULL) Rear = NULL; return data; } /* Function to check if thw queue is empty */ 117 int Empty() { if(Front == NULL) { return 1; } else CU IDOL SELF LEARNING MATERIAL (SLM)

return 0; } /* Function to display elements */ void Display() { if(Empty()) printf(\"\\nEMPTY QUEUE\\n\"); else { temp = Front; printf(\"\\nQUEUE ELEMENTS : \"); while(temp != NULL) { printf(\"%d \",temp -> data); temp = temp -> next; } } } /* Main Function */ int main() { int num,choice; while(1) { printf(\"\\n\\nQUEUE OPERATIONS\\n\\n1.ENQUEUE\\n2.DEQUEUE\\n3.DISPLAY\\n\\n\"); scanf(\"%d\",&choice); switch (choice) { 118 CU IDOL SELF LEARNING MATERIAL (SLM)

case 1: printf(\"\\nEnter item : \"); scanf(\"%d\",&num); EnQueue(num); break; case 2: if(!(Empty())) printf(\"\\nDequeued element : %d\",DeQueue()); break; case 3: Display(); break; default: exit(0); } } return 0; } 9.3 TYPES OF QUEUES Queue in data structure is of the following types 1. Simple Queue 2. Circular Queue 3. Priority Queue 4. Dequeue (Double Ended Queue) Simple Queue The simple queue is a normal queue where insertion takes place at the FRONT of the queue and deletion takes place at the END of the queue. 119 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 9.3: Simple Queue Representation Circular Queue In a circular queue, the last node is connected to the first node. Circular queue is also called as Ring Buffer. Insertion in a circular queue happens at the FRONT and deletion at the END of the queue. Figure 9.4: Circular Queue Representation Priority Queue In a priority queue, the nodes will have some predefined priority. Insertion in a priority queue is performed in the order of arrival of the nodes. The node having the least priority will be the first to be removed from the priority queue. Figure 9.5: Priority Queue Representation 120 CU IDOL SELF LEARNING MATERIAL (SLM)

Dequeue (Doubly Ended Queue) In a Double Ended Queue, insertion and deletion operations can be done at both FRONT and REAR of the queue. Figure 9.6: Dequeue Array Representation 9.4 APPLICATIONS OF QUEUE Queue, as the name suggests is used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn, like in the following scenarios: 1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc. 2. In real life scenario, Call Center phone systems use Queues to hold people calling them in order, until a service representative is free. 3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served 4. Calls to larger companies are generally placed on a queue when all operators are busy 9.5 SUMMARY • In a queue, there are two variables i.e. front and rear, that are implemented in the case of every queue. Front and rear variables point to the position from where insertions and deletions are performed in a queue. • The initial value of the front end queue is -1, which indicates that the queue is empty. • The array implementation cannot be used for large scale applications so we used a linked list. • In a linked queue, each node of the queue consists of two parts i.e. data part and the linked part. Each element of the queue points to its immediate next element in the memory. In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. Types of a queue: 121 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Simple Queue 2. Circular Queue 3. Priority Queue 4. Dequeue (Double Ended Queue) 9.6 KEYWORDS • Enqueue: Add an element to the end of the queue • Dequeue: Remove an element from the front of the queue • IsEmpty: Check if the queue is empty • IsFull: Check if the queue is full • Peek: Get the value of the front of the queue without removing it 9.7 LEARNING ACTIVITY The activity aims to make them realize the limitation of stack & introduces the need of queues. Identify the flaw of stack if used in a scenario where a queue is needed. Let them play an act of shopkeeper & customer. One student may become shopkeeper & the others will be customers. After every 10 seconds a new customer will come & add himself in a stack. The shopkeeper serves the customer once every 15 seconds using the LIFO fashion. Make them realize that in this fashion the one who came first may never get his & turn will be waiting forever. ___________________________________________________________________________ ____________________________________________________________________ 9.8 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What are the basic operations that could be performed on a Queue? 2. What are the limitations of the linear queue? How they can be rectified 3. Write short notes on the application of queues 4. List out any two application of the queue 5. Write short notes on types of the queue. Long Questions 122 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Give one implementation of a priority queue and explain the routines used. 2. Explain the array implementation of Queue ADT. 3. How does queue work? Explain the algorithm for inserting and deleting from a queue. 4. Explain the List implementation of Queue ADT. 5. Write the routines to implement queues using: a. Linked lists b. Arrays B. Multiple choice Questions 1. A normal queue, if implemented using an array of size MAX_SIZE, gets full when? a. Rear = MAX_SIZE – 1 b. Front = (rear + 1)mod MAX_SIZE c. Front = rear + 1 d. Rear = front 2. Which of the following is not the type of queue? a. Ordinary queue b. Single ended queue c. Circular queue d. Priority queue 3. Queues serve major role in ______________ a. Simulation of recursion b. Simulation of arbitrary linked list c. Simulation of limited resource allocation d. Simulation of heap sort 4. Circular Queue is also known as ________ a. Ring Buffer b. Square Buffer c. Rectangle Buffer 123 CU IDOL SELF LEARNING MATERIAL (SLM)

d. Curve Buffer 5. Which of the following is true about the linked list implementation of the queue? a. In a push operation, if new nodes are inserted at the beginning of the linked list, then in pop operation, nodes must be removed from the end. b. In a push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning. c. Both of these d. None of these Answer 1. (a) 2. (b) 3. (c) 4. (a) 5. (c) 9.9 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 124 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 10: LINKED LIST Structure 10.0 Learning Objective 10.1 Introduction and representation of the linked list 10.2 Operations: Create, Insertion, Deletion 10.3 Operations: TRAVERSAL, MERGING AND SORTING 10.4 Summary 10.5 Keywords 10.6 Learning activity 10.7 Unit End Questions 10.8 References 10.0 LEARNING OBJECTIVE After studying this unit, the student will be able to • Describe the basics of linked lists • Analyse the representation of linked list • Explain and implement linked list operations and its applications. 10.1 INTRODUCTION AND REPRESENTATION OF LINKED LIST Linked List: Linked List are often defined as a set of objects called nodes that are randomly stored within the memory. A node contains two fields i.e. data stored at that specific address and therefore the pointer which contains the address of subsequent node within the memory. The last node of the list contains the pointer to the null. and therefore, the first node of the list is head. Figure 10.1: linked list representation 125 CU IDOL SELF LEARNING MATERIAL (SLM)

Limitations of array Implementation: 1. The dimensions of the array must be known beforehand before using it within the program. 2. The increasing size of the array may be a time taking process. it's almost impossible to expand the dimensions of the array at run time. 3. All the weather within the array got to be continuously stored within the memory. Inserting a component within the array needs shifting of all its predecessors. Uses of Linked List: 1. The list doesn't get to be within the memory location in any particular order. The node is often located anywhere in memory and connected to make an inventory. This leads to optimum space use. 2. List size is restricted to the memory size and doesn't got to be declared beforehand. 3. An empty node can't be present within the linked list. 4. we will store values of primitive types or objects within the singly linked list. List ADT Operation: 1. Insertion − Adds a component at the start of the list. 2. Deletion − Deletes a component at the start of the list. 3. Display − Displays the entire list. 4. Search − Searches a component using the given key. 10.2 OPERATIONS: CREATE, INSERTION, DELETION Create List: The following steps are used to create a linked List. 1. The primary step of making linked list of n nodes starts from defining node structure. we'd like a custom type to store our data and site of next linked node. Where data is that the data you would like to store in list. *next is pointer to an equivalent structure type. The *next will store location of next node if exists otherwise NULL. 2. Declare a pointer to node type variable to store link of first node of linked list. Say struct node *head. you'll also declare variable of node type alongside node structure definition. 3. Input number of nodes to make from user, store it in some variable say n. 126 CU IDOL SELF LEARNING MATERIAL (SLM)

4. Declare two more helper variable of node type, say struct node *newNode, *temp; 5. If n > 0 then, create our first node i.e. head node. Use dynamic memory allocation to allocate memory for a node. Say head = (struct node*)malloc(size of(struct node));. 6. If there's no memory to allocate for head node i.e. head == NULL. Then print some error message and terminate the program, otherwise move to the below step. 7. input file from user and assign to go using head->data = data;. 8. initially head node points to NULL. Hence, assign head->next = NULL;. 9. Now, we are through with head node we should always move to creation of other nodes. Copy reference of head to another temporary variable, say temp = head;. we'll use temp to store reference of previous node. 10. Allocate memory and assign memory regard to newNode, say newNode = (struct node*)malloc(sizeof(node));. 11. If memory got allocated successfully then read data from user and assign to data section of latest node. Say newNode->data = data;. 12. confirm new node points to NULL. 13. Now link previous node with newly created node i.e. temp->next = newNode;. 14. Make current node as previous node using temp = temp->next;. 15. Repeat step 10-14 for remaining n - 2 other nodes. struct Node Figure 10.2: Singly Linked List { CU IDOL SELF LEARNING MATERIAL (SLM) int data; 127

struct Node *Next; }; Example Program: void create(int x , List L) { struct TmpCell; TmpCell = (struct node *) malloc(sizeof(struct Node)); TmpCell->data = x; TmpCell->Next = NULL if(L == NULL) { L = TmpCell; } else { L->Next = TmpCell; } } List Insertion: Insert Elements to a Linked List. You can add elements to either the beginning, middle or end of the linked list. Insert at the beginning 1. Allocate memory for new node 2. Store data 3. Change next of new node to point to head 4. Change head to point to recently created node Example Program: void InsertAtBegin(int data, List Head) 128 CU IDOL SELF LEARNING MATERIAL (SLM)

{ 129 struct Node *newNode; newNode = malloc(sizeof(struct Node)); newNode->data = data; newNode->Next = Head; Head = newNode; } Insert at the End 1. Allocate memory for new node 2. Store data 3. Traverse to last node 4. Change next of last node to recently created node Example Program: void InsertAtEnd(int data, List Head) { struct Node *newNode; struct Node *temp = head; newNode = malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; while(temp->next != NULL) { temp = temp->next; } temp->next = newNode; } Insert at the Middle 1. Allocate memory and store data for new Node CU IDOL SELF LEARNING MATERIAL (SLM)

2. Traverse to node just before the required position of new node 3. Change next pointers to include new node in between Example Program: void insertAtMiddle(int data, List Head) { struct Node *newNode; newNode = malloc(sizeof(struct Node)); newNode->data = data; struct Node *temp = Head; for(int i=2; i < position; i++) { if(temp->Next != NULL) { temp = temp->Next; } } newNode->Next = temp->Next; temp->Next = newNode; } List Deletion: You can delete data either from the beginning of linked list, end or from a particular position. 1. Delete from beginning 2. Delete from end 3. Delete from middle 1. Delete from beginning Point head to the second node Head = Head->Next; 2. Delete from end • Traverse to second last element • Change its next pointer to null 130 CU IDOL SELF LEARNING MATERIAL (SLM)

struct Node* temp = Head; while(temp->Next->Next!=NULL) { temp = temp->Next; } temp->Next = NULL; 3. Delete from middle • Traverse to element before the element to be deleted • Change next pointers to exclude the node from the chain for(int i=2; i< position; i++) { if(temp->Next!=NULL) { temp = temp->Next; } } temp->Next = temp->Next->Next; 10.3 OPERATIONS: TRAVERSAL, MERGING AND SORTING Traversing a Linked List A connected list may be a linear arrangement that has got to be traversed beginning at the highest and ending at rock bottom . Unlike arrays, where random access is possible, a connected list involves sequential traversal to access its nodes. Traversing a linked list is vital in many applications. for instance, we might want to print an inventory or look for a selected node within the list. Or we might want to perform a complicated operation on the list as we traverse the list. The algorithm for traversing an inventory is fairly trivial. 1. Start with the top of the list. Access the content of the top node if it's not null. 2. Then attend subsequent node (if exists) and access the node information 3. Continue until no more nodes (that is, you've got reached the last node 131 CU IDOL SELF LEARNING MATERIAL (SLM)

Algorithm: 132 begin procedure traverse if(FRONT == NULL) print \"EMPTY list\" and exit. end if else temp = HEAD while temp != NULL { print “List data” temp = temp-> NEXT } end else end procedure Example Program: struct node * Traverse (List Head) { struct Node *temp = Head; printf(\"\\n\\nList elements are - \\n\"); while(temp != NULL) { printf(\"%d --->\",temp->data); temp = temp->Next; } return temp; } CU IDOL SELF LEARNING MATERIAL (SLM)

Merging a Linked List: once you merge two linked list with sorted order follow the below steps; 1. Compare the top of both linked lists. 2. Find the smaller node among the 2 head nodes. the present element are going to be the smaller node among two head nodes. 3. The remainder elements of both lists will appear then. 4. Now run a recursive function with parameters, subsequent node of the smaller element and therefore the other head. 5. The recursive function will return subsequent smaller element linked with remainder of the sorted element. Now point subsequent of current element thereto , i.e., curr_ele- >next=recursivefunction() 6. Handle some corner cases. 7. If both the heads are NULL return null. 8. If one head is null return the opposite. 9. Example Program: struct Node *SortedMerge(struct Node* x, struct Node* y) { if(x == NULL) return y; if(y == NULL) return x; if(x->data < y->data) { x->next = SortedMerge(x->next,y); return x; } else { 133 CU IDOL SELF LEARNING MATERIAL (SLM)

y->next = SortedMerge(x,y->next); return y; } } Sorting a Linked List: sortList() will sort the nodes of the list in ascending order. 1. Define a node current which can point to go . 2. Define another node index which can point to node next to current. 3. Compare data of current and index node. If current's data is bigger than the index's data then, swap the info between them. 4. Current will point to current.next and index will point to index.next. 5. Continue this process until the whole list is sorted. Example Program: void SortList(struct Node *Head) { struct Node *current = Head, *index = NULL; int temp; if(Head == NULL) { return; } else { while(current != NULL) { index = current->Next; while(index != NULL) { 134 CU IDOL SELF LEARNING MATERIAL (SLM)

if(current->data > index->data) { temp = current->data; current->data = index->data; index->data = temp; } index = index->Next; } current = current->Next; } } } 10.4 SUMMARY • In this lesson, we learned how to traverse, append, prepend, insert and delete nodes from a linked list. These operations are quite useful in many practical applications. • In the process of creating and managing slides, we can use the concepts such as inserting and deleting nodes learned in this lesson. Many other applications may require you to think of an abstraction like a list, where the list can be easily maintained. • Linked lists remain one of the widely used concepts in programming applications. More advanced linked list structures like an array of linked lists or linked list of linked lists or multilinked lists can be used to implement applications that require complex data structures. • Insertion is the process of placing a node at a specified position in the linked list. • Deletion is the process of removing an existing node from the linked list. The node can be identified by the occurrence of its value or by its position. • Traversal of a linked list is the process of displaying the entire linked list's contents and retracing back to the source node. • Merge is used to one or more list is combined in a single linked list. 10.5 KEYWORDS • Insertion − Adds an element at the beginning of the list. 135 CU IDOL SELF LEARNING MATERIAL (SLM)

• Deletion − Deletes an element at the beginning of the list. • Display − Displays the complete list. • Search − Searches an element using the given key. 10.6 LEARNING ACTIVITY 1. Swap two adjacent elements by adjusting only the pointers ( not the data) using Singly Linked List ___________________________________________________________________________ ____________________________________________________________________ 10.7 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What is singly linked list? 2. Write the example for Linear and Non-Linear data structure 3. Write the procedure for inserting an element in the list 4. What are the advantages of using a linked list rather than array? 5. What is a linear linked list? Long Questions 1. Write a program to print out the elements of a singly linked list. 2. Explain the Linked list implementation 3. Write algorithms for ADT operations for insert a node to linked list 4. Write algorithm for delete a node from linked list 5. Explain with an example the creation of a linked list, insertion and deletion of nodes, and swapping of any two nodes B. Multiple choice Questions 1. Which of the following is not a disadvantage to the usage of array? a. Fixed size b. There are chances of wastage of memory space if elements inserted in an array are lesser than the allocated size c. Insertion based on position d. Accessing elements at specified positions 136 CU IDOL SELF LEARNING MATERIAL (SLM)

2. What is the functionality of the following code? public void function(Node Node) { if(size == 0) Head = Node; else { Node temp,cur; for(cur=Head;(temp=cur.getNext())!=null;cur=temp); cur.setNext(node); } size++; } a. Inserting a node at the beginning of the list b. Deleting a node at the beginning of the list c. Inserting a node at the end of the list d. Deleting a node at the end of the list 3. Which of these is not an application of a linked list? a. To implement file systems b. For separate chaining in hash-tables c. To implement non-binary trees d. Random Access of elements 4. Which of the following is the advantage of the array data structure? 137 a. Elements of mixed data types can be stored. b. Easier to access the elements in an array c. Index of the first element starts from 1. d. Elements of an array cannot be sorted CU IDOL SELF LEARNING MATERIAL (SLM)

5. What does the following function do for a given Linked List with first node as head? void fun1(struct node* head) { if(head == NULL) return; fun1(head->next); printf(\"%d \", head->data); } a. Prints all nodes of linked lists b. Prints all nodes of linked list in reverse order c. Prints alternate nodes of Linked List d. Prints alternate nodes in reverse order Answer 1. (a) 2. (c) 3. (d) 4. (b) 5. (b) 10.8 REFERENCES Reference Books: • R1 Trembley & Soreson, Introduction to Data Structures Applications, Second Edition, Pearson Education. • R2 A. Tannenbaum, Y. Lanhgsam and A.J. Augenstein, Data Structures Using C++, Prentice Hall of India. Text Books: • T1 Schaum's Outlines Series- Data Structures, Seymour Lipschutz, TMH. • T2 E. Balagarusamy, Data Structure using C/C++, Tata McGraw-Hill Education. Websites: • https://www.geeksforgeeks.org/ • https://www.tutorialspoint.com/ 138 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 11: TYPES OF LINKED LIST Structure 11.0 Learning Objective 11.1 One-way list 11.2 Two-way list 11.3 Circular linked list 11.4 Header linked list 11.5 Summary 11.6 Keywords 11.7 Learning activity 11.8 Unit End Questions 11.9 References 11.0 LEARNING OBJECTIVE After studying this unit, the student will be able to • Describe about the types of linked list and their implementations. • Distinguish between the advantages and disadvantages of using Linked Lists. 11.1 ONE-WAY LIST ONE WAY LIST or SINGLY LINKED LIST: In programmes, it's the foremost widely used linked list. once we mention a linked list, we're talking a few singly linked list. The singly linked list may be a arrangement that's divided into two parts: the info part and therefore the address part, which contains the address of subsequent or successor node. A pointer is another name for the address portion of a node. Suppose we've three nodes, and therefore the addresses of those three nodes are 100, 200 and 300 respectively. The representation of three nodes as a linked list is shown within the figure:11.1. We can observe within the above figure that there are three different nodes having address 100, 200 and 300 respectively. the primary node contains the address of subsequent node, i.e., 200, the second node contains the address of the last node, i.e., 300, and therefore the third node contains the NULL value in its address part because it doesn't point to any node. The pointer that holds the address of the initial node is understood as a head pointer. 139 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 11.1: One Way Linked List Representation The linked list, which is shown within the above diagram, is understood as a singly linked list because it contains only one link. during this list, only forward traversal is possible; we cannot traverse within the backward direction because it has just one link within the list. 1. Each node features a single link to a different node is named a one-way list or Singly Linked List. 2. Singly Linked List doesn't store any pointer any regard to the previous node. 3. Each node stores the contents of the node and a regard to subsequent node within the list. 4. during a singly linked list, the last node features a pointer which indicates that it's the last node. It requires a regard to the primary node to store one linked list. 5. it's two successive nodes linked together linearly and contains the address of subsequent node to be followed. 6. it's successor and predecessor. First node doesn't have predecessor while last node doesn't have successor. Last node has successor reference as NULL. 7. it's only single link for subsequent node. 8. during this sort of linked list, only forward sequential movement is feasible, no direct access is allowed. Figure 11.2: One Way Linked List Node Representation 140 struct Node { CU IDOL SELF LEARNING MATERIAL (SLM)

int data; struct Node *Next; } Advantage: 1. Insertions and Deletions are often done easily. 2. It doesn't need movement of elements for insertion and deletion. 3. It space isn't wasted as we will get space consistent with our requirements. 4. Its size isn't fixed. 5. It are often extended or reduced consistent with requirements. 6. Elements may or might not be stored in consecutive memory available, even then we will store the info in computer. 7. It's less costly. Disadvantage: 1. It requires more room as pointers also are stored with information. 2. Different amount of your time is required to access each element. 3. If we've to travel to a specific element then we've to travel through all those elements that precede that element. 4. We will not traverse it from last & only from the start. 5. It's tough to sort the weather stored within the linear linked list. 11.2 TWO-WAY LIST Two-Way List or Doubly Linked List: The doubly linked list, as its name implies, contains two pointers. The doubly linked list is often defined as a three-part linear data structure: the info part, the address part, and therefore the other two address sections. A doubly linked list, in other words, may be a list of three sections in each node: one data element, a pointer to the previous node, and a pointer to subsequent node. Suppose we've three nodes, and therefore the address of those nodes is 100, 200 and 300, respectively. The representation of those nodes during a doubly-linked list is shown below: 141 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 11.3: Two Way Linked List As we will observe within the above figure, the node during a doubly-linked list has two address parts; one part stores the address of subsequent while the opposite a part of the node stores the previous node's address. The initial node within the doubly linked list has the NULL value within the address part, which provides the address of the previous node. Figure 11.4: Two Way Linked List Node Representation struct Node { int data; struct Node *Next; struct Node *Prev; } Advantages of Doubly Linked List 1. A doubly linked list can be traversed in both forward and backward directions. 2. To delete a node in a singly linked list, the previous node is required, while in doubly linked list, we can get the previous node using previous pointer. 3. It is a very convenient than singly linked list. Doubly linked list maintains the links for bidirectional traversing. Disadvantages of Doubly Linked List 142 CU IDOL SELF LEARNING MATERIAL (SLM)

1. In doubly linked list, each node requires extra space for previous pointer. 2. All operations such as Insert, Delete, Traverse etc. require extra previous pointer to be maintained. 11.3 CIRCULAR LINKED LIST Circular Linked List may be a variation of Linked list during which the primary element points to the last element and therefore the last element points to the primary element. Both Singly Linked List and Doubly Linked List are often made into a circular linked list. Two types of Circular Linked List 1. Singly circular Linked List 2. Double circular linked list Singly Circular Linked List: A singly linked list may be a sort of circular linked list. the sole difference between a singly linked list and a circular linked list is that the last node during a singly linked list doesn't point to the other node, so its relation portion is NULL. Figure 11.5: Singly Circular Linked List Doubly Circular Linked Lis: Circular doubly linked list may be a more complexed sort of arrangement during which a node contain tips that could its previous node also because the next node. Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the primary node of the list. the primary node of the list also contains address of the last node in its previous pointer. 143 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 11.6: Doubly Circular Linked List Because a circular doubly linked list contains three parts in its structure, therefore, it demands more room per node and costlier basic operations. However, a circular doubly linked list provides easy manipulation of the pointers and therefore the searching becomes twice as efficient. Advantages of Circular Linked Lists: 1. Any node is often a start line. we will traverse the entire list by ranging from any point. We just got to stop when the primary visited node is visited again. 2. Useful for implementation of queue. Unlike this implementation, we don’t get to maintain two pointers for front and rear if we use circular linked list. we will maintain a pointer to the last inserted node and front can always be obtained as next of last. 3. Circular lists are useful in applications to repeatedly go round the list. for instance, when multiple applications are running on a PC, it's common for the OS to place the running applications on an inventory then to cycle through them, giving each of them a slice of your time to execute, then making them wait while the CPU is given to a different application. it's convenient for the OS to use a circular list in order that when it reaches the top of the list it can cycle around to the front of the list. 4. Circular Doubly Linked Lists are used for the implementation of advanced data structures like Fibonacci Heap. Disadvantages of a circular linked list: 1. counting on the implementation, inserting at the beginning of the list would require checking out the last node which might be expensive. 2. Finding the top of list and loop control is harder (no NULL's to mark beginning and end) 11.4 HEADER LINKED LIST 144 CU IDOL SELF LEARNING MATERIAL (SLM)

A header node may be a unique node that appears at the highest of an inventory. The header- linked list may be a list that has this type of node. When information aside from that contained in each node is required, this type of list comes in handy. For example, suppose there's an application during which the amount of things during a list is usually calculated. Usually, an inventory is usually traversed to seek out the length of the list. However, if the present length is maintained in a further header node that information are often easily obtained. Types of Header Linked List 1. Grounded Header Linked List 2. Circular Header Linked List Grounded Header Linked List It is an inventory whose last node contains the NULL pointer. within the header linked list the beginning pointer always points to the header node. start -> next = NULL indicates that the grounded header linked list is empty. The operations that are possible on this sort of linked list are Insertion, Deletion, and Traversing. Figure 11.7: Grounded Header Linked List 145 Example Program: CU IDOL SELF LEARNING MATERIAL (SLM)

struct Link* create_header_list(int data) 146 { // Create a new Node struct Link *new_Node, *Node; new_Node = (struct Link*) malloc(sizeof(struct Link)); new_Node->info = data; new_Node->Next = NULL; // If it is the first Node if (start == NULL) { // Initialize the start start = (struct Link*) malloc(sizeof(struct Link)); start->Next = new_Node; } else { // Insert the Node in the end Node = start; while (Node->Next != NULL) { Node = Node->Next; } Node->Next = new_Node; } return start; } Circular Header Linked List CU IDOL SELF LEARNING MATERIAL (SLM)

A list in which last node points back to the header node is called circular linked list. The chains do not indicate first or last nodes. In this case, external pointers provide a frame of reference because last node of a circular linked list does not contain the NULL pointer. The possible operations on this type of linked list are Insertion, Deletion and Traversing. Figure 11.8: Circular Header Linked List 147 Example Program: struct Link* create_header_list(int data) { // Create a new Node struct Link *new_Node, *Node; new_Node = (struct Link*) malloc(sizeof(struct Link)); new_Node->info = data; new_Node->Next = NULL; new_Node->Prev = NULL; // If it is the first Node if (start == NULL) { CU IDOL SELF LEARNING MATERIAL (SLM)

// Initialize the start start = (struct Link*) malloc(sizeof(struct Link)); start->Next = new_Node; start->Prev = new_Node; } else { // Insert the Node in the end Node = start; while (Node->Next != NULL) { Node = Node->Next; } Node->Next = new_Node; new_Node->Prev = Node; } return start; } Applications of Header Linked List 1. In header node, you can maintain count variable which gives number of nodes in the list. You can update header node count member whenever you add /delete any node. It will help in getting list count without traversing in O(1) time. 2. In addition to address of first node you can also store the address of last node. So that if you want to insert node at the rear end you don't have to iterate from the beginning of the list. Also in tcase of DLL(Doubly Linked List) if you want to traverse from rear end it helps. 3. We can also use it to store the pointer to the current node in the linked list which eliminates the need of an external pointer during the traversal of the linked list. 148 CU IDOL SELF LEARNING MATERIAL (SLM)

4. While inserting a new node in the linked list we don't need to check whether start node is null or not because the header node will always exist and we can insert a new node just after that. 11.5 SUMMARY • A one-way linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail). • A two-way Linked List contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the one-way linked list. • Circular Linked List is a variation of the Linked list in which the first element points to the last element and the last element points to the first element. Both Singly Linked List and Doubly Linked List can be made into a circular linked list. • A header node is a special node that is found at the beginning of the list. A list that contains this type of node, is called the header-linked list. This type of list is useful when information other than that found in each node is needed. 11.6 KEYWORDS • Singly-linked list: singly linked list pointer to points only one direction. • Doubly linked list: doubly linked list pointer to points both direction. • Circular linked list: Circular Linked List is a variation of the Linked list in which the first element points to the last element and the last element points to the first element • Header linked list: A header node is a special node that is found at the beginning of the list. A list that contains this type of node, is called the header-linked list. This type of list is useful when information other than that found in each node is needed. 11.7 LEARNING ACTIVITY we want students to realize the need for an organized data structure & make them realize the importance of a list & its useful properties i.e. dynamic increase or decrease in size & insertion at any point with low cost. Define an array of size 10 & fill it with some data. Then ask the students that if there is a need to insert one more element then what can be done? Of course a new array with bigger size will be declared, all the data will be copied in it & new data will be added after that. What if three elements are already added in array (say apple, banana & orange) keeping alphabetical order in mind. Now you want to insert another element “Mango” 149 CU IDOL SELF LEARNING MATERIAL (SLM)

in it. In the case of an array, there is a need to move the entire list of elements one index further that comes after mango and place mango on its place. Moving further with these two activities makes students realize the need of a structure that can increase or decrease its size dynamically & there is always a place to insert data anywhere without the need of disturbing the others. ___________________________________________________________________________ ____________________________________________________________________ 11.8 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. Define one-way linked list? 2. What is a two-way linked list? 3. What is a header linked list? 4. What is meant by circularly linked list? 5. What are the applications of linked list? Long Questions 1. Explain with an example the creation of a linked list, insertion and deletion of nodes, and swapping of any two nodes. 2. What is doubly linked list? Explain the algorithm in detail for inserting a node to the left and deleting a node from the doubly linked list? 3. Explain the Linked list implementation. 4. Write algorithms for ADT operations for insert a node to linked list. 5. Write algorithm for deleting a node from Header Linked List. B. Multiple choice Questions 150 1. How do you insert an element at the beginning of the list? a)public void insertBegin(Node node) { node.setNext(head); head = node; size++; CU IDOL SELF LEARNING MATERIAL (SLM)