{"id":52,"date":"2018-07-18T08:56:43","date_gmt":"2018-07-18T08:56:43","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=52"},"modified":"2018-12-12T07:08:27","modified_gmt":"2018-12-12T07:08:27","slug":"linked-list-implementation-of-list-adt","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/linked-list-implementation-of-list-adt\/","title":{"rendered":"Linked List Implementation of List ADT"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures.This is the fourth module of the course and we will be talking about the linked list implementation of List ADT.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of this module are as follows:\r\n\r\n \r\n\r\n\u2022 To understand Linked List Implementation of List ADT\r\n

\u2022 To explore the singly linked list, the circular list and the doubly linked list implementations of List ADT<\/p>\r\n\u2022 To know about the representation of a polynomial as a linked list\r\n\r\n \r\n\r\n4.1 Linked List Implementation (Pointer)<\/strong>\r\n\r\n \r\n

Sometimes it is not possible or realistic to ensure that the list is stored contiguously as it may not be possible to determine the size of the list required beforehand. We may end up wasting space because we have overestimated the requirements. In such cases we use a linked list. In this case we have a series of structures or locations that are not necessarily adjacent in memory. Compared to the array implementation, the pointer implementation uses only as much space as is needed for the elements currently on the listbut however requires additional space for the pointers in each cell of the linked list.<\/p>\r\n \r\n

Linked lists require some additional steps of code during implementation, but however have some specific advantages as the linked list is dynamic as they can easily grow and shrink in size.We don\u2019t need to know how many nodes will be in the list. The locations necessary for the linked list are obtained as when needed.<\/p>\r\n \r\n\r\n4.2 Easy and Fast Insertions and Deletions<\/strong>\r\n\r\n \r\n

To insert or delete an element in an array what is needed is to copy to temporary variables to make room for new elements and close the gap caused by deleted elements.With a linked list, there is no need to move other nodes. We need to only reset some pointers. In other words for a linked list implementation there is no need to estimate the maximum size of the list and consequently there is no wasted space. The time taken for some of the common operations such as printList, find and findKth is of the order of O(n) while insert and delete is of the order of O(1). Insert at position 0 (making a new element) or inserting does not require moving the other elements.<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Similarly delete at position 0 or deleting requires no shifting of elements. Insertion and deletion becomes easier, but finding the Kth element for the place where insertion or deletion needs to be carried out requires time of the order of O(n).<\/p>\r\n \r\n

4.3 Linked Lists<\/strong><\/p>\r\n \r\n

A linked listis essentially a series of nodes connected by links where each node contains some data (any type) and apointer to the next node in the list. In some cases there may be a Head<\/em><\/strong>whichis a pointer to the first node. The Head node has null data value with its pointer pointing to the first node in the list. For convenience we do not show the contents of the head node except the pointer to the first node in the list.The last node of a linked list normally points to NULL(Figure 4.1). Note, that the nodes in a linked list can be spread out <\/strong>over the memory and need not occupy contiguous memory locations. In all the discussions regarding insertion and deletion operations on lists we assume that the list is not empty and hence we do not discuss boundary conditions.<\/p>\r\n

\"\"<\/p>\r\n

4.3 Insertion- The Scenario<\/strong><\/p>\r\n

Let us study the insertion scenario in the case of linked lists. You have a linked list which may be empty or not, may beordered, or not. You want to add an element into the given linked list (Figure 4.2).<\/p>\r\n\"\"\r\n

When inserting a new node into a linked list, there are four possible cases as described below:<\/p>\r\n \r\n\r\n1. Insert into an empty list\r\n\r\n2.Insert in front\r\n\r\n3. Insert at back\r\n\r\n4. Insert in middle\r\n\r\n \r\n

However in fact, we need to handle only two cases. The insert as the first node can handle Case 1 and Case 2. Insert in the middle or at the end of the list Case 3 and Case\u00a04can be handled in a similar manner.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\u00a0 \u00a0 \u00a0<\/strong>\r\n\r\n 4.3.1 The Actual Insertion<\/strong>\r\n\r\n \r\n\r\nThe actual insertion into a linked list involves the following steps:\r\n