Linked List- Searching into a Sorted List | Insertion | Data Structure & Algorithm

SEARCHING IN LINKED LIST

CASE : LIST Is Sorted Suppose the data in LIST are sorted. Again we search for ITEM in LIST by traversing the list using a pointer variable PTR and comparing ITEM with the contents INFO[PTR] of each node, one by one, of LIST. Now, however, we can stop once ITEM exceeds INFO[PTR]. The algorithm follows. Algorithm SRCHSL(INFO, LINK, START, ITEM, LOC) LIST is a sorted list in memory. This algorithm finds the location LOC of the node where ITEM first appears in LIST, or sets LOC = NULL. 1. Set PTR = START. 2. Repeat Step 3 while PTR != NULL 3. If ITEM less than INFO[PTR], then: Set PTR = LINK[PTR]. [PTR now points to next node.] Else if ITEM = INFO[PTR], then: Set LOC = PTR, and Exit. [Search is successful.] Else: Set LOC = NULL, and Exit. [ITEM now exceeds INFO[PTR]] [End of If structure.] [End of Step 2 loop.] 4. Set LOC = NULL. 5. Exit. The complexity of this algorithm is still the same as that of other linear search algorithms; that is. the worst-case running time is proportional to the number n of elements in LIST, and the average-case running time is approximately proportional to n/2. Recall that with a sorted linear array we can apply a binary search whose running time proportional to log2 n. On the other hand, a binary search algorithm cannot be applied to a sorted linked list, since there is no way of indexing the middle element in the list. This property is one of the main drawbacks in using a linked list as a data structure. INSERTION Inserting at the Beginning of a List Suppose our linked list is not necessarily sorted and there is no reason to insert a new node in any special place in the list. Then the easiest place to insert the node is at the beginning of the list. Algorithm INSFIRST(INFO, LINK, START, AVAIL, ITEM) This algorithm inserts ITEM as the first node in the list. 1. [OVERFLOW?] If AVAIL = NULL, then: Write: OVERFLOW, and Exit. 2. [Remove first node from AVAIL list.] Set NEW = AVAIL and AVAIL = LINK[AVAIL]. 3. Set INFO[NEW] = ITEM. [Copies new data into new node) 4. Set LINK[NEW] = START. [New node now points to original first node.) 5. Set START = NEW. [Changes START so it points to the new node.) 6. Exit. Inserting after a Given Node Suppose we are given the value of LOC where either LOC is the location of a LIST or LOC = NULL. The following is an algorithm which inserts ITEM into LIST so that ITEM follows node A or. when LOC = NULL, so that ITEM is the first node. Let N denote the new node (whose location is NEW). If LOC = NULL, N is inserted as the first node in LIST. Otherwise, we let node N point to Node B (which originally followed node A) by the assignment LINK[NEW] = LINK[LOC] and we let node A point to the new node N by the assignment LINK[LOC] = NEW Algorithm INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM) This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts ITEM as the first node when LOC = NULL. 1. [OVERFLOW?] If AVAIL = NULL, then: Write: OVERFLOW, and Exit. 2. [Remove first node from AVAIL list.] Set NEW = AVAIL and AVAIL = LINK[AVAIL]. 3. Set INFO[NEW] = ITEM. [Copies new data into new node.] 4. If LOC = NULL, then: [Insert as first node.] Set LINK[NEW] = START and START = NEW. Else: [Insert after node with location LOC.) Set LINK [NEW] = LINK[LOC] and LINK[LOC] = NEW. [End of If structure.] 5. Exit. Inserting into a Sorted Linked List FINDA(INFO, LINK, START, ITEM, LOC) This procedure finds the location LOC of the last node in a sorted list such that INFO[LOC] less than ITEM, or sets LOC = NULL. 1. [List empty?] If START = NULL, then: Set LOC = NULL, and Return. 2. [Special case?] If ITEM less than INFO[START], then: Set LOC = NULL, and Return. 3. Set SAVE = START and PTR = LINK[START]. [Initializes pointers.) 4. Repeat Steps 5 and 6 while PTR != NULL. 5. If ITEM less than INFO[PTR], then: Set LOC= SAVE, and Return. [End of If structure.] 6. Set SAVE = PTR and PTR = LINK[PTR]. [Updates pointers.] [End of Step 4 loop.] 7. Set LOC = SAVE. 8. Return. INSERT(INFO, LINK, START. AVAIL, ITEM) This algorithm inserts ITEM into a sorted linked list. 1. [Use algorithm to find the location of the node preceding ITEM.) Call FINDA(INFO, LINK, START, ITEM, LOC). 2. [Use Algorithm to insert ITEM after the node with location LOC.] Call INSLOC(INFO. LINK, START. AVAIL, LOC, ITEM). 3. Exit.

For more details click here