83301 - DATA STRUCTURES UNIT I- LIST Abstract Data Types (ADTs) - List ADT - Array-based implementation — Linked list implementation — Singly linked lists — Circularly linked lists — Doubly-linked lists — Applications of lists — Polynomial ADT — Radix Sort - Multilists. A collection of facts, concepts, figures, observations, occurrences or instructions in a formalized manner, ‘The meaning that is currently assigned to data by means of the conventions applied to those data (i.e. processed data) Record Collection of related fields. Data type Set of elements that share common set of properties used to solve a program. Data Structure is the way of organizing, storing, and retrieving data and their relationship with each other. A data structure is a data organization, management, and storage format that enables efficient access and modification.More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, ice, it is an algebraic structure about data. * Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by a pointer. «Thus, the array and record data structures are based on computing the addresses of data items with arithmetic operations Q istics of. 1 It depicts the logical representation of data in computer memory. 2. It represents the logical relationship between the various data elements. Ithelps in efficient manipulation of stored data elements. 4. It allows the programs to process the data in an efficient manner2. Insertion Insertion can be defined as the process of adding the elements to the data structure at any location. If the size of data structure is n then we can only insert n-1 data elements into it. 3. Deletion The process of removing an element from the data structure is called Deletion, We can delete an element from the data structure at any random location. © Ifwe try to delete an element from an empty data structure then underflow occurs. 4. Searching The process of finding the location of an element within the data structure is called Searching. There are two algorithms to perform searching, Linear Search and Binary Search. We will discuss each one of them later in this tutorial. 5. Sorting The process of arranging the data structure in a specific order is known as Sorting. There are many algorithms that can be used to perform sorting, for example, insertion sort, selection sort, bubble sort, ete. 6. Merging When two lists List A and List B of size M and N respectively, of similar type of elements, clubbed or joined to produce the third list, List C of size (M+N), then this process is called merging eerie Cone een Integer Arrays Pointer ns oa Primary Data Structures/Primitive Data Structures Primitive data structures include all the fundamental data structures that can be directly manipulated by machine-level instructions, Some of the common primitive data structures include integer, character, real, boolean eteGraph A Graph is a non linear data structure. It is often viewed as a generalization of the tree structure. It contains two main components vertices (nodes) and edges. Two nodes are connected via an edge. The graph is used to represent many computer applications, like - a computer network, in which nodes are network workstations and the edges are the network connections. Tree Tree is a hierarchical relationship between various elements. It is a set of one or more nodes and nodes are connected by an edge. Each node contains some value. The node is represented by a circle and edge lives connecting these nodes. Tree is a non linear data structure, which is very flexible, versatile and widely used. The field of computer science will address the task of storing, accessing & manipulating data Data structures are widely applied in the following areas: + Compiler design + Operating system + Statistical analysis package + DBMS. + Numerical analysis + Simulation + Artificial intelligence Graphies + System sofiware design, Robotics etc., BSTRACT DATA TYPES (ADTS An abstract Data type (ADT) is defined as a mathematical model with a collection of operations defined on that model. Set of integers, together with the operations of union, intersection and set difference form a example of an ADT. An ADT consists of data together with functions that operate on that data. The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view. The process of providing only the essentials and hiding the details is known as abstraction.7. Makeempty- Makes the list empty. Implementation of list ADT 1 Array based Implementation 2. Linked List based implementation ARRAY IMPLEMENTATION OF LIST Array is a collection of specific number of same type of data stored in consecutive memory locations. Array is a static data structure i.e., the memory should be allocated in advance and the size is fixed. This will waste the memory space when used space is less than the allocated space, Insertion and Deletion operation are expensive as it requires more data movements. Find and Print list operations takes constant time. 2%} 1 | 30 | 4] so | oo Afo] Atl] A] AL] AL] ALS] The position of each element is given by an index from 0 to n-1, where n is the number of elements. The element with the index can be accessed in constant time (ie) the time to access does not depend on the size of the lis. The time taken to add an element at the end of the list does not depend on the size of the list. But the time taken to add an element at any other point in the list depends on the size of the list ue. So the additions near the because the subsequent elements must be shifted to next index start of the list take longer time than the additions near the middle or end. imilarly when an element is removed, subsequent elements must be shifted to the previous index value. So removals near the start of the list take longer time than removals near the middle or end of the list. Array Representation + Element — Each item stored in an array is called an element,Ifn=6, the output of creation is as follows list(6] Insert Operation Insert operation is to insert one or more data elements into an array. Based on the requirement, a new element can be added at the beginning, end, or any given index of array. Inserting the element in the last position of an array is easy. But inserting the element at a particular positionin an array is quite difficult since it involves all the subsequent elements to be shifted one position to the right. 20 | 10 | 30 | 40] so | oo Alo) Af] A] AB] AG) ALS] Routine to insert an clement in the array: void Insert( ) { int i,data,pos; printf{"\nEnter the data to be inserted:\t"); seanf("%d",Sedata); printf{"\nEnter the position at which element to be inserted:\t"); scanf("%d" pos); if (pos==n) printf (“Array overflow”); fori =nel 5 i list{i+1] = list{i]; ist{plos-1] = data; nen+l; Display; } posel sis) Consider an array with 5 clements [ max elements = 10 ]Consider an array with 5 elements [ max element 10 20 30 40 50 If data 20 is to be deleted from the array, then 30 has to be moved to data 20 position, 40 has to be moved to data 30 position and 50 has to be moved to data 40 position IN IN LN 10 20 30 40 50 After this 3 data movements, data 20 is deleted from the 2™ position of the array. 10 30 40 50 Display Operation/Traversing a list Traversal is. the process of visiting the elements in a array Display( ) operation is used to display all the elements stored in the list. The elements are storedfrom the index 0 to n - 1. Using a for loop, the elements in the list are viewed Routine to traverse/display elements of the array void display( ) { inti printf("\n**Elements in the array**\n" for(i=0;i%d" (i+1),element{i]); break; case 4: if(top==LIST_SIZE-1) { print{{"\n Linear List is Full:"); ){ printf("\n Linear List is Empty:"); break; } printf("\n Deleted Data-->Element :%d" element{0)); top for Osi<=topsit+) element{i]=element{i+1]; break; case 8: if(top—1) printf("\n Linear List is Empty:"); else printf("\n Deleted Data—>Element :%d",element{top~]); break; case 9: iftop=—-1) { printf("\n Linear List is Empty:"); break; } printf("\n Enter the Element for Deletion :"); scanft"%d",Sedeldata); found-0; for(i=0;i<=top;i++) iffelement{i]=deldata) { found=1; printi("\n Deleted data—>Element :%d"element{i]); top. for(i=ij<-top;i+4) element{j]=clement{j+1]; break; } if(found==0) printf("\n Element %d Not Found ",deldata); break; default: free(element); printf("\n End Of Run Of Your Program........."); exit(0); } 3 3Element[1Jis—>100 Element[2]is—>200 Element[3]is—>300 Element[4]is—>400 Element[S]is>500 basic Operations in a Linear List. 1.Create New List 2.Modify List 3.View List 4.Insert First S.Insert Last 6.Insert Middle 7.Delete First 8.Delete Last 9.Delete Middle Enter the Choice | to 10:4 Enter the Element:10 basic Operations in a Linear List... 1.Create New List 2.Modify List 3.View List 4JInsert First S.Insert Last_ 6.Insert Middle 7 Delete First _8.Delete Last 9,Delete Middle Enter the Choice I to 10:3 Element[1Jis->10 Element[2]is—>100 Element{3]is>200 Element{4]is-->300 Element{S]is-->400 Element{6]is->500 basic Operations in a Linear List 1.Create New List 2.Modify List 3.View List 4.Insert First S.lnsert Last 6.Insert Middle 7.Delete First __8.Delete Last 9.Delete Middle Enter the Choice | to 10 : 6 Enter the Element after which the insertion is to be made:200 Enter the Element :250 basic Operations in a Linear List. 1.Create New List 2.Modify List 3.View List 4Insert First S.lnsert Last 6.Insert Middle 7.Delete First _8.Delete Last 9.Delete Middle Enter the Choice I to 10:3 Element[|Jis—>10 Element Element: Element [: is: 1 2} 3) 4) Sis. Element| I af i Hi I* This fixing of the size beforehand usually results in overestimation of size which means wwe tend to usually waste space rather than have program run out. ‘+ Anvarray store its nodes in consecutive memory locations. ‘* __ Insertion and deletion operation in array are expensive. Since insertion is performed by pushing the entire array one position down and deletion is performed by shifting the entire array one position up. ‘* The deletion and insertion of elements into the list is slow since it involves shifting of elements, It also means that data must be added to the end of the list for insertion and deletion to be efficient. If insertion and deletion is towards the front of the list, all other elements must shuffle down. This is slow and inefficient. This inefficiency is even more pronounced when the size of the list is large. Arrays are suitable for - Randomly accessing any element. ~ Searching the list for a particular value ~ Inserting or deleting an element at the end. Applications of arrays Arrays are particularly used in programs that require storing large collection of similar type data elements, LINKED LIST BASED IMPLEMENTATION A Linked list is an ordered collection of elements, Each element in the list is referred as a node.Fach node contains two fields namely, Data field-The data field contains the actual data of the elements to be stored in the list, Next field- The next field contains the address of the next node in the list, DATA | NEXT Linked list can be visualized as a chain of nodes, where every node points to the next node A Linked list node Head Next Next Next Data Items Data tems Data tems tT NULL Advantages of Linked List 1 Linked lists are dynamic data structures - The size is not fixed. They canConsider a list A having n nodes and B with m nodes. Then the operation concatenation will place the Ist node of B in the (n+1) the node in A, After concatenation A will contain (name) nodes, Types of linked list, Singly Linked list or Linear list or One-way list Doubly linked list or Two-way list Circular linked list Doubly circular linked list BeNS Dynamic allocation The process of allocating memory to the variables during execution of the program or at run time is known as dynamic memory allocation, C language has four library routines which allow this function. Dynamic memory allocation gives best performance in situations in which we do not know memory requirements in advance. C provides four library routines to automatically allocate ‘memory at the run time, ‘Memory allocation/de-allocation functions Function | Task malloc() |Allocates memory and returns a pointer to the first byte of allo- cated space calloc() |Allocates space for an array of elements, initializes them to zero and returns a pointer to the menory free() | Frees previously allocated menory realloc() |Alters the size of previously allocated menory To use dynamic memory allocation functions, you must include the header file stdlib.h. malloc() The malloc function reserves a block of memory of specified size and returns a pointer of type void. This means that we can assign it to any type of pointer. The general syntax of malloc() is ptr =(cast-type*)malloc(byte-size); where ptr is a pointer of type cast-type. malloc() returns a pointer (of east type) to an area ofmemory with size byte-size. calloc(): calloc() function is another function that reserves memory at the run time. It is normally used to request multiple blocks of storage each of the same size and then sets all bytes to zero, calloc()eS mn List The primitive operations performed on the linked list are as follows 1. Creation This operation is used to create a linked list. Once a linked list is created with one node, insertion operation can be used to add more elements in a node, 2. Insertion- This operation is used to insert a new node at any specified location in the linked list. A new node may be inserted, . At the beginning of the linked list, . At the end of the linked list, . At any specified position in between in a linked list. 3.Deletion- This operation is used to delete an item (or node) from the linked list. A node may be deleted from the, . Beginning of a linked list, . End of a linked list, . Specified location of the linked list. 4. Traversing - It is the process of going through all the nodes from one end to another end of a linked list, In a singly linked list we can visit the nodes only from left to right (forward traversing). But in doubly linked list forward and backward travel ig is possible 5. Searching- It is the process finding a specified node in a linked list. 6. Concatenation- It is the process of appending the second list to the end of the first list. Consider a list A having n nodes and B with m nodes. Then the operation coneatenation will place the Ist node of B in the (n+1) the node in A. After concatenation A will contain (name) nodes, Insertion Before we implement actual operations, first we need to set up an empty list. First, perform the following steps before implementing actual operations. + Step 1 - Include all the header files which are used in the program,L Newnode Before creation ‘Affer creation: Creating a linked list b. Inserting a node to the front of list, c. Inserting a node in the middle i = Newnade Newnode Before insertion After insertion Insertion at the beginning ¢. Inserting a node in the middle i Newnode Before insertion After insertion Insertion in the middle d. Inserting a node to the end of listDeleting a Specific Node from the list We can use the following steps to delete a specific node from the single linked list. + Step 1 - Check whether list is Empty (head == NULL) + Step 2 - If it is Empty then, display ‘List is Empty terminate the function. + Step 3 -If it is Not Empty then, define two Node pointers 'temp1' and ‘temp2' and initialize ‘temp!’ with head. + Step 4- Keep moving the temp1 until it reaches to the exact node to be deleted or to the last node. And every time set temp? = temp!" before moving the ‘tempI’ to its next node. + Step 5 - If it is reached to the last node then display ‘Given node not found in the list! Deletion not possible!!!". And terminate the function. Step 6 - If it is reached to the exact node which we want to del list is having only one node or not + Step 7 -If list has only one node and that is the node to be deleted, then set head = NULL and delete temp! (free(temp1)). + Step 8 - If list contains multiple nodes, then check whether templ is the first node in the list (temp == head). + Step 9 - If temp1 is the first node then move the head to the next node (head = head > next) and delete temp! + Step 10 - If templ is not first node then check whether it is last node in the list (temp1 — next = NULL). + Step 11 -Iftemptis last node then settemp2 — next = NULL and delete temp! (free(temp!)). + Step 12 - If temp1 is not first node and not last node then set temp2 —> next = temp —+ next and delete temp! (free(temp!)). Deletion is not possible’ and , then check whether a.Deleting a node to the front of list B= BeBe Bo Before deleting first node (10) Pe = Be Be After deleting first node (10) b. Deleting the middle nodeallocated, whenever it is required and it is de- allocated whenever it is not needed. Data is stored in non-contiguous memory blocks. . Insertion and deletion of elements are easier and efficient, . Provides flexibility. No need to shift elements of a linked list to make room for a new element or to delete an element. Disadvantages of Linked List More memory - Needs space for pointer (link field). Accessing arbitrary element is time consuming. Only sequential search is supported not binary search, DOUBLY-LINKED LIST Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, cither forward and backward. A doubly linked list is a linked list in which each node has three fields namely Data, Next, Prev. . Data-This field stores the value of the element . Next-This field points to the successor node in the list ‘© Prev-This field points to the predecessor node in the list, Next Next —7e | & Tu "The PREV field of the first node and the NEXT field of the last node will contain NULL. + The PREV field is used to store the address of the preceding node, which enables us to traverse the list in the backward direction. + A doubly linked list provides the ease to manipulate the elements of the list as it maintains pointers to nodes in both the directions (forward and backward). Doubly Linked Lists-Declaration{ struct node *new_node; int num; printf("\n Enter the data : "); scanf("%d", &num); new_node = (struct node *)malloc(sizeofistruct node)); new_node => data = num; start > prev = new_node; new_node > next = start; new_node -> prev = NULL; start = new_node; retum start; } Inserting a New Node in a Doubly Linked List In this section, we will discuss how a new node is added into an already existing doubly 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. Anscrting a Node at the Beginning of a Doubly Linked Algorithm to insert a new node at the beginning In Step 1, we first check whether memory is available for the new node. If the free memory has exhausted, then an OVERFLOW message is printed . Otherwise, if free memory cell is available, then we allocate space for the new node. Set its DATA part with the given VAL and the NEXT part is initialized with the address of the first node of the list, which is stored in START. . Now, since the new node is added as the first node of the list, it will now be known as the START node, that is, the START pointer variable will now hold the address of NEW_NODE. Inserting a Node at the end of a Doubly Linked List Suppose we want to add a new node with data 9 as the last node of the list. Then the following changes will be done in the linked list [= A= = = ETE ke memory for the new node and initialize its DATA part to 9 and its Pointer variable PTR and aake it point to the first node of the list. Move PTR so that i€ points to the last node of the list. Add the new node after the rose pointed by PTR. START rRInserting a Node Before a Given Node in a Doubly Linked List Consider the doubly linked list shown in Fig. Suppose we want to add a new node with value 9 before the node containing 3. Before discussing the changes that will be done in the linked list. . In Step 1, we first check whether memory is available for the new node. . In Step 5, we take a pointer variable PTR and initialize it with START. . ‘That is, PTR now points to the first node of the linked list. . In the while loop, we traverse through the linked list to reach the node that has its value equal to NUM. . We need to reach this node because the new node will be inserted before this node. . ‘Once we reach this node, we change the NEXT and PREV fields in such a way that the new node is inserted before the desired node. ra z aL elie 2x Stan Allocate memory for the new node and initialize 4ts DATA part to 9. Take a pointer variable PTR and make it point to the first node of the list. x [a z 3 4 2[x ‘to the value before Add-the new node in bet ing se xls z 3 Ts tLe PT START struct node *insert_before(struet node *start) { struct node *new_node, *ptr; int num, val; printi("\n Enter the data : scanft"%d", &num);{ struct node *ptr; pir = start; start = start > next; start > prev = NULL; free(ptr); retum start; t Deleting the Last Node from a Doubly Linked List Consider the doubly linked list shown in Fig. Suppose we want to delete the last node from the linked list, then the following changes will be done in the linked list. xl PLB et it Rett et [el eet pel« START Take a pointer variable PTR that points to the first node of the list. xa eA BletEletrPe ele Pir START, PTR Nove PTR so that it now points to the last node of the list. xal et Ble El etPleet ete Pk START PTR Free the space occupied by the node pointed by PTR and store NULL in NEXT field of its preceding node. xa] et bPletEl etree ike START Algorithm to delete the last node of a doubly linked list In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. The while loop traverses through the list to reach the last node. Once we reach the last node, we can also access the second last node by taking its address from the PREV field of the last node. Po delete the last node, we simply have to set the next field of second last node to NULL, so that it now becomes the (new) last node of the linked list. The memory of the previous last node is freed and returned to the free pool.int val; printf("\n Enter the value after which the node has to deleted : "); seanf"%d", &val); ptr = start; while(ptr > data != val) pir = ptr-> next; temp = ptr > next; ptr > next = temp -> next; temp > next > prev = ptr; free(temp); return start; 1g an clement: (int x List L) { Position p, temp; P=Find(x,L); if(PL>next) temp=L; L->next=temp->next; temp->next->prev=L; free(temp); elseif{ IsLast( p, { temp =p; p> prev > next = NULL; free(temp); } Else { temp =p; p> prev > next = p > next; p> next > prev =p > prev; free(temp); } » _ Routine to display the elements in the list: void Display( List L) { P=L-> next; while (p != NULL)Why Circular? Ina singly linked list, for accessing any node of the linked list, we start traversing from the first node. If we are at any node in the middle of the list, then it is not possible to access nodes that precede the given node, This problem can be solved by slightly altering the structure of a singly linked list, In a singly linked list, the next part (pointer to next node) is NULL. If we utilize this link to point to the first node, then we can reach the preceding nodes. ‘Types of CLL CLL can be implemented as circular singly linked list and circular doubly linked list The circular singly liked list has no beginning and no ending Hei Advantages of Circular iked is. 1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again. 2) Useful for implementation of queue. Unlike this implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can 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 around the list. For example, when multiple applications are runing on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list. 4) Circular Doubly Linked Lists are used for implementation of advanced data structures. like Fibonacci Heap, Circular linked list are mostly used in task maintenance in operating systems. There are many examples where circular linked list are being used in computer science including browser surfing where a record of pages visited in the past by the user, is maintained in the form of. circular linked lists and can be accessed again on clicking the previous button,3, Inserting At Specific location in the list Before we implement actual operations, first we need to setup empty list. First perform the following steps before implementing actual operations. * 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 LINSERTION AT THE BEGINNING OF THE LIST void insertAtBeginning(int value) { struct Node *newNod newNode = (struct Node*)malloc(sizeof{struet Node)); newNode -> data = value; if(head = NULL) newNode -> next = head; } else t struct Node *temp = head; while(temp -> next != head) temp = temp -> next; newNode -> next = head; head = newNode; temp -> next = head; printf("\nInsertion success!!!"); EXAMPLE Step 1: Assume linked list is empty and hence Head=Null} else { struct Node *temp = head; while(temp > next != head) temp = temp > next; temp -> next = newNode; newNode => nex‘ id; 3 printf("\nlnsertion success!!!"); } Example Before Insertion e »le After Insertion = =Le ‘Le fe Le 3, INSERTION AT THE SPECIFIC LOCATION OF THE LIST void insertA fter(int value, int location) { struct Node *newNode; newNode ~ (struct Node*)malloc(sizeoftstruct Node)); newNode -> data = value; iffhead == NULL) { head ~ newNode; newNode > next = head; 3 else { struct Node *temp = head; while(temp > data != location) { if(temp -> next == head) {1, Deleting from Beginning of the list void deleteBeginning() t it—head = NULL) printf("List is Empty!!! Deletion not possible!!!"); else { struct Node *temp = head; if(temp > next = head) { head = NULL; free(temp); } else{ head = head -> next; free(temp); } printf("\nDeletion success } } Example anor Ratode co) Le pel a [owe = ae ao ‘ G0] fost=[a_ fom} += [=] +f == 2. Deleting from end of the list void deleteEnd()Remove Last Node wt LO Teoble [orpole [ope [= fos 700 “a0 f= * hare plevious eae te Revove Lasitlode 9 Hea 4050, aL | 4877 | 22 ail! jay “4800 450 ae7 3. Deleting from specific location of the list void deleteSpecific(int delValue) { iff head == NULL) printf("List is Empty!!! Deletion not possible!!!"); else { struct Node *temp! = head, temp2; while(temp! -> data != delValue) { if(temp! -> next = head) t printf("\nGiven node is not found in the list!!1"); goto FuctionEnd; i else { temp2 = temp]; temp = temp] > next; t } if{temp! -> next = head){ head = NULL; free(temp!); } else{ if(temp! = head) { temp2 = head; while(temp2 -> next != head) temp2 = temp2 -> next; head = head > next;‘start Circular Doubly Linked List, Due to the fact that a circular doubly linked list contains three parts in its structure therefore, it demands more space per node and mote expensive basic operations. However, a circular doubly linked list provides easy manipulation of the pointers and the searching becomes twice as efficient, Memory Management of Circular Doubly linked list The following figure shows the way in which the memory is allocated for a circular doubly linked list. The variable head contains the address of the first element of the list i.e. I hence the starting node of the list contains data A is stored at address 1, Since, each node of the list is supposed to have three parts therefore, the starting node of the list contains address of the last node i.e. 8 and the next node i.e. 4. The last node of the list that is stored at address 8 and containing data as 6, contains address of the first node of the list as shown in the image ie. 1 In circular doubly linked list, the last node is identified by the address of the first node which is stored in the next part of the last node therefore the node which contains the address of the first node, is actually the last node of the list.Newnode(w void insertEnd(struct Node** start, int value) { 111 the list is empty, create a single node 11 circular and doubly list if (+start = NULL) { struct Node* new_node = new Node; new_node->data = value; new_node->next ~ new_node->prev ~ new_node; start = new_node; return; 2.Insertion at the beginning of the list There are two scenario of inserting a node in circular doubly linked list at beginning. Either the list is empty or it contains more than one element in the list. Allocate the memory sp: for the new node ptr by using the following statement. 1, ptr= (struct node *)malloc(sizeof{struct node); In the first case, the condition head == NULL becomes true therefore, the node will be added as the first node in the list, The next and the previous pointer of this newly added node will point to itself only. This can be done by using the following statement. L head = ptr; 2 ptr -> next = head; 3 ptr-> prev = head;New node(T) start CD “Seceneco a =| ae al _ = Insertion into cteuar doubly linked list at beginning void insertBegin(struct Node** start, int value) { Pointer points to last Node struct Node *last = (*start)->prev; struct Node* new_node = new Node; new_node->data = value; // Inserting the data setting up previous and next of new node new_node->next = *sta new_node->prev ~ last; {/ Update next and previous pointers of start fH and last. last->next = (*start)->prev = new_node; {/ Update start pointer *start = new_node;The node which is to be deleted can be the only node present in the linked list. In this case, the condition head — next deleted. head will become true, therefore the list needs to be completely It can be simply done by assigning head pointer of the list to null and free the head pointer. 1. head = NULL 2 free(head); in the second scenario, the list contains more than one clement in the list, therefore the condition head — next == head will become false. Now, reach the last node of the list and make a few pointer adjustments there. Run a while loop for this purpose 1, temp =head; 2 while(temp > next != head) 3, { 4 temp = temp -> next; 5. 3 Now, temp will point to the last node of the list. The first node of the list i.e. pointed by head pointer, will need to be deleted. Therefore the last node must contain the address of the node that is pointed by the next pointer of the existing head node. Use the following statement for this purpose. 1. temp ->next = head > next; The new head node i.e. next of existing head node must also point to the last node of the list through its previous pointer. Use the following statement for this purpose. 1. head > next > prev =temp; Now, free the head pointer and the make its next pointer, the new head node of the list. 1, free(head); 2 head = temp -> next; in this way, a node is deleted at the beginning from a circular doubly linked list.POLYNOMIAL MANIPULATION A polynomial can be represented in an array or in a linked list by simply storing the coefficient and exponent of each term. However, for any polynomial operation, such as addition or multiplication of polynomials, you will find that the linked list representation is easier to deal with. What is a polynomial A polynomial p(x) is the expression in variable x which is in the form (axn + bxnel + .... + ict k), where a, b, ¢ ...., k fall in the category of real numbers and 'n' is non negative integer, which is called the degree of polynomial. ‘An essential characteristic of the polynomial is that each term in the polynomial expression consists of two parts: one is the coefficient other is the exponent Ex: 10x2 + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value Points to keep in Mind while working with Polynomials: The sign of cach coefficient and exponent is stored within the coefficient and the exponent itself Additional terms having equal exponent is possible one The storage allocation for each term in the polynomial must be done in ascending and descending order of their exponent rst of all note that in a polynomial all the terms may not be present, especially if it is going to be a very high order polynomial. Consider, Sx!?+ 2x? + 4x7+ 6x5 +x? + 12x. Now this 12th order polynomial does not have all the 13 terms (including the constant term). It would be very easy to represent the polynomial using a linked list structure, where each node can hold information pertaining to a single term of the polynomial Each node will need to store the variable x, the exponent and the coefficient for each term. It often does not matter whether the polynomial is in x or y. This information may not be very crucial for the intended operations on the polynomial. Thus we need to define a node structure to hold two integers , viz. exp and coff. Compare this representation with storing the same polynomial using an array structure. In the array we have to have keep a slot for each exponent of x, thus if we have a polynomial of order 50 but containing just 6 terms, then a large number of entries will be zero in the array. You will also see that it would be also easy to manipulate a pair of polynomials if they are{ poe9-pt oa: p3 > coff'=pl -> coff, append(p3, phead3); /* now move to the next term in list 1* pl=pl next; } 1 * if p2 exponent tums out to be higher then make p3 same as p2 and append to final list*/ while (pl ->exp < p2 > exp) { p3 >exp = p2 >e xp; p3 >coff= p2 -> coff; append(p3, phead3); p2=p2 > next; } /* now consider the possibility that both exponents are same , then we must add the coefficients to get the term for the final list * while (pl->exp = p2 > exp) (sone plo-on: p3->coff = pl>coff'+ p2-> coff; append(p3, phead3) ; pl =pl->next ; p2=p2->next ; } 1 now consider th possiliy that 2 gts exhase , dt at ems remaining only in list. So all those terms have to be appended to end of list3. However, you do not have to do it term by term, as pl is already pointing to remaining terms, so simply append the pointer pl to phead3 */ if (pl != NULL) append (p1,phead3) ; else append (p2, phead3); Now, you can implement the algorithm in C, and maybe make it more efficient.Repres (ing using arr The simple way is to represent a polynomial with degree 'n’ and store the coefficient of n+] terms of the polynomial in the array. So every array element will consist of two values: Coefficient and Exponent, " 2 3 5 8 COEFFICIENT ARR, EXPONENTS Representing using linked list A polynomial can be thought of as an ordered list of non zero terms. Each non zero term is a two-tuple which holds two pieces of information: The exponent part The coefficient part Syntax: struct polynomial int coefficient int exponent; struct polynomial *next + Input: Ist number = 5x*2 + 4x1 + 2x%0 2nd number = 5x1 + 5x0 Output: 5x72 + 9x1 + 7x%0 Input: Ast number = 5x3 + 4x*2 + 2x0 2nd number = 5x*1 + 5x“0 Output: $x°3 + 4x42 + $x*1 + 7x40Step 3 furthermore, we compare the exponents of the current terms again ‘expo(p)-expo(q) therefore, we add the coefficients of these two terms and link this to the resultant linked list and advance the pointers to their next. you will notice that nodes Q reaches the NULL and P points the last node Step 4 In the above figure, you will notice that there is no node in the second polynomial to compare with. you can understand in a better way after seeing the figure, so the last node in the first polynomial is added to the end of the resultant linked list. the next below figure is the output which comes Polynomials Addition of two polynomials Cooma zola ao] 0 Timo iy fools * sol2 |e wo] Step 5: therefore, the display the resultant linked list, the resultant linked list is the pointed to by the pointer ft Creation of Polynomial: poly create(poly *head, poly *newnode)All Operations (Tnsertion, Deletion, Merge, Traversal) + Tnsertion * Deletion + Merge two sorted linked lists + Traversal + Assume, that we have a list with some nodes. Traversal is the very basie ‘operation, which presents as a prt in almost every operation on a singly-linked list + For instance, algorithm may traverse a singly-linked list to find a value, find a position for insertion, etc, For a singly-linked list, only forward direction traversal is possible. ‘Traversal algorithm + Beginning from the head + check, if the end of list hasn't been reached yet; + do some actions with the current node, which is specific for particular algorithm: © current node becomes previous and next node becomes current. Go to the step 1 Polynomial Manipulation - Merge, Traversal The linked list data structure supports the following operations. We assume that the location of the first node is given by the special vairable called head. x Insert(x, a) : Insert x next to element a in the list. x Remove(x): Remove element x from the list. x Find(x) : Find and return, if present, the location of element x. x Print(): Print the contents of the list. Using C style pointers, The following is the pseudocode for the operations. We assume that we have a structure such as: Struct node { int value; struct node *next; } With the above definition ofa structure, let us implement the above operations Given a linked list via the head pointe Jet us first implement the operations Find and+ Read two polynomials. + Add them. + Display the resultant polynomial. Addition of Polynomials: void add() { poly *ptrl, *ptr2, *newnode; ptrl=listl; pir2=list2; while(ptrl!=NULL && ptr2!= NULL) { newnoie malic ply if(ptrl->power=ptr2->power) { newnode->coeff = ptrl >coeff + ptr2->coeff, newnode->power=ptrl>power; newnode->next-NULL; list3create(list3.newnode); ptrl=ptr->next; ptr2=ptr2>next; } ase { sgpit power piapowe) { newnode->voetf ptrl >coeft, newnode->power=ptrl->power; newnode->next-NULL; list3=create(list3.newnode); ptrl=ptrl->next; Yee { newnode-eoct= pct newnode->power=ptr2->power; newnode->next=NULL; list3=create(list3,newnode); ptr2=ptr2->next; by FOR SUBTRACTION OF POLYNOMIALS add this statement in the above program newnode->coeff ~ ptrl>coeff - ptr2->coeff MULTIPLICATION OF POLYNOMIALS: Multiplication of two polynomials however requires manipulation of each node such that the exponents are added up and the coefficients are multiplied. After each term of first polynomial is operated upon with each term of the second polynomial, then the result hasStep 2 - Consider the least significant digit of each number in the list which is to be sorted. Step 3 - Insert each number into their respective queue based on the least significant digit. Step 4 - Group all the numbers from queue 0 to queue 9 in the order they have inserted into their respective queues. Step 5 - Repeat from step 3 based on the next least significant digit. Step 6 = Repeat from step 2 until all the numbers are grouped based on the most significant digit. EXAMPLE 1 Consider the following list of unsorted integer numbers 82, 901, 100, 12, 150, 77, 55 & 23 Step 1 ~ Define 10 queues each represents a bucket for digits from 0 to 9. UUUUUUUUUU Saas nats Soma” een See Seat Saae! eae’ seane tem ‘Step 2 - Insert all the numbers of the list into respective queue based on the Least significant digit (once placed digit) of every number. 82, 901, 100, 12, 150, 77, 55 & 23 BWEEIULIULUL Queue Queue Quene2 Quur3 Queeet Queues Queor6 Queer? Quour® Queue? Group all the numbers from queue- to queue-9 Inthe order they have inserted & consider the list for next step as input list. 100, 150, 901, 82, 12, 23, 55 & 77170, 90, 802, 2, 24, 45, 75, 66 Sorting by next digit (10s place) gives: [*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.] 802, 2, 24, 45, 6 170, 75, 90 Sorting by the most significant digit (100s place) gives: 2, 24, 45, 66, 75, 90, 170, 802 EXAMPLE 3 In the given array, the largest element is 736 that have 3 digits in it. So, the loop will run up to three times (i.c., to the hundreds place). That means three passes ate required to sort the array. Now, first sort the elements on the basis of unit place digits (i.e., x = 0). Here, we are using the counting sort algorithm to sort the elements. Pass 1 In the first pass, the list is sorted on the basis of the digits at 0's place. After the first pass, the array elements are =° x eervouru After the third pass, the array elements are — Now, the array is sorted in ascending order. Radix sort complexity Now, let's see the time complexity of Radix sort in best case, average case, and worst case. We will also see the space complexity of Radix sort. 1. Time Complexity © Best Case Complexity - It occurs when there is no sorting required, ie. the array is already sorted. The best-case time complexity of Radix sort is S(n+k), + Average Case Complexity - It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of Radix sort is 0(nk). © Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of Radix sort is O(nk). 2, Space Complexity © The space complexity of Radix sort is O(n + k).int list[] = { 82, 901, 100, 12, 150, 77, 55, 23 }; int i, n = sizeofllist) / sizeof(list[O)); print{("List of numbers before sort: \n"); for(i = 0; i<8; i++) printf("%die", listfi] ); radixsort(list, n); printf("\n\nList of numbers after sort: \n") print(list, n); printf("\n\n"); return 0; OUTPUT List of numbers before sort: 82 901 100 12 150 77 58 23 List of numbers after sort: 12 23° 55 (77 82 «100 150 901 MULTILISTS A multilist is a structure in which a number of lists are combined to form a single aggregate structure. A university with 40,000 students and 2,500 courses needs to be able to generate two types of reports. The first report lists the class registration for each class, and the second report lists, by student, the classes that each student is registered for. The obvious implementation might be to use a two-dimensional array. Such an array would have 100 million entries. The average student registers for about three courses, so only 120,000 of these entries, or roughly 0.1 percent, would actually have meaningful data. What is needed is a list for each class, which contains the students in the class. We also need a list for each student, which contains the classes the student is registered for. Figure 3.27 shows our implementation, As the figure shows, we have combined two lists into one, All lists use a header and are circular. To list all of the students in class C3, we start at C3 and traverse its list (by going right). The first cell belongs to student SI. Although there is no explicit information to this effect, this can be determined by following the student's linked list until the header is, reached. Once this is done, we return to C3's list (we stored the position we were at in the course list before we traversed the student's list) and find another cell, which can be