ArraysLinked ListsA node in a linked list is a structure that has at least two fields. One of the fields is a data field; the other is a pointer that contains the address of the next node in the sequence.More examples of NodesA simple Linked ListEmpty ListBasic Linked List OperationsAdding node to Empty ListAdd Node at EndThis would result in the node pNew to be linked to pPre.Add Node at BeginningCounting the nodes in a ListCreating a Linked list from an arrayLinked Lists 1ListsLists are ordered collections of objects. This does not mean that lists are sorted, butrather that as items are added, one can predict their relative positions. For example, onecan define an operator that adds items at the end of the list, or at the front. Given the list20,30,50, the operation append 69 will result in 20,30,50,69, while addfront 12 to thenew list would result in 12,20,30,50,69. As you observe this particular list is alreadysorted. Now to insert element 42 in its proper position in the list, we may like to define anew operation insert 42, which would result in the list 12,20,30,42,50,69. If we aresearching for a specific item, and we find it in the list, we return 1. The operation search30 would return 1, as the element is present in the list. We can also remove items from thelist through a delete operation such as delete 20, which would create an empty position (ahole) in the list, and all elements after 20 would have to be shifted one position forwardto result in the final list 12,30,42,50,69. The effect of insert 25 would require shifting allelements after 12 one position back to accommodate the new element 25.You know how easy it is to implement the lists using arrays, where we could do searchingor sorting operations. If the list were sorted, the searching operation would take O(log n)operations. What about insert and delete operations? To insert a new element in thebeginning of the array, you have to shift all the elements down by one position toaccommodate it. Similarly, to delete an item, you have to shift up all the elements to fillin the hole created by the item. For a list with n elements, these operations could bemore expensive computations of the order O(n). Another shortcoming with arrays is that they have to have a fixed size, which must bedeclared in advance before the program starts executing. In many applications, thenumber of elements in the list may vary greatly, depending on the input, so memoryrequirements may change during execution of the program.Recursive data structuresWhat is desired is a way to allocate memory for new items ONLY WHEN necessary, andto free that memory space when it is no longer needed. Furthermore, this newly allocatedmemory must be logically combined into a single entity (representing the list).What is a list? We can think of a list as an entity containing a similar entity. A list is adata item followed by another list. The list 12,20,30,42,50,69 can be thought of as being2composed of the data item 12, followed by another list 20,30,42,50,69. Thus we candefine a list structure in terms of itself. Data types that are defined in this way are calledrecursive data types.Consider the structurestruct list{int data;struct list *next;};This structure defines a list as containing an item of type int, followed by another list.The second list is connected through the link next. More appropriately, this list is referredto as a linked list. Each element is linked to the next one through a link field, which is apointer to the address of the next element.But the definition alone is not sufficient to store the values of the elements of the list. Youhave to request memory to allocate space to hold each item. As the structure is dynamic(it can grow or shrink), more memory can be requested dynamically. Dynamic Memory AllocationCreating and maintaining dynamic data structures requires dynamic memory allocation –the ability for a program to obtain more memory space at execution time to hold newvalues, and to release space no longer needed.In C, functions malloc and free, and operator sizeof are essential to dynamicmemory allocation.- Unary operator sizeof is used to determine the size in bytes of any data type.e.g.sizeof(double)sizeof(int)- Function malloc takes as an argument the number of bytes to be allocated andreturn a pointer of type void * to the allocated memory. (A void * pointer maybe assigned to a variable of any pointer type. ) It is normally used with the sizeofoperator.3An example:struct node{int data;struct node *next;};struct node *ptr;ptr = (struct node *) malloc(sizeof(struct node)); - Function free de-allocates memory- i.e. the memory is returned to the system sothat the memory can be reallocated in the future.e.g.free(ptr);4??ptrptr?Linked Lists- It is an important data structure.- An abstraction of a list: i.e. a sequence of nodes in which each node is linked tothe node following it.- Lists of data can be stored in arrays, but linked lists provide several advantages:Arrays- In an array each node (element) follows the previous one physically (i.e. contiguousspaces in the memory)- Arrays are fixed size: either too big (unused space ) or not big enough (overflowproblem)- Maximum size of the array must be predicted which is sometimes not possible.- Inserting and deleting elements into an array is difficult. Have to do lot of datamovement, if in array of size 100, an element is to be inserted after the 10th element,then all remaining 90 have to be shifted down by one position.Linked Lists- Linked lists are appropriate when the number of data elements to be represented inthe data structure are not known in advance.- Linked lists are dynamic, so the length of a list can increase or decrease as necessary.- A linked list is a collection of nodes, each node containing a data element.- Each node does not necessarily follow the previous one physically in the memory.Nodes are scattered at random in memory.- Insertion and Deletion can be made in Linked lists , by just changing links of a fewnodes, without disturbing the rest of the list. This is the greatest advantage.5- But getting to a particular node may take large number of operations, as we do notknow the address of any individual node .- Every node from start needs to be traversed to reach the particular node.A simple Node StructureA node in a linked list is a structure that has at least two fields.