1 Linked Lists – I2Lists Lists are ordered collections of objects. This does not mean that lists are sorted, but rather that as items are added, one can predict their relative positions. For example, one can define an operator that adds items at the end of the list, or at the front. Given the list 20,30,50, the operation append 69 will result in 20,30,50,69, while addfront 12 to the new list would result in 12,20,30,50,69. As you observe this particular list is already sorted. Now to insert element 42 in its proper position in the list, we may like to define a new operation insert 42, which would result in the list 12,20,30,42,50,69. If we are searching for a specific item, and we find it in the list, we return 1. The operation search 30 would return 1, as the element is present in the list. We can also remove items from the list through a delete operation such as delete 20, which would create an empty position (a hole) in the list, and all elements after 20 would have to be shifted one position forward to result in the final list 12,30,42,50,69. The effect of insert 25 would require shifting all elements 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 searching or 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 the beginning of the array, you have to shift all the elements down by one position to accommodate it. Similarly, to delete an item, you have to shift up all the elements to fill in the hole created by the item. For a list with n elements, these operations could be more expensive computations of the order O(n). Another shortcoming with arrays is that they have to have a fixed size, which must be declared in advance before the program starts executing. In many applications, the number of elements in the list may vary greatly, depending on the input, so memory requirements may change during execution of the program. Recursive data structures What is desired is a way to allocate memory for new items ONLY WHEN necessary, and to free that memory space when it is no longer needed. Furthermore, this newly allocated memory 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 a data item followed by another list. The list 12,20,30,42,50,69 can be thought of as being composed of the data item 12, followed by another list 20,30,42,50,69. Thus we can define a list structure in terms of itself. Data types that are defined in this way are called recursive data types. Consider the structure3struct 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 referred to as a linked list. Each element is linked to the next one through a link field, which is a pointer to the address of the next element. But the definition alone is not sufficient to store the values of the elements of the list. You have 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. Here is an example which allocates memory for a particular node to hold the value of an integer, and also the pointer to the next node. Memory allocation for a node: struct node{ int data; struct node *next; }; struct node *ptr; ptr = (struct node *) malloc(sizeof(struct node)); Once the data has been processed, and the program does not require the data, the memory occupied by the node can be returned to main memory . • Function free de-allocates memory- i.e. the memory is returned to the system so that the memory can be reallocated in the future. e.g. free(ptr); ? ? ptr ptr ?4Linked Lists • It is an important data structure. • An abstraction of a list: i.e. a sequence of nodes in which each node is linked to the 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. contiguous spaces in the memory) − Arrays are fixed size: either too big (unused space ) or not big enough (overflow problem) − 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 data movement, 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 in the 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 few nodes, without disturbing the rest of the list. This is the greatest advantage. − But getting to a particular node may take large number of operations, as we do not know the address of any individual node . − Every node from start needs to be traversed to reach the particular node.5 A simple Node Structure A 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. struct list { int data; struct list *next; } The pointer variable next is called a link. Each structure is linked to a succeeding structure by way of the field next. The pointer variable next contains an address of either the location in memory of the successor struct list element or the special value NULL. data next6More examples of Nodes A node with one data field: struct node{ int number; struct node * link; }; A node with 3 data fields: struct student{ char name[20]; int id; double grdPts; struct student *next_student; }; A structure in a node: struct person{