UCTURES LINEAR DaTA STR ore and organize data in a 1. Data may be arranged in ticular organization cture is a Specific way to st hese data can be used efficiently late! he logical or mathematical model for a pa In computer terms, a data stru computer's memory so that t! many different ways such as # of data is termed as a data structure. Need of Data Structures As applications are getting complexed and amount of data is increasing day by day, there may arrise the following problems: 1. Processor speed: To handle very large amout of data, high s| butas the data is growing day by day to the billions of files per entity, processor may fail to deal with that much amount of data. 2. Data Search: Consider an inventory size of 106 items ina store, If our application needs to search for a particular item, it needs to traverse 106 items every time, results in slowing down the search process. 3. Multiple requests: If thousands of users are searching the data simultaneously on a web server, then there are the chances that a very large server can be failed during that process in order to solve the above problems, data structures are used. Data is organized to form a data structure in such a way that all items are not required to be searched and required data can be searched instantly. peed processing is required, ‘Types of Data Structure The data structure can be sub divided into major types: 1. Linear Data Structure 2. Non-linear Data Structure LoL Linear Data Structure : A data structure is said to be linear if its elements combine to form any specific order. There are basically two techniques of representing such linear structure within memory. , TATA Pusiications————ie 3 nong all the elements representeg tures are termed as arrays, tionships ar se linear struc the linear relationship among all the elements. ei i inear structures are id technique onceptof pointers or links. These line: a rete ems i eare: tie byusing ron examples of linear data structure y = ts. The comm xa inear rel ig to provide the linea? soa + inca memory cation: is wo provide First" means 0! The secon represented as linked lis siacksd Linked lists ; P Stack ture: This structure is mostly used for representing data that near Data Struct mong various elements. Examples of Non Linear ionship ar ations! eats 2 Family of trees Table of contents 2. Noni contains a hierarchical rel: Data Structures are listed given: d ‘Advantages of Data Structures 1. Efficiency : Efficiency of a program de example: suppose, we have some data and we nee record, In that case, if we organize our data in an array, sequentially element by element. hence, using array may not be very efficient here. There are better data structures which can make the search process efficient like ordered array, binary search tree or hash tables. pends upon the choice of data structures. For .d to perform the search for a particular we will have to search 2. Reusability: Data structures are reusable, ie. once we have implemented a particular data structure, we can use it at any other place. Implementation of data structures can be compiled into libraries which can be used by different clients. 3. Abstraction: Data structure is specified by the ADT which provides a level of abstraction. The client program uses the data structure through interface only, without getting into the implementation details, Disadvantages of Data Structures 1. Auser who has deep knowled; e ctionali ae P ige about the functionality of the data structure can make 2 If thereis an error in the data structure cannot help themselves solve the prob sin aned fe Seteet the bug; The original user lem and fix it, 32 | LINEAR Data STRUCTURES i aa, nsxalaeid Alinear data st h the elem ructure is a stru i nel cture in whic] elements are connected to the previous and the owe sequentially, sed ; ‘quentially, so they can be traversed or ac near data structures is easier ag the el — P ele a ents are stored sequentially, and 3 cement. As the elements are stored noe ne sole Tun. The implementation of iene s ially organized ji td one after another and can i only one elena i 'Y One element at. data elements in an array atime, Tata PusLications 1DATA STRUCTURES USING C inked List. ‘The types of linear data structures are Array, Queue, Stack, L r example, if we want 1, Array: An array consists of data elements of a same data type tostore the roll numbers of 10 students, so instead of creating 10 integer type variables, we will create an array having size 10. Therefore, we can say that an array saves a lot of memory and reduces the length of the code. 2, _ Stack: It is linear data structure that uses the LIFO (Last In-First Out) rule in which the data added last will be removed first. The addition of data element in a stack is known as a push operation, and the deletion of data element form the list is known as pop operation. OQeve 3. Queue: It is @ data structure that uses the FIFO rule (First In-First Out). In this rule, the element which is added first will be removed first. There are two terms used in the queue front end and rear The insertion operation performed at the back end is known ad enqueue, and the deletion operation performed at the front end is known as dequeue. 4, Linked list: It is a collection of nodes that are made up of two parts, ie., data element and reference to the next node in the sequence. Arrays are defined as the collection of similar types of data items stored at contiguous memory locations. It is one of the simplest data structures where each data element can be randomly accessed by using its index number. In C programming, they are the derived data types that can store the primitive type of data such as int, char, double, float, etc. For example, if we want to store the marks of a student in 6 subjects, then we don’t need to define a different ‘variable for the marks in different subjects. Instead, we can define an array that can store the marks in each subject at the contiguous memory locations. Following are the important terms to understand the concept of Array. 1. Element : Each item stored in an array is called an element. 2. Index : Each location of an element in an array has a numerical index, which is used to identify the element. Properties of Array ‘There are some of the properties of an array that are listed as follows - 1. Each element in an array is of the same data type and carries the same size that is 4 bytes, 2. Elements in the array are stored at contiguous memory locations from which the first clement is stored at the smallest memory location. Tata Puatications 35]MCA e array can be randomly accessed since we can calculate the addres, 8 of s of th “ 3, Elements of th en base address and the size of the data ete, "Mens each element of the array with the giv’ Representation of an Array in various ways in different programming languages, As - AS an We can represent an array illustration, let's sce the declaration of array in C language - “ne Elements int array [10] = (35, 33, 42, 10, 14, 19, 27, 44, 26, 31} Type Size As per the above illustration, there are some of the following important points - 1. Index starts with 0. 2. Thearray’s length is 10, which means we can store 10 elements. 3. Each element in the array can be accessed via its index. Types of Array Representation In the Data Structure, there are two types of array representation are exists: 1. One Dimensional Array 2. Two Dimensional Array 1. One Dimensional Array Itisa list of the variable of similar data types.It allows random access and alll the elements can be accessed with the help of their index.The size of the array is fixed.For a dynamically sized array, vector can be used in C++. Representation of 1D array: Memory Location 200 201 202 203 204 205206" =" * Te ToTsfe[o[-T-T-] oT 23 45 6+. = Index 2. Two Dimensional Array Itis a list of lists of the variable of the same data type.It also allows random access all the elements can be accessed with the help of their index.It can also be see" - collection of 1D arrays, Itis also known as the Matrix.Its dimension can be increase [ss] SSS Tata Pusie and SATIONSDATA STRUCTURES USING C from 2 to 3 and 4 so on. They all are referred to as a multi-dimension array. The most common multidimensional array is a 2D array. Representation of 2D Array Column d Column Column 2 [stor [ cae xa Applications of Arrays 1, 2D Arrays are used to implement matrices. 2. Arrays can be used to implement various data structures like a heap, stack, queue, etc. 3. They allow random access. 4. They are cache-friendly. Memory Allocation of an Array As stated above, all the data elements of an array are stored at contiguous locations in the main memory. The name of the array represents the base address or the address of the first element in the main memory. Each element of the array is represented by proper indexing. We can define the indexing of an array in the below ways - 1. 0 (zero-based indexing): The first element of the array will be arr{0]. 2. 1 (one-based indexing): The first element of the array will be arr[1]. 3. n(n- based indexing): The first element of the array can reside at any random index number. ma ‘Address 4 104 108 nz 116 take 4 bytes in the memory. Tata PusticationsMCA Basic Operations of Array . rane say Now, let’s discuss the basic operations supported in the array 4, Traversal - This operation is used to print the elements of the array. 2. Insertion - Itis used to add an element ata particular index. delete an element from a particul: nt using the given index or by the value. 3, _ Deletion - It is used to jar index. 4. Search - It is used to search an eleme! 5. Update - It updates an element at a particular index. Advantages of Array 1. Array provides the single name for the group of variables of the same type. Therefore, it is easy to remember the name of all the elements of an array. 2, Traversingan array isa very simple process; we just need to increment the base address of the array in order to visit each element one by one. 3. Any element in the array can be directly accessed by using the index. Disadvantages of Array 1. Array is homogenous. It means that the elements with similar data type can be stored init. 2. Inarray, there is static memory allocation that is size of an array cannot be altered. 3. we will be wastage of memory if we store less number of elements than the declared size. 2D Array 2 ; ek D array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns. He ee ee ere ‘ implement a relational database look alike data of functions wherever required, ig bulk of data at once which can be passed to any number How to Declare 20 Array The syntax of declaring two dimensi 'g two dimensional array is very much similar to that of a one dimensional array, given as follows int arr[max_rows|{max_columns]; Le) neDATA STRUCTURES USING C However, It produces the data structure which looks like following. 0 1 2 seek med 0 afoj(o} { son, afoyiz) |... 7 ajoynay | 1 afayto) | afay aftyi2) |... afaj(n-a} 2 | azo) | ages | ayy |... s2te-a) | 3 | amy | ats) agai) |. [soe | 4 wero) story ware [aes | afn-a}ia} | afn-ayia) | ..... a{n-1}[n-2)} afn][n] Above image shows the two dimensional array, the elements are organized in the form of rows and columns. First element of the first row is represented by a[0][0] where the number shown in the first index is the number of that row while the number shown in the second index is the number of the column. How do we access data in a 2D array Due to the fact that the elements of 2D arrays can be random accessed. Similar to one dimensional arrays, we can access the individual cells in a 2D array by using the indices of the cells. There are two indices attached to a particular cell, one is its row number while the other is its column number. However, we can store the value stored in any particular cell of a 2D array to some variable x by using the following syntax. int x = afi] {jj where i and jis the row and column number of the cell respectively. We can assign each cell of a 2D array to 0 by using the following code: for ( int i= { for (int j=0; j void main () { int arr[3][3],ij; for (i=0;i<3;i++) { for (j=0;j<3;j++) { printf(“Enter al %dJ[%d]: ij); scanf(“%d”" &arr{i] [j)); } } printf(’\\n printing the elements ....\n”); for(i=0;i<3;i++) { printf(“\n"); for (j=0;j<3,j+-+) { Printf(“%d\ ” arrfiJfj);DATA STRUCTURES USING C 3.4 A Stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. Stack has one end, whereas the Queue has two ends (front and rear). It contains only one pointer top pointer pointing to the topmost element of the stack. Whenever an element is added in the stack, it is added on the top of the stack, and the element can be deleted only from the stack. In other words, a stack can be defined as a container in which insertion and deletion can be done from the one end known as the top of the stack. Some key points related to stack 1, _ Itis called as stack because it behaves like a real-world stack, piles of books, etc. 2. A Stack is an abstract data type with a pre-defined capacity, which means that it can store the elements of a limited size. 3. It isa data structure that follows some order to insert and delete the elements, and that order can be LIFO or FILO, Working of Stack Stack works on the LIFO pattern. As we can observe in the below figure there are five memory blocks in the stack; therefore, the size of the stack is 5. Suppose we want to store the elements in a stack and let’s assume that stack is empty. We have taken the stack of size 5 as shown below in which we are pushing the elements one by one until the stack becomes full. Pusht >| Push2 Pusha. Push 4 Push 5 >} Since our stack is full as the size of the stack is 5. In the above cases, we can observe that it goes from the top to the bottom when we were entering the new element in the stack. The stack gets filled up from the bottom to the top. When we perform the delete operation on the stack, there is only one way for entry and exit as the other end is closed. It follows the LIFO pattern, which means that the value entered first will be removed last. In the above case, the value 5 is entered first, so it will be removed only after the deletion of all the other elements. < a] TATA PUBLICATIONS -MCA a perations implemented on the stack: are some common opera lowing aay Tete an element ina stack then the operation is known as a Push, If 7 ve insert 1. push(): When we in: sl the stack is full then the overflow condition occurs. (): When we delete an element from the stack, the operation is known 8 a pop. If Hee is empty means that no element exists in the stack, this state is known as an he sta a underflow state. 3. _ isEmpty(): It determines whether the stack is empty or not. 4, isFull(): It determines whether the stack is full or not.’ 5. peek(): It returns the element at the given position. 6. count(): It returns the total number of elements available in a stack. 7. change(): It changes the element at the given position. 8. display(): It prints all the elements available in the stack, PUSH operation The steps involved in the PUSH operation is given below: 1 Before inserting an element ina stack, we check whether the stack is full. 2. Ifwe try toinsert the element ina stack, and the stack is full, then the overflow condition occurs, 3. When weinitialize a stack, we set the value of topas -1 to check that the stack is empty. 4. When thenew elementis pushed ina Stack, first, the value of the top gets incremented, i.e, top=top+1, and the element will be placed at the new Position of the top. 5. The elements will be inserted until we reach the max size of the stack, tort EP one ED..., =... |__| re Ls 20 2 73 Ke empty i -TATA PUBLICATIONSDATA STRUCTURES USING C POP Operation The steps involved in the POP operation is given below: 1, _ Before deleting the element from the stack, we check whether the stack is empty. 2. If we try to delete the element from the empty stack, then the underflow condition occurs. 3. __ Ifthe stack is not empty, we first access the element which is pointed by the top 4. Once the pop operation is performed, the top is decremented by 1, ie., top=top-1. top=3 top=2 top=4 “—~Pop = 40 4 pop = 30 40 0 30 30 30 20 20 20 10 40 10 Stack is full top=0 top=-4 top=-4 Neer een t0 P 20 io [~e empty The following are the applications of the stack: Balancing of Symbols Stack is used for balancing a symbol. For example, we have the following program: int main() { cout< dotete Input restricted double ended queue 2. Output restricted deque - As the name implies, in output restricted queue, deletion operation can be performed at only one end, while insertion can be performed from both ends. front rear | 4 ert ge Output restricted double ended queue Operations performed on Queue The fundamental operations that can be performed on queue are listed as follows - 1. Enqueue: The Enqueue operation is used to insert the element at the rear end of the queue. It returns void. 2. Dequeue: It performs the deletion from the front-end of the queue. It also returns the element which has been removed from the front-end. It returns an integer value. 3. Peek: This is the third operation that returns the element, which is pointed by the front pointer in the queue but does not delete it. Queue overflow (isfull): It shows the overflow condition when the queue is completely full. Queue underflow (isempty): It shows the underflow condition when the Queue is empty, i.e., no elements are in the Queue. Ways to implement the queue There are two ways of implementing the Queue: 1. Implementation using array: The sequntial allocation in a Queue can be implemen'™4 using an array, ahs : 2. Implementation using Linked list: TI implemented using a linked list, 100DATA STRUCTURES USING C. Array representation of Queue Wecan easily represent queue by using linear arrays, There afetwo variables i.¢. 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. Initially, the value of front and queue is -1 which represents an empty queue. Array representation of a queue containing 5 elements along with the respective values of front and rear, is shown in the following figure. 4 Tor 2 a 6 front ae § 4 Queue The above figure shows the queue of characters forming the English word “HELLO”. Since, No deletion is performed in the queue till now, therefore the value of front remains -1. However, the value of rear increases by one every time an insertion is performed in the queue. After inserting an element into the queue shown in the above figure, the queue will look something like following. The value of rear will become 5 while the value of front remains same. s o a — «lo front rear Queue after inserting an element After deleting an element, the value of front will increase from -1 to 0. however, the queue will look something like following. {_Te Queue ater deleting an element Tata Puptications ——————————_MCA Algorithm to insert any Element in a Queue Check if the queue is already full by comparing rear to max - 1. if so, then return an overflow error. If the item is to be inserted as the first element in the list, in that case set the value of front and rear to 0 and insert the element at the rear end. Otherwise keep increasing the value of rear and insert each element one by one having rear as the index. Algorithm 1. Step 1: IF REAR= MAX-1 Write OVERFLOW Go to step [END OF IF] 2. Step 2: IF FRONT = -1 and REAR = -1 SET FRONT = REAR = 0 ELSE SET REAR = REAR+1 [END OF IF] 3. Step 3: Set QUEUE[REAR] = NUM 4. Step 4: EXIT Algorithm to delete an element from the queue If, the value of front is -1 or value of front is greater than rear , write an underflow message and exit. Otherwise, keep increasing the value of front and return the item stored at the front end of the queue at each time. Algorithm 1. Step 1: IF FRONT =-1 or FRONT > REAR Write UNDERFLOW ELSE SET VAL = QUEUE[FRONT] SET FRONT = FRONT +1 {END OF IP] 2 Step 2: EXIT LaDATA STRUCTURES USING C prawback of Array Implementation Although, using this technique toimpl the technique of creating, a queue is easy, but there are some drawbacks of jement a queue. ace of the array, which is used to store queue elements, can f that queue because the elements can only be igh so that, all the space before 1. Memory wastage : The sp: never be reused to store the elements of inserted at front end and the value of front might be so hi that, can never be filled. limitation of array representation of queue The above figure shows how the memory space is wasted in the array representation of queue. In the above figure, a queue of size 10 having 3 elements, is shown. The value of the front variable is 5, therefore, we can not reinsert the values in the place of already deleted element before the position of front. That much space of the array is wasted and can not be used in the future (for this queue). 2. Deciding the array size On of the most common problem with array implementation is the size of the array which requires to be declared in advance. Due to the fact that, the queue can be extended atruntime depending upon the problem, the extension in the array size is a time taking process and almost impossible to be performed at runtime since a lot of reallocations take place. Due to this reason, we can. declare the array large enough so that we can store queue elements as enough as possible but the main problem with this declaration is that, most of the array slots (nearly half) can never be reused. It will again lead to memory wastage. Linked List implementation of Queue Due to the drawbacks discussed in the previous section of this tutorial, the array implementation can not be used for the large scale applications where the queues are implemented. One of the alternative of array implementation is linked list implementation of queue. The storage requirement of linked representation of a queue ‘vith 1 elements is o(n) while the time requirement for operations is o(1). 1 baat 9 si tlinked queue, each node ofthe queue consis of two parts ie, data part and the ink part. Each element of the queue points to its immediate next elementin the memory. Tata PuBLicationsP cn and rear pointer. Thi while the rear pointer contains the address of the last element of the queue. In the linked queue, there are two pointers maintained in the memory i.e. front Point i front pointer contains the address of the starting element of the quest ‘Ue Insertion and deletions are performed at rear and front end respectively. If front ang rear both are NULL, it indicates that the queue is empty. The linked representation of queue is shown in the following figure. oH HA} front rear Linked Queue Operation on Linked Queue There are two basic operations which can be implemented on the linked queues. The operations are Insertion and Deletion. 1. _ Insert operation ‘The insert operation append the queue by adding an element to the end of the queue. The new element will be the last element of the queue. Firstly, allocate the memory for the new node ptr by using the following statement. Ptr = (struct node *) malloc (sizeof(struct node)); There can be the two scenario of inserting this new node ptr into the linked queue. In the first scenario, we insert element into an empty queue. In this case, the condition front = NULL becomes true. Now, the new element will be addedas the only element of the queue and the next pointer of front and rear pointer both, will point to NULL. pir-> data front = ptr; rear = ptr; front -> next = NULL; rear -> next = NULL; } In the second case, the queue contains more than one element. The condition Ee NULL becomes false. In this scenario, we need to update the end pointer rearsothat Nt pointer of rear will point to the new node ptr. Since, this is a linked queue, hence w° we : : 08 ! E TATA Pusuicarions ad—_— to make the rear pointer point to the newly added node ptr. We also need to make the next f rear point to NULL. pointer 0 rear -> next = ptr; rear = ptr; rear->next = NULL; In this way, the element is inserted into the queue. The algorithm and the C implementation is given as follows. Algorithm 4. Step 1: Allocate the space for the new node PTR 2. Step 2: SET PTR -> DATA = VAL 3. Step 3: IF FRONT = NULL SET FRONT = REAR = PTR SET FRONT -> NEXT = REAR -> NEXT = NULL ELSE SET REAR -> NEXT = PTR SET REAR = PTR SET REAR -> NEXT = NULL [END OF IF] 4, Step 4: END 2. Deletion Deletion operation removes the element that is first inserted among all the queue elements. Firstly, we need to check either the list is empty or not. The condition front == NULL becomes true if the list is empty, in this case , we simply write underflow on the console and make exit. Otherwise, we will delete the element that is pointed by the pointer front. For this purpose, copy the node pointed by the front pointer into the pointer ptr. Now, shift the front pointer, point to its next node and free the node pointed by the node ptr. This is done by using the following statements. ptr = front; front = front -> next; free(ptr); Tata PuBuications.MCA The algorithm and C function is given as follows. Algorithm: Step 1: IF FRONT = NULL Write” Underflow “ Go to Step 5 [END OF IF} Step 2: SET PTR = FRONT Step 3: SET FRONT = FRONT -> NEXT Step 4: FREE PTR Step 5: END Due to the fact that queue performs actions on first in first out basis which is quite fair for the ordering of actions. There are various applications of queues discussed as below 1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU. Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate between two processes) for eg. pipes, file IO, sockets. Queues are used as buffers in most of the applications like MP3 media player, CD player, ete. Queue are used to maintain the play list in media players in order to add and remove the songs from the play-list. Queues are used in operating systems for handling interrupts. Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory. The last node of the list contains pointer to the null, Head 481 lnk 106DATA STRUCTURES USING C Uses of Linked List 1, Thelist is not required to be contiguously present in the memory. The node can reside any where in the memory and linked together to make a list. This achieves optimized utilization of space. 2, _ list size is limited to the memory size and doesn’t need to be declared in advance. 3. Empty node can not be present in the linked list. 4. Wecan store values of primitive types or objects in the singly linked list. Operations performed on Linked list The basic operations that are supported by a list are mentioned as follows - Insertion - This operation is performed to add an element into the list. Deletion - It is performed to delete an operation from the list. Display - It is performed to display the elements of the list. Peps Search - It is performed to search an element from the list using the given key. Types of Linked list The following are the types of linked list: 1. Singly Linked list Doubly Linked list Circular Linked list Doubly Circular Linked list PeN It is the commonly used linked list in programs. If we are talking about the linked list, it means it is a singly linked list. The singly linked list is a data structure that contains two parts, i.e., one is the data part, and the other one is the address part, which contains the address of the next or the successor node. The address part ina nodeis also known asa pointer. Suppose we have three nodes, and the addresses of these three nodes are 100, 200 and 300 respectively. The representation of three nodes as a linked list is shown in the below figure: TATA PusticationsMCA We can observe in the above figure that there ae three different nodes having addresg 100, 200 and 300 respectively. The first node contains the address of the next node, i, 209, the second node contains the address of the last node, ie, 300, and the third node contain, the NULL value initsaddress part asit does not point to any node. The pointer that holds the address of the initial node is known asa head pointer. The linked list, whichis shown in the above diagram, is known asa singly linked lista itcontains only asingle link. In this list, nly forward traversal is possible; we cannot traverse in the backward direction as it has only one link in the list, Representation of the node in a singly linked list struct node { int data; struct node “next; } In the above representation, anode containing two members, pointer (next) of the node type. we have defined a user-defined structure named the first one is data of integer type, and the other one is the As the name suggests, the doubly linked list contains two pointers. We can define the doubly linked list as a linear data structure with three parts: the data part and the other two address part. In other words, a doubly linked listis a list that has three parts in a single node, includes one data part, a pointer to its previous node, and a pointer to the next node. Suppose we have three nodes, and the address of these nodes are 100, 200 and 300, respectively. The representation of these nodes in a doubly-linked list is shown below: = o TREES — ES — oe = = = us As we can observe in the above figure, the node in a doubly-linked list has two address Parts; one part stores the address of the next while the other part of the node stores the previous node's address. The initial node in the doubly linked list has the . value in the address part, which provides the address of the previous node. 408 = Tata PUBLICATIONSDATA STRUCTURES USING © Representation of the node ina doubly linked list struct node { int data; struct node *next; struct node *prev; } In the above representation, we have defined a user-defined structure named a node with three members, one is data of integer type, and the other two are the pointers, ie, next and prev of the node type. The next pointer variable holds the address of the next node, and the prev pointer holds the address of the previous node. The type of both the pointers, i.e., next and prev is struct node as both the pointers are storing the address of the node of the struct node type. ‘A circular linked list is a variation of a singly linked list. The only difference between the singly linked list and a circular linked list is that the last node does not point to any node ina singly linke d list, so its link part contains a NULL value. On the other hand, the circular linked list is a list in which the last node connects to the first node, so the link part of the last node holds the first node’s address. The circular linked list has no starting and ending node. We can traverse in any direction, i., either backward or forward. The diagrammatic representation of the circular linked list is shown below: struct node { int data; struct node *next; } A circular linked list is a sequence of elements in which each node has a link to the next node, and the last node is having a link to the first node. The representation of the circular linked list will be similar to the singly linked list, as shown below: Tata Pustications.doubly circular linked list has the features of both the circular linkeq The doubly list and doubly linked list. aE —————— Cee — ES — Es 400 200 300 Inoad entation of the doubly circular linked list in which the lastnodeis attached to the firstnode and thus creates a circle. It is a doubly linked list also because each node holds the address of the previous node also. The main difference between the doubly linked list and doubly circular linked list is that the doubly circular linked list does not contain the NULL value in the previous field of the node. As the doubly circular linked contains three parts, i.e., two address parts and one data part so its representation is similar to the doubly linked list. ‘The above figure shows the repres struct node { int data; struct node “next; struct node *prev; } Advantages of Linked list The advantages of using the Linked list are given as follows - 1, Dynamic data structure - The size of the linked list may vary according to the requirements. Linked list does not have a fixed size. 2. Insertion and deletion - Unlike arrays, insertion, and deletion in linked list is easier. Array elements are stored in the consecutive location, whereas the elements in the linked list are stored at a random location. To insert or delete an el a in an arra we have to shift the elements for creating the space, Whereas, in inked li zi ee id of shifting, we just have to update the address of the pointer of the meas i oi 3. Memory efficient - The size of a linked list can grow or shrink according to the requirements, so memory consumption in linked list is efficient, ret 4. Implementation - We can implement both stacks and queues using linked list. 110 Tata PuBLICATIONSDisadvantages of Linked list The limitations of using the Linked list are given as follows - 1. Memory usage - In linked list, node occupies more memory than array. Each node of the linked list occupies two types of variables, ie., one is a simple variable, and another oneis the pointer variable, 2, Traversal - Traversal is not easy in the linked list. If we have to access an element in the linked list, we cannot access it randomly, while in case of array we can randomly access it by index. For example, if we want to access the 3rd node, then we need to traverse all the nodes before it. So, the time required to access a particular node is large. Reverse traversing ~ Backtracking or reverse traversing is difficult in a linked list. In a doubly-linked list, it is easier but requires more memory to store the back pointer. The applications of the Linked list are given as follows - With the help of a linked list, the polynomials can be represented as well as we can perform the operations on the polynomial. Alinked list can be used to represent the Sparse matrix. The various operations like student’s details, be implemented using the linked list as the li can hold different data types. employee's details, or product details can inked list uses the structure data type that _ 4 Using linked list, wecan implementstack, queue, tree, and other various data structures. 5. The graph is a collection of edges and vertices, and the graph can be represented as an adjacency matrix and adjacency list. If we want to re present the graph as an adjacency matrix, then it can be implemented as an array. If we want to represent the graph as an adjacency list, then it can be implemented as a linked list. 6. linked list can be used to implement dynamic memory allocation. The dynamicmemory allocation is the memory allocation done at the run-time. Tata Puatications eeYr MCA IMPORTANT QUESTIONS ——— TS What is array data structure? What are the representation and applications Of arrays) 2. Elaborate on different types of array data structure. 3. What are different operations available in stack data structure? 4. What is a queue data structure? What are the applications of queue? 5. Differentiate between stack and queue data structure. 6. Whats a linked list data structure? What are the applications for the Linked list? 7. Elaborate on different types of Linked List data structures? 8. __ Differentiate between Array and Linked List. ee Pusticarions