aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaLinked List.pptx

sf

1. LINKED LIST

2. Linked Lists An array is a data structure where elements are stored in consecutive memory locations. In order to occupy the adjacent space, a block of memory that is required for the array should be allocated before hand. Once the memory is allocated, it cannot be extended any more. This is why the array is known as a static data structure . In contrast to this, the linked list is called a dynamic data structure where the amount of memory required can be varied during its use. In the linked list, the adjacency between the elements is maintained by means of links or pointers . A link or pointer actually is the address (memory location) of the subsequent element. Thus, in a linked list, data (actual content) and link (to point to the next data) both are required to be maintained. An element in a linked list is a specially termed node , which can be viewed as shown in Figure 3.1. A node consists of two fields: DATA (to store the actual information) and LINK (to point to the next node).

3. DEFINITION A linked list is an ordered collection of finite, homogeneous data elements called nodes where the linear order is maintained by means of links or pointers. Depending on the requirements the pointers are maintained, and accordingly the linked list can be classified into three major groups: single linked list, circular linked list, and double linked list . Struct node { int number; struct node *p; };

4. SINGLE LINKED LIST (SLL or One Way List) In a single linked list each node contains only one link which points to the subsequent node in the list. Figure 3.2 shows a linked list with six nodes. Here, N1, N2, …, N6 are the constituent nodes in the list. HEADER is an empty node (having data content NULL) and only used to store a pointer to the first node N1. Thus, if one knows the address of the HEADER node from the link field of this node, the next node can be traced, and so on. This means that starting from the first node one can reach to the last node whose link field does not contain any address but has a null value. Note that in a single linked list one can move from left to right only; this is why a single linked list is also called one way list .

5. Representation of a Linked List in Memory There are two ways to represent a linked list in memory: Static representation using array Dynamic representation using free pool of storage Static representation In static representation of a single linked list, two arrays are maintained: one array for data and the other for links. The static representation of the linked list in Figure 3.2 is shown in Figure 3.3.

6. Dynamic representation The efficient way of representing a linked list is using the free pool of storage. In this method, there is a memory bank (which is nothing but a collection of free memory spaces) and a memory manager (a program, in fact). During the creation of a linked list, whenever a node is required the request is placed to the memory manager; the memory manager will then search the memory bank for the block requested and, if found, grants the desired block to the caller. Again, there is another program called the garbage collector ; it plays whenever a node is no more in use; it returns the unused node to the memory bank. It may be noted that memory bank is basically a list of memory spaces which is available to a programmer. Such a memory management is known as dynamic memory management . The dynamic representation of linked list uses the dynamic memory management.

7. A list of available memory spaces in the memory bank is stored in an array called AVAIL . For a request of a node, the list AVAIL is searched for the block of right size. If AVAIL is not null or if the desired size is not found, the memory manager will return a null response. Suppose the block XY is found and let it be XY. Then the memory manager grants this block of XY to the caller in a temporary buffer, say NEW. The newly available node XY then inserted into the linked list by changing the pointers of the concerned nodes. In Figure 3.4(a), the node XY is inserted at the end and change of pointers is shown by the dotted arrows. Figure 3.4(b) explains the mechanism of how a node can be returned from the linked list to the memory bank. "The pointers which are required to be manipulated while returning a node are shown with dotted arrows. Note that such allocations or deallocations are carried out by changing the pointers only."

8. Operations on a Single Linked List The operations possible on a single linked list are listed below: Traversing the list Inserting a node into the list Deleting a node from the list Copying the list to make a duplicate of it Merging the linked list with another one to make a larger list Searching for an element in the list. We will assume the following convention in our subsequent discussions: suppose X is a pointer to a node. The values in the DATA field and LINK field will be denoted by XDATA and XLINK, respectively. We will write NULL to imply null value in the DATA and LINK fields.

9. Traversing a single linked list In traversing a single linked list, we visit every node in the list starting from the first node to the last node. The following is the algorithm Traverse_SL for the same. Algorithm Traverse_SL Input: HEADER is the pointer to the header node. Output: According to the Process() Data structures: A single linked list whose address of the starting node is known from the HEADER. Steps: ptr = HEADER → LINK   // ptr is to store the pointer to a current node While ( ptr ≠ NULL) do   // Continue till the last node   Process( ptr )   // Perform Process() on the current node    ptr = ptr → LINK   // Move to the next node EndWhile Stop Note: A simple operation, namely Process(), may be devised to print the data content of a node, or count the total number of nodes, etc.

10. Inserting a node into a single linked list There are various positions where a node can be inserted: ( i ) Inserting at the front (as a first element) (ii) Inserting at the end (as a last element) (iii) Inserting at any other position. Before we discuss these insertions, let us assume a procedure GetNode (NODE) to get a pointer of a memory block which suits the type NODE. The procedure may be defined as follows: Note: The GetNode () procedure as defined above is just to understand how a node can be allocated from the available storage space. In C, C++, and Java, there is a library routine for doing the same such as alloc (), malloc() (in C, C++), new (in C++, Java).

11. Procedure GetNode Input: NODE is the type of the data for which a memory has to be allocated. Output: Return a message if the allocation fails else the pointer to the memory block allocated. Steps: If (AVAIL = NULL)   // AVAIL is the pointer to the pool of free storage   Return(NULL)   Print "Insufficient memory: Unable to allocate memory" Else   // Sufficient memory is available    ptr = AVAIL  // Start from the location, where AVAIL points   While ( SizeOf ( ptr ) ≠ SizeOf (NODE)) and ( ptr → LINK ≠ NULL) do      // Till the desired block is found or the search reaches the end of the pool     pr1 = ptr   // To keep the track of the previous block      ptr = ptr → LINK   // Move to the next block    EndWhile   If ( SizeOf ( ptr ) = SizeOf (NODE))  // Memory block of right size is found     pr1 → LINK = ptr → LINK   // Update the AVAIL list     Return( ptr )   Else     Print "The memory block is too large to fit"     Return(NULL)    EndIf EndIf Stop

12. Inserting a node at the front of a single linked list The algorithm InsertFront_SL is used to insert a node at the front of a single linked list. Algorithm InsertFront_SL Input: HEADER is the pointer to the header node and X is the data of the node to be inserted. Output: A single linked list with a newly inserted node at the front of the list. Data structures: A single linked list whose address of the starting node is known from the HEADER.

13. Steps: new = GetNode (NODE) // Get a memory block of type NODE and store its pointer in new If (new == NULL) then // Memory manager returns NULL on searching the memory bank Print "Memory underflow: No insertion" Exit // Quit the program Else new→LINK = HEADER→LINK // Change of pointer 1 as shown in Figure 3.5(a) new→DATA = X // Copy the data X to newly availed node HEADER→LINK = new // Change of pointer 2 as shown in Figure 3.5(a) EndIf Stop

14. Inserting a node at the end of a single linked list The algorithm InsertEnd_SL is used to insert a node at the end of a single linked list. Algorithm InsertEnd_SL Input: HEADER is the pointer to the header node and X is the data of the node to be inserted. Output: A single linked list with a newly inserted node having data X at the end of the list. Data structures: A single linked list whose address of the starting node is known from the HEADER.

15. Steps: new = GetNode (NODE) // Get a memory block of type NODE and return its pointer as new If (new == NULL) then // Unable to allocate memory for a node Print "Memory is insufficient: Insertion is not possible" Exit // Quit the program Else ptr = HEADER // Start from the HEADER node While ( ptr→LINK ≠ NULL) do // Move to the end ptr = ptr→LINK // Change pointer to the next node EndWhile ptr→LINK = new // Change the link field of last node // Pointer 1 as in Figure 3.5(b) new→DATA = X // Copy the content X into the new node new→LINK = NULL // Change of new link as last node EndIf Stop

16. Inserting a node into a single linked list at any position in the list The algorithm InsertAny_SL is used to insert a node into a single linked list at any position in the list. Algorithm InsertAny_SL Input: HEADER is the pointer to the header node, X is the data of the node to be inserted, and KEY being the data of the key node after which the node has to be inserted. Output: A single linked list enriched with newly inserted node having data X after the node with data KEY. Data structures: A single linked list whose address of the starting node is known from the HEADER.

17. Steps: new = GetNode (NODE) // Get a memory block of type NODE and returns its pointer as new If (new == NULL) then // Unable to allocate memory for a node Print "Memory is insufficient: Insertion is not possible“ Exit   // Quit the program Else ptr = HEADER   // Start from the HEADER node While ( ptr→DATA ≠ KEY) and ( ptr→LINK ≠ NULL) do // Move to the node having data as KEY or at the end if KEY is not in the list ptr = ptr→LINK   EndWhile If ( ptr→LINK = NULL) then   // Search fails to find the KEY.   Print “KEY is not available in the list”   Exit  Else    new→LINK = ptr→LINK  // Change the pointer 1 as shown in Figure 3.5(c)    new→DATA = X  // Copy the content into the new node    ptr→LINK = new  // Change the pointer 2 as shown in Figure 3.5(c)   EndIf EndIf Stop

18. Deleting a node from a single linked list Like insertions, there are also three cases of deletions: ( i ) Deleting from the front of the list (ii) Deleting from the end of the list (iii) Deleting from any position in the list Let us consider the procedure for various cases of deletion. We will assume a procedure, namely ReturnNode ( ptr ) which returns a node having pointer ptr to the free pool of storage. The procedure ReturnNode ( ptr ) is defined as follows:

19. Procedure ReturnNode Input: PTR is the pointer of a node to be returned to a list pointed by the pointer AVAIL. Output: The node is inserted into the list AVAIL at the end. Steps: 1. ptr1 = AVAIL  // Start from the beginning of the free pool 2. While (ptr1→LINK ≠ NULL) do 3.  ptr1 = ptr1→LINK 4.  EndWhile 5. ptr1→LINK = PTR   // Insert the node at the end 6. PTR→LINK = NULL   // Node inserted is the last node 7. Stop Note: The procedure ReturnNode () inserts the free node at the end of the pool of free storage whose header address is AVAIL. Alternatively, we can insert the free node at the front or at any position of the AVAIL list which is left as an exercise for the student. In C and C++ this procedure is realized as a library routine free().

20. Deleting the node at the front of a single linked list The algorithm DeleteFront_SL is used to delete the node at the front of a single linked list. Such a deletion operation is explained in Figure 3.6(a). Algorithm DeleteFront_SL Input: HEADER is the pointer to the header node. Output: A single linked list after eliminating the node at the front of the list. Data structures: A single linked list whose address of the starting node is known from the HEADER. Steps: 1.  ptr = HEADER→LINK  // Pointer to the first node 2. If ( ptr = NULL) then   // If the list is empty 3.  Print “The list is empty: No deletion” 4.  Exit   // Quit the program 5. Else   // The list is not empty 6.  ptr1 = ptr→LINK   // ptr1 is the pointer to the second node, if any 7.  HEADER→LINK = ptr1   // Next node becomes the first node as in Figure 3.6(a) 8.   ReturnNode ( ptr )   // Deleted node is freed to memory bank for future use 9.  EndIf 10. Stop

21. Deleting the node at the end of a single linked list The algorithm DeleteEnd_SL is used to delete the node at the end of a single linked list. This is shown in Figure 3.6(b). Algorithm DeleteEnd_SL Input: HEADER is the pointer to the header node. Output: A single linked list after eliminating the node at the end of the list. Data structures: A single linked list whose address of the starting node is known from the HEADER. Steps: ptr = HEADER             // Move from the header node If ( ptr→LINK = NULL) then   Print "The list is empty: No deletion possible"   Exit Else   While ( ptr→LINK ≠ NULL) do     ptr1 = ptr           // To store the previous pointer      ptr = ptr→LINK         // Move to the next    EndWhile   ptr1→LINK = NULL      // Last but one node becomes the last node as in Figure 3.6(b)    ReturnNode ( ptr )       // Deleted node is returned to the memory bank for future use EndIf Stop

22. Deleting the node from any position of a single linked list The algorithm DeleteAny_SL is used to delete a node from any position in a single linked list. This is illustrated in Figure 3.6(c). Algorithm DeleteAny_SL Input: HEADER is the pointer to the header node, KEY is the data content of the node to be deleted. Output: A single linked list except the node with data content as KEY. Data structures: A single linked list whose address of the starting node is known from the HEADER.

23. Steps: ptr1 = HEADER              // Start from the header node ptr = ptr1→LINK // ptr = HEADER →LINK    // This points to the first node, if any While ( ptr ≠ NULL) do   If ( ptr→DATA ≠ KEY) then   // If not found the key     ptr1 = ptr        // Keep a track of the pointer of the previous node      ptr = ptr→LINK         // Move to the next   Else     ptr1→LINK = ptr→LINK    // Link field of the predecessor is to point the successor of node under deletion, see Figure 3.6(c)      ReturnNode ( ptr )        // Return the deleted node to the memory bank     Exit                 // Exit the program    EndIf EndWhile If ( ptr = NULL) then        // When the desired node is not available in the list   Print "Node with KEY does not exist: No deletion" EndIf Stop

24. Copying a single linked list For a given list we can copy it into another list by duplicating the content of each node into the newly allocated node. The following is an algorithm to copy an entire single linked list. Deep copy of a Linked List means we do not copy the references of the nodes of the original Linked List rather for each node in the original Linked List a new node is created.

25. Algorithm Copy_SL Input: HEADER is the pointer to the header node of the list. Output: HEADER1 is the pointer to the duplicate list. Data structures: Single linked list structure. Steps: ptr = HEADER                // Current position in the master list HEADER1 = GetNode (NODE)     // Get a node for the header of the duplicate list ptr1 = HEADER1          // ptr1 is the current position in the duplicated list ptr1→DATA = NULL        // Header node does not contain any data While ( ptr ≠ NULL) do       // Till the traversal of master node is finished   new = GetNode (NODE)    // Get a new node from memory bank    new→DATA = ptr→DATA   // Copy the content   ptr1→LINK = new      // Insert the node at the end of the duplicate list    new→LINK = NULL   ptr1 = new    ptr = ptr→LINK       // Move to the next node in the master list EndWhile Stop

26. Merging two single linked lists into one list Suppose two single linked lists, namely L1 and L2 are available and we want to merge the list L2 after L1. Also assume that, HEADER1 and HEADER2 are the header nodes of the lists L1 and L2, respectively. Merging can be done by setting the pointer of the link field of the last node in the list L1 with the pointer of the first node in L2. The header node in the list L2 should be returned to the pool of free storage. Merging two single linked lists into one list is illustrated in Figure 3.7.

27. Algorithm Merge_SL Input: HEADER1 and HEADER2 are the pointers to the header nodes of lists (L1 and L2, respectively) to be merged. Output: HEADER is the pointer to the resultant list. Data structures: Single linked list structure. Steps: ptr = HEADER1 While ( ptr→LINK ≠ NULL) do      // Move to the last node in the list L1    ptr = ptr→LINK EndWhile ptr→LINK = HEADER2→LINK    // Last node in L1 points to the first node in L2 ReturnNode (HEADER2)       // Return the header node to the memory bank HEADER = HEADER1         // HEADER becomes the header node of the merged list Stop

28. Searching for an element in a single linked list The algorithm Search_SL () is given below to search an item in a single linked list. Algorithm Search_SL Input: KEY, the item to be searched. Output: LOCATION, the pointer to a node where the KEY belongs to or an error message. Data structures: A single linked list whose address of the starting node is known from HEADER. Steps: ptr = HEADER→LINK        // Start from the first node flag = 0, LOCATION = NULL While ( ptr ≠ NULL) and (flag = 0) do   If ( ptr→DATA = KEY) then   // Search is finished     flag = 1     LOCATION = ptr     Print "Search is successful"     Return (LOCATION)   Else      ptr = ptr→LINK       // Move to the next node    EndIf EndWhile If ( ptr = NULL) then   Print "Search is unsuccessful" EndIf Stop

29. CIRCULAR LINKED LIST In our previous discussion, we have noticed that in a single linked list, the link field of the last node is null (hereafter a single linked list may be read as ordinary linked list), but a number of advantages can be gained if we utilize this link field to store the pointer of the header node. A linked list where the last node points the header node is called the circular linked list. Figure 3.8 shows a pictorial representation of a circular linked list. Circular linked lists have certain advantages over ordinary linked lists. Some advantages of circular linked lists are discussed below: Accessibility of a member node in the list In an ordinary list, a member node is accessible from a particular node, if keys match from that node only. But in a circular linked list, every member node is accessible from any node by merely chaining through the list.

30. Suppose, we are manipulating some information which is stored in a list. Also, think of a case where for a given data, we want to find the earlier occurrence(s) as well as post occurrence(s). Post occurrence(s) can be traced out by chaining through the list from the current node irrespective of whether the list is maintained as a circular linked or an ordinary linked list. In order to find all the earlier occurrences, in case of ordinary linked lists, we have to start our traversing from the header node at the cost of maintaining the pointer for the header in addition to the pointers for the current node and another for chaining. But in the case of a circular linked list, one can trace out the same without maintaining the header information, rather maintaining only two pointers. Note that in ordinary linked lists, one can chain through left to right only whereas it is virtually in both the directions for circular linked lists.

31. Null link problem The null value in the link field may create some problem during the execution of programs if proper care is not taken. This is illustrated below by mentioning two algorithms to perform search on ordinary linked lists and circular linked lists. Algorithm Search_SL Input: KEY the item to be searched. Output: Location, the pointer to a node where KEY belongs or an error message. Data structures: A single linked list whose address of the starting node is known from the HEADER. Steps: ptr = HEADER→LINK While ( ptr ≠ NULL) do   If ( ptr→DATA ≠ KEY) then      ptr = ptr→LINK   Else     Print "Search is successful"     Return ( ptr )    EndIf EndWhile If ( ptr = NULL) then   Print "The entire list has traversed but KEY is not found" EndIf Stop

32. Note: In the algorithm Search_SL , two tests in step 2 (while ( ptr ≠ NULL) and ( ptr→DATA ≠ KEY)) cannot be packed together because in that case there will be an execution error for ptr→DATA since it is not defined when ptr = NULL. But with a circular linked list, a very simple implementation is possible without any special care for the NULL pointer. As an illustration, the searching of an element in a circular linked list is given below: Algorithm Search_CL Input: KEY the item of search. Output: Location, the pointer to a node where KEY belongs or an error message. Data structures: A circular linked list whose address to the starting node is known from the HEADER.

33. Steps: ptr = HEADER→LINK While ( ptr→DATA ≠ KEY) and ( ptr ≠ HEADER) do    ptr = ptr→LINK EndWhile If ( ptr→DATA = KEY)   Return ( ptr ) Else   Print "Entire list is searched: KEY node is not found" EndIf Stop Some easy-to-implement operations Some operations can more easily be implemented with a circular linked list than with an ordinary linked list. Operations like merging (concatenation), splitting (decatenation), deleting, disposing of an entire list, etc. can easily be performed on a circular linked list.

34. Algorithm Merge_CL Input: HEADER1 and HEADER2 are the two pointers to header nodes. Output: A larger circular linked list containing all the nodes from lists HEADER1 and HEADER2. Data structures: Circular linked list structure. Steps: ptr1 = HEADER1→LINK ptr2 = HEADER2→LINK HEADER1→LINK = ptr2     // Pointer assignment (Figure 3.9) While (ptr2→LINK ≠ HEADER2) do   // Move to the node just preceding the node HEADER2   ptr2 = ptr2→LINK EndWhile ptr2→LINK = ptr1       // Pointer assignment (Figure 3.9) ReturnNode (HEADER2)    // Return the HEADER2 to the free storage pool Stop

35. One can easily compare the algorithm Merge_CL with the algorithm Merge_SL . In the algorithm Merge_SL , the entire list is needed to be traversed in order to locate the last node, which is not required in the algorithm Merge_CL . This implies that Merge_CL works faster than Merge_SL . Circular linked lists have some disadvantages as well. One main disadvantage is that without adequate care in processing, it is possible to get trapped into an infinite loop! This problem occurs when we are unable to detect the end of the list while moving from one node to the next. To get rid of this problem, we have to maintain a special node whose data content is possibly NULL, as such a node does not contain any valid information, so it is nothing but just a wastage of memory space.

36. DOUBLE LINKED LISTS In a single linked list one can move beginning from the header node to any node in one direction only (from left to right). This is why a single linked list is also termed a one-way list . On the contrary, a double linked list is a two-way list because one can move in either direction, either from left to right or from right to left. This is accomplished by maintaining two link fields instead of one as in a single linked list. A structure of a node for a double linked list is represented in Figure 3.10. From the figure, it can be noticed that two links, viz. RLINK and LLINK , point to the nodes on the right side and left side of the node , respectively. Thus, every node, except the header node and the last node, points to its immediate predecessor and immediate successor.

37. 3.4.1 Operations on a Double Linked List All the operations as mentioned for a single linked list can be implemented more efficiently using a double linked list. In this section, only the insertion and deletion operations are discussed. Other operations like traversing, copying, merging, etc. are kept for the reader as exercises. Inserting a node into a double linked list Figure 3.11 shows a schematic representation of various cases of inserting a node into a double linked list. Let us consider the algorithms of various cases of insertion. ( i ) Inserting a node in the front The algorithm InsertFront_DL is used to define the insertion operation in a double linked list. Algorithm InsertFront_DL Input: X is the data content of the node to be inserted. Output: A double linked list enriched with a node in the front containing data X. Data structure: Double linked list structure whose pointer to the header node is the HEADER .

38. Operations on a Double Linked List Steps: ptr = HEADER → LINK   // Points to the first node new = GetNode (NODE)    // Avail a new node from the memory bank If (new ≠ NULL) then new → LLINK = HEADER     // Newly inserted node points the header as its left node HEADER → RLINK = new    // Header now points to the new node new → RLINK = ptr    // See the change in pointer shown as 3 in Figure 3.11(a) ptr → LLINK = new    // See the change in pointer shown as 4 in Figure 3.11(a) new → DATA = X   // Copy the data into the newly inserted node Else Print “Unable to allocate memory: Insertion is not possible” EndIf Stop

39. Inserting a node at the end The algorithm InsertEnd_DL is to insert a node at the end into a double linked list. Algorithm InsertEnd_DL Input : X is the data content of the node to be inserted. Output : A double linked list enriched with a node containing data X at the end of the list. Data structure : Double linked list structure whose pointer to the header node is the HEADER.

40. Steps: 1.  ptr = HEADER 2. While ( ptr → RLINK ≠ NULL) do   // Move to the last node 3.   ptr = ptr → RLINK 4.  EndWhile 5. new = GetNode (NODE)   // Avail a new node from the memory bank 6. If (new ≠ NULL) then   // If the node is available 7.  new → LLINK = ptr    // Change the pointer shown as 1 in Figure 3.11(b) 8.   ptr → RLINK = new   // Change the pointer shown as 2 in Figure 3.11(b) 9.  new → RLINK = NULL   // Make the new node as the last node 10.  new → DATA = X   // Copy the data into the new node 11. Else 12.  Print “Unable to allocate memory: Insertion is not possible” 13.  EndIf 14. Stop

41. Inserting a node at any position in the list The algorithm InsertAny_DL is used to insert a node at any position into a double linked list. Algorithm InsertAny_DL Input : X is the data content of the node to be inserted, and KEY the data content of the node after which the new node is to be inserted. Output : A double linked list enriched with a node containing data X after the node with data KEY. If KEY is not present in the list then it is inserted at the end. Data structure : Double linked list structure whose pointer to the header node is the HEADER.

42. Steps: 1.  ptr = HEADER 2. While ( ptr → DATA ≠ KEY) and ( ptr → RLINK ≠ NULL)   // Move to the key node if current node is not the KEY node or if the list reaches the end 3.   ptr = ptr → RLINK 4.  EndWhile 5. new = GetNode (NODE)   // Get a new node from the pool of free storage 6. If (new = NULL) then   // When the memory is not available 7.  Print (Memory is not available) 8.  Exit   // Quit the program 9.  EndIf 10. If ( ptr → RLINK = NULL) then   // If the KEY is not found in the list and reaches the last node 11.  new → LLINK = ptr // Insert the new node at the last 12.   ptr → RLINK = new 13.  new → RLINK = NULL // Make the new node as the last node 14.  new → DATA = X   // Copy the information to the newly inserted node 15. Else   // The KEY is available and inserting the new node after the KEY node 16.  ptr1 = ptr → RLINK   // Next node after the key node 17.  new → LLINK = ptr    // Change the pointer shown as 2 in Figure 3.11(c) 18.  new → RLINK = ptr1   // Change the pointer shown as 4 in Figure 3.11(c) 19.   ptr → RLINK = new   // Change the pointer shown as 1 in Figure 3.11(c) 20.  ptr1 → LLINK = new   // Change the pointer shown as 3 in Figure 3.11(c) 21.   ptr = new   // This becomes the current node 22.  new → DATA = X   // Copy the content to the newly inserted node 23.  EndIf 24. Stop

43. Note: Observe that the algorithm InsertAny_DL will insert a node even the KEY node does not exist. In that case, the node will be inserted at the end of the list. Also, note that the algorithm will work even if the list is empty. Deleting a node from a double linked list Deleting a node from a double linked list may take place from any position in the list, as shown in Figure 3.12. Let us consider each of those cases separately. (a) Deleting a node from the front of a double linked list The algorithm DeleteFront_DL is defined below to delete a node from the front of a double linked list. Algorithm DeleteFront_DL Input : A double linked list with data. Output : A reduced double linked list. Data structure : Double linked list structure whose pointer to the header node is the HEADER.

44. Steps: 1.  ptr = HEADER → RLINK   // Pointer to the first node 2. If ( ptr = NULL) then   // If the list is empty 3.  Print “List is empty: No deletion is made” 4.  Exit 5. Else 6.  ptr1 = ptr → RLINK   // Pointer to the second node 7.  HEADER → RLINK = ptr1   // Change the pointer shown as 1 in Figure 3.12(a) 8.  If (ptr1 ≠ NULL)   // If the list contains a node after the first node of deletion 9.   ptr1 → LLINK = HEADER   // Change the pointer shown as 2 in Figure 3.12(a) 10.   EndIf 11.   ReturnNode ( ptr )   // Return the deleted node to the memory bank 12.  EndIf 13. Stop Note: The algorithm DeleteFront_DL works even if the list is empty.

45. (b) Deleting a node at the end of a double linked list Algorithm DeleteEnd_DL Input : A double linked list with data. Output : A reduced double linked list. Data structure : Double linked list structure whose pointer to the header node is the HEADER. Steps: 1.  ptr = HEADER 2. While ( ptr → RLINK ≠ NULL) do   // Move to the last node 3.   ptr = ptr → RLINK 4.  EndWhile 5. If ( ptr = HEADER) then   // If the list is empty 6.  Print “List is empty: No deletion is made” 7.  Exit   // Quit the program 8. Else 9.  ptr1 = ptr → LLINK   // Pointer to the last but one node 10.  ptr1 → RLINK = NULL   // Change the pointer shown as 1 in Figure 3.12(b) 11.   ReturnNode ( ptr )   // Return the deleted node to the memory bank 12.  EndIf 13. Stop

46. (c) Deleting a node from any position in a double linked list Algorithm DeleteAny_DL Input : A double linked list with data, and KEY, the data content of the key node to be deleted. Output : A double linked list without a node having data content KEY, if any. Data structure : Double linked list structure whose pointer to the header node is the HEADER.

47. Steps: 1.  ptr = HEADER → RLINK   // Move to the first node 2. If ( ptr = NULL) then 3.  Print “List is empty: No deletion is made” 4.  Exit   // Quit the program 5.  EndIf 6. While ( ptr → DATA ≠ KEY) and ( ptr → RLINK ≠ NULL) do   // Move to the desired node 7.   ptr = ptr → RLINK 8.  EndWhile 9. If ( ptr → DATA = KEY) then   // If the node is found 10.  ptr1 = ptr → LLINK   // Track the predecessor node 11. ptr2 = ptr ->RLINK // Track the successor node 12. ptr1->RLINK = ptr2 // Change the pointer shown as 1 in Figure 3.12(c) 13. If (ptr2 ≠ NULL) then // If the deleted node is the last node 14. ptr2->LLINK = ptr1 // Change the pointer shown as 2 in Figure 3.12(c) 15. EndIf 16. ReturnNode ( ptr ) // Return the free node to the memory bank 17. Else 18. Print "The node does not exist in the given list" 19. EndIf 20. Stop

48. 3.5 CIRCULAR DOUBLE LINKED LIST The advantages of both double linked list and circular linked list are incorporated into another type of list structure called circular double linked list and it is known to be the best of its kind. Figure 3.13 shows a schematic representation of a circular double linked list. Here, note that the RLINK (right link) of the rightmost node and LLINK (left link) of the leftmost node contain the address of the header node; again the RLINK and LLINK of the header node contain the address of the rightmost node and the leftmost node, respectively. An empty circular double linked list is represented as shown in Figure 3.14 . In case of an empty list, both LLINK and RLINK of the header node point to itself.

49. 3.5.1 Operations on Circular Double Linked List All the regular operations like inserting, deleting, traversing, searching, merging, splitting, disposing, etc. can be implemented very easily with a circular linked list. Implementations of the said operations are left as an exercise for the reader. Here, only the sort operation is illustrated. Sorting operation with a circular double linked list The algorithm Sort_CDL shows the sorting of elements stored in a circular double linked list. Algorithm Sort_CDL ( ) Input: A circularly double linked with elements. Output: Sorted version of the circularly double linked list. Data structures: Circular double linked list structure with HEADER being the pointer of the header node.

50. Steps: ptrBeg = HEADER->LLINK // Pointer to the first node — the beginning node ptrEnd = HEADER->RLINK // Pointer to the last node — the ending node While ( ptrBeg ≠ ptrEnd ) do // To traverse the entire list — outer loop ptr1 = ptrBeg ptr2 = ptr1->RLINK While (ptr2 ≠ ptrEnd ) do // For compare and interchange — inner loop If Order(ptr1->DATA, ptr2->DATA) = FALSE then Swap (ptr1, ptr2) // Interchange the data content at ptr1 and ptr2 EndIf ptr1 = ptr1->RLINK // Move the first pointer to the next ptr2 = ptr2->RLINK // Move the second pointer to the next EndWhile ptrEnd = ptrEnd ->LLINK // Rightmost node is now sorted out EndWhile Stop

51. In the above algorithm, we have assumed the procedure Order(data1, data2) to test whether two data are in a desired order or not; it will return TRUE if they are in order else FALSE. We also assume another procedure Swap(ptr1, ptr2) to interchange the data contents at the nodes pointed by the pointers ptr1 and ptr2. These procedures are simple to implement and their implementation is left to students. The above algorithm uses the bubble sorting technique. The execution of each outer loop bubbles up the largest node towards the right end of sorting (say, in ascending order) and each inner loop is used to compare the successive nodes and push up the largest towards the right if they are not in order. Figure 3.15 illustrates the sorting procedure. Students may see whether the algorithm Sort_CDL is also applicable to the double linked list data structure or not.

52. Stack - Linked List Implementation To implement a stack using a singly linked list, we follow the LIFO (Last In, First Out) principle by inserting and removing elements from the head of the list, where each node stores data and a pointer to the next node. In the stack Implementation, a stack contains a top pointer. which is the "head" of the stack where pushing and popping items happens at the head of the list. The first node has a null in the link field and second node-link has the first node address in the link field and so on and the last node address is in the "top" pointer. The main advantage of using a linked list over arrays is that it is possible to implement a stack that can shrink or grow as much as needed. Using an array will put a restriction on the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocated. so overflow is not possible.

53. Stack Operations push():  Insert a new element into the stack ( i.e just insert a new element at the beginning of the linked list.) pop():  Return the top element of the Stack ( i.e simply delete the first element from the linked list.) peek():  Return the top element. display():  Print all elements in Stack. Peek Operation Check if there is any node present or not, if not then return. Otherwise return the value of top node of the linked list Display Operation Take a temp node and initialize it with top pointer  Now start traversing temp till it encounters NULL Simultaneously print the value of the temp node

54. Push Operation Initialise a node Update the value of that node by data i.e. node->data = data Now link this node to the top of the linked list And update top pointer to the current node Pop Operation First Check whether there is any node present in the linked list or not, if not then return Otherwise make pointer let say temp to the top node and move forward the top node by 1 step Now free this temp node

55. Time Complexity:  O(1), for all push(), pop(), and peek(), as we are not performing any kind of traversal over the list. Auxiliary Space:  O(n), where n is the size of the stack Benefits of implementing a stack using a singly linked list Dynamic memory allocation : The size of the stack can be increased or decreased dynamically by adding or removing nodes from the linked list, without the need to allocate a fixed amount of memory for the stack upfront. Efficient memory usage:  Since nodes in a singly linked list only have a next pointer and not a prev pointer, they use less memory than nodes in a doubly linked list. Easy implementation : Implementing a stack using a singly linked list is straightforward and can be done using just a few lines of code. Versatile : Singly linked lists can be used to implement other data structures such as queues, linked lists, and trees.

56. Real time examples of stack Stacks are used in various real-world scenarios where a last-in, first-out (LIFO) data structure is required. Here are some examples of real-time applications of stacks: Function Call Stack:  When a function is called, its return address and parameters are pushed onto the stack. The stack ensures functions execute and return in reverse order.. Undo/Redo Operations:  In apps like text or image editors, actions are pushed onto a stack. Undo removes the last action, while redo restores it. Browser History:  Browsers use stacks to track visited pages. Visiting a page pushes its URL onto the stack, and the "Back" button pops the last URL to go to the previous page. Expression Evaluation:  In compilers, expressions are converted to postfix notation and evaluated using a stack. Call Stack in Recursion:  Recursive function calls are pushed onto the stack. Once recursion ends, the stack is popped to return to the previous function call.

57. Queue - Linked List Implementation we maintain two pointers, front and rear . The front points to the first item of the queue and rear points to the last item. enQueue (): This operation adds a new node after the rear and moves the rear to the next node. deQueue (): This operation removes the front node and moves the front to the next node. Time Complexity:  O(1), The time complexity of both operations enqueue() and dequeue() is O(1) as it only changes a few pointers in both operations Auxiliary Space:  O(1), The auxiliary Space of both operations enqueue() and dequeue() is O(1) as constant extra space is required

58. Follow the below steps to solve the problem: Create a class Node with data members integer data and Node* next A parameterized constructor that takes an integer x value as a parameter and sets data equal to x   and next as NULL Create a class Queue with data members Node front and rear Enqueue Operation with parameter x: Initialize Node* temp   with data = x If the rear is set to NULL then set the front and rear to temp   and return(Base Case) Else set rear next to   temp and then move rear to temp Dequeue Operation: If the front is set to NULL return(Base Case) Initialize Node temp   with front and set front to its next If the front is equal to NULL   then set the rear to NULL Delete temp from the memory

59. Adding two polynomials using Linked List Given  two polynomial  numbers represented by a linked list. The task is to  add  these lists meaning the coefficients with the same variable powers will be added. Note:  Given polynomials are sorted in  decreasing  order of power. Input: 5x 2 +4x+2 and 5x+5 = 5x 2 +9x+7 head1: [[5, 2], [4, 1], [2, 0]] head2: [[5, 1], [5, 0]] Output: [[5, 2], [9, 1], [7, 0]] Input: head1: [[5, 3], [4, 2], [2, 0]] head2: [[5, 1], [-5, 0]] Output: [[5, 3], [4, 2], [5, 1], [-3, 0]] Explanation: head1 can be represented as 5x 3 + 4x 2 + 2 , head2 can be represented as 5x - 5 , add both the polynomials to get 5^ 3 + 4x 2 + 5x - 3