9.1 INTRODUCTION with character data, Searching refers to the operation of finding the Io. lection of items. ching frequently apply te a file o ina file F can contain many y determine the records in, in such a field are called keys or Sel 10 @ particular primary key, y value, pier will first9.2. SORTING La A be a list of elements Ay, Aye + 4q in memory. Sorting ; rearranging the contents of A so that they are increasing in order (nur that is, so that A, SA, $A; 5 SA, Since A has n elements, there are n! ways that the contents can appear i ! permutations of 1, 2..... m. Accordingly, each sorting nas £ precisely to the of these a! possib Example 9.1 Suppose an array DATA contains 8 elements as follows: | DATA: 77, 33, 44, 11, 88, 22, 66, 55 After sorting, DATA must appear in memory as follows: DATA: 11, 22, 33, 44, 55, 66, 77, 8B Since DATA consists of 8 elements, there are B! = 40 320 ways that th 22,..., BB can appear in DATA. . — Complexity of Sorting Algorithms ‘The complexity of a sorting algorithm measures the running time as a o be sorted. We note that each sorting algorithm S will be made ‘ items t r , A, contain the items to be sorted and B is an operations, where Ay, Az, au (a) Comparisons, which test whether Aj < Aj or test whether A; < Buco (b) Interchanges, which switch the contents of A; and A, or of A, and By (e) Assignments, which set B += Ayand then set Aj2= Bor Ajz= Ay = Normally, the complexity function measures only the number of of other operations is at most a constant factor of the number of comy There are two main cases whose complexity we will consider, the’ case, In studying the average case, we make the probabilistic assumption of the given n items are equally likely. (The reader is referred to Sec. discussion of complexity.) “a Previously, we have studied the bubble sort (Sec. 4.6), quicksort (S 7.10). The approximate number of comparisons and the order of comp are summarized in the following table:Worst Case Average Case (n= Babble Sort meh z= Ory rs nin+3) 7 Quacksont 5 = On?) LAn log n = Ofn log a) dn log n = Oin log n) = tn | a(n—1) | | ! | Oin log nj = bubble sort is a very slow way of that the average-case comple cate complexity in jog mn) to indie, ‘oruing: its main advantage is the simplicity af nity (nt log n) of heapsor is the same as that of seems quicker than quicksort (n”), However, ‘atc that quicksont is Superior fo heapsom except on rare occasions. Lower Bounds y ask whether thete is an algorithm which can sort. items in time of order less tam « number of comparisons in the worst case. for the algorithm S is equal: } to th 1 path in the decision tree T or, in other words, the depth D of the wee, Te ber of comparisons for the algorithm 5 is epalo tea tree T. i : 3 Of shows 2 decision tree T for sorting » = 3 items. Observe cinal nodes. The values of 2 and E for the tree follow: fs with N exterpal n than 2 external9.3 INSERTION SORT Suppose an array A with n clements A[L], A[2), ..., A[N] is in memory. The algorithm scans A from A[I] to A[N], inserting each element A[K] into its Proper | Previously sorted subarray A[1), A[2], .... A[K — I}. That i Pass 1, A[1) by itself is trivially sorted. Pass 2. A[2) is inserted cither before ‘or after A[1] so that: A[1], Al2) is Pass 3. A[3} is inserted into its proper place in A[1], A[2], that is, before A[I and A[2], or after A(2}, so that: A[1], A[2], A(3] is sorted. iL: Pass 4. A[4] is inserted into its proper place in ATL], A[2), A[3] so that: A[1], A[2]. A[3), A[4] is sorted. ALN] is inserted into its proper place in A[1], A(2} A(1), A[2), ..., A[N] is sorted. This sorting algorithm is frequently used when n is small. For example, tl popular with bridge players when they are first sorting their cards, 9 There remains only the problem of deciding how to insert AIK] in its p subarray A[1], A[2], ..., A[K - 1]. This can be accomplished by comp comparing A[K] with A[K — 2], comparing A[K] with A[K - 3], and so on3 Sorting and Searc clement Ald] such that AU] AK]. Then cach of the clements A[K — Mh AIK = 2). a AU lis moved forward one location, and AIK] is then inserted in the J + Ist position in the array. The algorithm is simplified if there always is an clement A(J] such that AU) < ALK}; otherwise we must constantly check to sce if we are comparing ATK) with A(1]. This condition can be accomplished by introducing a Sentinel element A[O] = —s (Or a very small number), —— Example 9.4 See Suppose an array A contains B elements as follosg: 77, 33, 44, 11, 88, 22, 66, 55 the insertion sort algorithm, the algorithm, and the arrow Figure 9.3 illustrates A(K] in each pass of ‘The circled element indicates the inserting A[K}. indicates the proper place for |_Pass [Alor Alt Alay AT Alt] AIS] |. ksi [uae on kez: | Kes: | Kaa: | — Kas: | -s | Kee: = n | Km: | Kee [ Sorted: | = The formal statement of our inse: ion sort algorithm follows, Algorithm 9.1; (Insertion Sort) TNSERTION(A, Nj, ‘This algorithm sorts the array A with N I. Set A[O] := —=, [Initializes 2. Repeat Steps 3 to 5 for K = 2, 3.srl astencen “ieee aan 9.4 SELECTION SORT Suppose an array A with m elements A[l], A(2]. algorithm for sorting A works as follows. First find the s first position. Then find the second smallest clement in the And so on, More precisely: Find the location LOC of the smallest in the list of N elements Af1], A[2]. .... AIN], and then interchange A[LOC] and A[1]. Then: Find the location LOC of the smallest in the sublist of N — 1 elem A[2], AGB], -..» ALN], and then interchange A[LOC) and A(2]. A[1], A(2] is sorted, since A[I] $ A[2]- ., A(N] is in memory. mallest element in the list list and put it in the Pass 1. Pass 2.— 2 and x ind the location LOC of the x pss STuallest in the Ssblist of N~2 elements, 4 AD). Ala), vv AUN], and thea interchen AILOCy and ay3), ties bs ~ AU, Alay, = ABD ed ns ah “— ; pas N=. Find the location 1, : op eee OC of the smaller f the elements ~1, ANI, inesshange AILOC and Aly tt ‘Thess SIN. AINI, an pe ATLL, AR}, ++ AIN] Sone, since ANN 1} < apy, a! Ths A is sorted after N— 1 passes, A ite ah c TWD re | Example 9.5 eS Suppose an array A contains g elemey Mts as follows: % 77,33, 44, 14, 88, 22, 66, 55 Applying the selection sort algorithm to 4 Yields the data in Fig. 9.4. LOC gives the location of the smallest among AIK), Ak + Ve ny Al The circled elements indicate the elements IN] duris Pass kK. which are to be interchamee oe = AIK] and LOC : Sach other element AU) as follows; {) If MIN < AUJ), then sim ©) TEMIN > AD), then o ply move to the next clement, Pdate MIN and LOC by SettingDato Structures the last element A(NI. MIN: will contain the s .. A[N] and LOC will contain its location. Jy as a procedure. After comparing MIN with elements A[K], A[K + 1], -- The above process will be stated separate! Procedure 9.2: MIN(A, K. N, LOC) Anarray A is in: memory. element among A[K], AIK + 1], -- 1. Set MIN := A[K] and LOC := K. [Initializes point z Repeat for J = K +1, K +2, oi If MIN > ALJ], then: Set MIN := ALJ] and LOC [End of loop.) 3. Return. ‘The selection sort algorithm can now be easily stated: Algorithm 9.3: (Selection Sort) SELECTION(A, N) This algorithm sorts the array A with N elements. 1. Repeat Steps 2 and 3 for K = 1, 2... N- 2. Call MIN(A, K, N, LOC). 3. [Interchange A{K] and A(LOC].] Set TEMP := A[K], A[K] := A[LOC] and All [End of Step | loop.] 7 F 4. Exit. irSORTING; BUBBLE SORT ‘A bea list of n numbers, Sorting A rele Bee ing refers to the operation of rearranging the elements of A so A[l] < AL2] < AI3] <... < AIN] example, suppose A originaily is the list “ 8, 4, 19,2, 7, 13, 5, 16 er sorting, A is the Tist 2,4, 5,7, 8.13, 16,19 to be a trivial task, Actually, sorting efficiently may be quite complicated. In many different sorting algorithms; some ‘of these algorithms are discussed im. and discuss a very simple sorting algorithm knowa as the bubble sort. of sorting refers to arranging numerical data in increasing order, this triction is only for notational convenience. Clearly, sorting may also mean arranging nul i «ae order of arranging non-numerical data in alphabetical order. ‘Actually, A is records, and sorting ‘A refers to rearranging the records of A so that the values Sorting may seem , there 9, Here we presen apter mark: The above definition ¢ ly a file of viven key are ordered. ubble Sort iit of numbers AUT], AUZI = rmeamory. The buble sort algoritin ate : uppose the _ ATN} ism follows:Step 1. Compare A[1] and A[2] and arrange them in the desired 0 ‘Then compare A(2) and A[3] and arrange them s0 that AL2) < ALS] A(3] and A[4] and arrange them so that A[3] < A[4]. tin ‘A(N — 1] with A[N] and arrange them so that A[N = 1) 27, interchange 51 and 27 as follows: 32, @)(G4) 85, 66. 23, 13, 57 (©) Compare A, and A,. Since 51 < 85, the st is not altered. (d) Compare A, and As Since 85 > 66, interchange B and 86 as follows: 32, 27, 5 (5) 23, 13,57 (e) Compare As and Ay. Since 85 > 23, interchange 8: and 23 as follows: | + 32, 27, $1, 65,23) @5)33. 57 x Since 85 > 13, interchange 85 and 13 to yield: 32, 27, 51, 66, 23,03) 65)57 ince 85 > 57, interchange 85 and 51 to yield: 32, 27, 51, 66, 23, 13, Suppose the foll (a) Compare Ay and Az. | (b) Compare A, and Aj. (f) Compare A, and Ay. (g) Compare A, and Aj. 51a e Last me of them has moved its way 23, $6. (13,) (23) 27, 33, 51, 57, 66, 85 oe UR "Pass 6 actually has two comparisons, A, with A, and A, and A3. The second comparison does not involve an interchange. 7, Finally, A, is compared with Aj. Since 13 < 23, no interchange | list has & elements; it is sorted after the seventh pas ‘the list was actually sorted after the sixth pass.Chapter Five Linked Lists 5.1 INTRODUCTION ‘The everyday usage of the term “list” refers wo a linear collection of data items. Figure $.Mah shows w shopping list; it contains a first clement, a second clement... and a last clement. F requently, we want to add items to or delete items from a list. Figure 5.1(b) shows the shopping list afer thrre ftems have been added at the end of the list and two others have been deleted (by Being crossed out).heer vcore Compute the address of an element in an array, On the other hand, y,, disadvantages—e p., it is felatively expensive to insert and delete elements jy 9 an alray usually occupies a block of memory space, one cannot simply double sy an array when additional space is required, (For this reason, arrays are called ./ said to be static data structures.) Another way of storing a list in memory is to have each element in the list ‘ontair a link or pointer, which contains the address of the neat element in the lic elements in the list need not occupy adjacent space in memory. This will mak: and delete elements in the list. Accordingly, if one were mainly interested in x data for inserting and deleting, as in word Processing, one would not store the d rather iin a list using pointers. This latter type of data structure is called a finkecd iss ., subject matter of this chapter. We also discuss circular lists and two-way lists—wt, Beneralizations of linked lists—and their advantages and disadvantages, 5.2 LINKED LISTS A linked list, or one-way list inear collection of data elements, called iodes, her order is given by means of pointers. That ix, each node is divided into wo parts: the Contains the information of the clement, and the second part, called the fink fleld ox field, contains the address of the next node in the list. _ Figure 5.2 is a schematic diagram of a linked list with 6 nodes. Each node is pict Parts. The left part represents the information Part of the node, which may contain an ¢ of data items (¢.g., NAME, ADDRESS,...). The Fight part represents the nexipointer {) node, and there [Link] arrow drawn from it to the neat node in the list This follows Practice of drawing an arrow from a field to a node whea the address of the node app: Biven ficld. The pointer of the last node contains a special value, called the mull pointer, stict ‘any invalid address. Noxipointer field ot wird node Information part ot third node Fig. 5.2 Linked List with 6 Nodes 0 or a negative number is used for the null pointer.) The null pointer. n WHE diagram, signals the end of the list. The linked list also contains a dist p0'™ led START or NAME—which contains the address of the first node in the lis he there is an arrow drawn from START to the first node, Clearly, we need only this addr: 4 START to trace through the list.’A special case is the list that has no nodes. Such a list is the null list or empty list and is denoted by the hull pointer in the variable START.a . Linked Lists ital wa i erates vant an lo 12 beds, of which 9 nt ft the pointer field, alee ote of ihe patents ths ie ar bea ae tient. Hence START contains swe, We athe vara TART pit : se the y baad i dams, occupies bed 5. | Also, Adams's pointer is e Dean's pointer is 11, Besar) Sele) Sites Deani thelnextipat ety forthe last patient (Sam s, the next patient, rete occupies bed 3; grows have been drawn to ee) Contains the null pointer, “ 11; and so on. The “ate the listin: , denoted by 0. (Some | ing of the first few pati | w patients.) bed | umber i er | Patient Nea sant [5 | i 1 | kirk Fi | = Samuels 5.3 REPRESENTATION OF LINKED LISTS IN MEMORY be maintained in memory, unless otherwise specified of hem-here INFO and Let LIST be a linked list. Then LIST will s—we will call t implied, as follows. First of all, LIST requires wo linear array’ 1 n a uch that INFO[K] and LINK[K] contain, respectively. the information part and the LIST also requires @ variable name—such as xipointer sentinel — field of a node of LIST. As n° we. | ic i Jocation of the beginnine which contains the locatio! " iby NULL—which indicates the end of the list. Since the 8 iti il choose NULL = 0, unless other’ ing of the list, and a ne) subscripts of the arrays INFO and ise stated. ——— rlee ‘examples of lt lists i nodes of a list need not oc followit of linked lists indicate that the e Epaa Sacen? INFO and LINK, and that more than one list may be maint linear arrays INFO and LINK. However, each list must have its own pointer variable » location of its first mode. Rabel = Tahoe = Figure 5.4 pictures a linked li single character. We can obtain the actual string, as follows: START = 9, so INFO[9] = N is the first character. UINK[9] = 3, so INFO[3] = 0 is the second character. rou] = 6, $0 INFO[6) = Gi (blank) is the third character. ] = 12, $0 INFO[11] = € is the fourth character. LINK[11] = 7, $0 INFO[7) = X is the fifth character. _ “HINK[7] = 10, go INFO[10] = 1 is the sixth character. LINK[10] = 4,50 INFO[4] = T is the seventh character. NULL value, so the list has ended. is. NO EXIT is the character string. INFO st in memory where each node of the list contains 3 I list of characters, or, in other words, theRE Achaia 5.5 SEARCHING A LINKED LIST Let LIST be a linked list in me information is given. This sec of. the node where ITEM first LIST are sorted, wher mory. stored as in Sees, 5.3 and 5.4. Suppose a spc tion discusses rwo searching algorithms for findin, appears in LIST. The first algorithm does not assum, reas the second algorithm does assume that LIST is sorted, If ITEM is actually a key value and we are searching through a file ITEM, then ITEM can Appear only once in LIST. LIST Is Unsorted for the record cx Suppose the data in LIST are not necessarily sorted, Then one searches for ITEM in List , traversing through the list using a pointer variable PTR and comparing ITEM with the INFO[PTR] of each node, one by one, of LIST. Before we update the pointer PTR by PTR == LINK(PTR] ‘We require two tests. First we have to check to sce whether we have reached the end of the list first we check to see whether PTR = NULL If not, then we check to see whether INFO[PTR] = ITEM ‘The two tests cannot be performed at the same time, since INFO[PTR] is not defined when PTR = NULL. Accordingly, we use the first test to control the execution Of a loop, and we let the second test take place inside the loop. The algorithm follows. on f ‘The complexity of this algorithm a Of the linear search algorithm for lin urrays discussed in Sec, 4,7. That is, the worst-exs ing time i Broportional tothe msnb=*# lements in LIST, and the average case “isae Peal eo a2 (with ‘condition that [TEM appears once in L ‘but with nade of LIST).__Linked Lists eS —__— a f the personnel file in Fig. 5.7. The follow: i i Consider t lowing module reads the social security umber NNN of an employee and then gives the emplayee a 5 percent increase in sila 4. Read: NNN. 2. Gall SEARCH(SSN, LINK, START, NNN, Loc) 3, IF LOC # NULL, then: Set SALARY(LOC] : = SALARY[LOC] + 0. O5+SALARY[LOC], | Write: NNN is not in file, | [End of If structure.) 4, Return. | | (The module takes care of the case in which there is an error in inputting the social security number.) LIST is Sorted Suppose the data in LIST are sorted. Again we search for ITEM in LIST by traversing the list sing 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. SRCHSL(INFO, LINK, START, ITEM, LOC) LIST is a sorted list in memory. This algorithm finds the location LOC of the r -ITEM first appears in LIST, or sets LOC = NULL. START... . Repeat Step 3 while PTR # NULL: < INFO[PTR], then: : Sa PTR := LINK[PTR). [PTR now points to next node.] if ITEM = INFO[PTR], then: 5 Set LOC := PTR. and Exit, [Search is successful.) _ “Set LOC := NULL, and Exit, [ITEM now exceeds INFO[PTRI If WFP] in AY ee Abputr vannoq wil 46be|pata Structures y a binary search wh orithm cannot be ap the list. This. prop ve can appl Recall iin vported Hinear array) WE bt pr os _ ee ‘On the other hand, binary search ner linked ri Pere igno way of indexing the middle cleme i ae in using @ linked list as 9 data structure- n Example 5.9 ‘i i ‘le in Fig. 5.7- The following module reads the name esate pe ae the employee a5 percent increase in salary (Compare with Example 5.8 ) 4. Read: EMPNAME. 2. Call SRCHSL(NAME,, LINK, START, EMPNAME, LOC). 3. If LOC 4 NULL, then: Set SALARY [LOC] := SALARY(LOC] + 0.05#SALARY! Ise: Write: EMPNAME is not in list. [End of If structure.) 4, Return. e can use the second search algorithm, Algorithm 5.3, since the Observe that now w list is sorted alphabetically. 5.6 MEMORY ALLOCATION; GARBAGE COLLECTION : in memory assumes the possibility of inserting new node lists and hence requires some mechanism which provides unused memory space for the new Analogously. some mechanism is required whereby the memory space ‘of deleted nodes becomes available for future use, These matters are discussed. in this section, while the general discussion of the inserting and deleting of nodes is postponed until later sections. Together with the linked lists in memory, a special list is maintained which consists of unused memory cells. This list, which has its own pointer, is called the /ist of available space or the free- storage list or the free pool. ; Severe oe linked. lists are’ implemented ‘by parallel arrays as described in the preceding _ fections, ang soruceslistertons ane eens are to be performed on our linked lists. Then the memory cel a Be Gee eae be a together to form a linked list using AVAIL . ree-storage list wi i Se - ae ill also be called the AVAIL list.) Such ‘The maintenance of linked IiLinked Lists e the list of patients in Example 5.1 js stored in the li x (s0 that the patient in bed K is assigned to BEDIK}). Then the seiable space in ihe linear array BED may be linked as in Fig. 5.9. Observe that GED(10) is the fist ble bed, BED[2] is the next available bed, and BED(6] is the last available bed Hence BED[6] has the null pointer in its nextpointer field; that is, LINK[6] = 0 BED LINK START niliare = 6 AVAIL jilable space in. the linear array TEST in Fig. 5.5 may be linked as in 10. Observe that each of the lists ALG and GEOM may use the AVAIL list. that AVAIL = 9, so TEST(9] is the first free node in the AVAIL list. Since AIL] = LINK(S] ~ 10, TEST[10] is the second free node in the AVATL list eer personnel file in Fig. 5.7. The available space in the linear array ay be linked as in Fig. 5.11. Observe that the free-storage list in NAME | of NAME(S], NAME[11]. NAME[13], NAME[5] and NAME([1]. Moreover, e that the values in LINK simultaneously list the free-storage space for MER in Fig. 5.6 may. be linked as in a four lists may use the AVAIL list for aa Structures oe E INFO START [2] ‘ Garbage Collection oI becomes reusable because a node is deleted from a list Suppose some memory space ; nt the space to be available for futu list is deleted from a program. Clearly, we wal to bring this about is to immediately reinsert the space into the free-storage list. _ will do when we implement jinked lists by means of linear arrays. However, this method too time-consuming for the operating system of a computer, which may choose an alter method, as follows. ‘The operating system of a computer may periodically collect all the deleted space onto the free. storage list. Any technique ‘which does this collection is called garbage collection. Garbage collection usually takes place in two steps. First the computer runs through all lists, tagging those ‘are currently in use, and then the computer runs through the memory, collecting all w ‘onto the free-storage list. The garbage collection may take place when there is only som: amount of space or no space at all left in the free-storage list, or when the CPU is idle and has time to do the collection, Generally speaking, the garbage collection is invisible to the programme’ Any further discussion about this topic of garbage collection lies beyond the scope of this text Overflow and Underflow Saeeng en data are soe inserted into a data structure but there is no available space, !-¢ .-storage list is empty. This situation is usually called overflow. The c y handle ae 5 immer may | pr by printing the message OVERFLOW. In such a case, the es a then modify ‘the program by adding space to the underlying arrays, Observe that overflow will occur with oul linked lists when AVAIL = NULL and there is an insertion. Analogously, the term underflow refers to the situation where one wants to delete data [ro"" * essage UNDERFLOW. Observe that jl m “ Sees Pe eacimmieennazeriuaeed ists een START =Linked Lists Ea) 57 INSERTION INTO A LINKED LIST inked li i as si Lt us ee meee succes ve nodes A and B, as pictured in Fig. 5.14(a). Suppose a t Hai ist between nodes A and B, The sche fg eae ee ae insertion appears.1n Fig, 5.14(b), That is, node A now points to Ce Se 2 onode B, to which A previously pointed. node N, and node N points START , Node A Node B Fela ee ee er START (a) Batore insertion 10 A Mode B BL mc co» {b) After insertion Fig. 5.14 Suppose our linked list is maintained in memory in the form LIST(INFO, LINK, START, AVAIL) Figure 5.14 does not take into account that the memory space for the N will come/frai thy AVAIL list. Specifically, for easier processing, the first node in the AVal a i for the new node N. Thus a more exact schematic diagram of such am inse Observe that three pointer fields are changed as follows: a The nextpointer field of node A now points to the new node N, to wi pointed. hich AVAIL previously _ Datalist—e eS the free pool, to which node N prey to which node A prey nts to the second node in pe field af node N now points to nade By ode N i the first node in the list, ther then N will co in th (2) AVAIL now (3). The nextpointer fi jal eases. If the new node * is the last node in the lit ‘There are also two speci point to N;. and if the new node N 9. 5.9, the alphabetical list of patients in a ward. Suppose 2 patient the ward, Observe that the first available bed. tween Green and Kirk. (a) Consider Fi Hughes js admitted to (i) Hughes is put in bed 10, a (ii) Hughes should be inserted into the list bet The three changes in the pointer fields follow. 4. LINK[8] = 10. [Now Green points to Hughes.] 2. LINK[10] = 1. [Now Hughes points to Kirk.] 3, AVAIL = 2. [Now AVAIL points to the next available bed.) (b) Consider Fig. 5.12, the list of brokers and their customers. Since the customer lists are not sorted, we will assume that each new customer is added to the beginning of fts list. Suppose Gordan is a new customer of Kelly. Observe that (8) Gordan is assigned to CUSTOMER(11], the first available node. (if) Gordan is inserted before Hunter, the previous first customer of Kelly. The three changes in the pointer fields follow: 4. POINT[2] = 11. [Now the list begins with Gordan.] 2. LINK(11] = 3. [Now Gordan points to Hunter.) 3, AVAIL = 18. [Now AVAIL points to the next available node.] Suppose the data elements A, B,C, D, E and F are inserted one after the other into the empty list in Fig. 5.13. Again we assume that each new node is _ inserted at the beginning of the list. Accordingly, after the six insertions, F will point to E, which points to 0, which points to C, which points to 8, which points to A; and A will contain the null pointer. Also, AVAIL = 7, the first available node after the six insertions, and START = 6, the location of the first node, F. Figure 5.16 shows the new list (where 1 = 10.) = insert nodes into linked lists come up in various situations. We discuss thr rt one inserts a node at the beginning of the list, the second one inserts 2.90" | given location, and the third one inserts 4 node into a sorted list. All 0 linked fist is in memory in the form LIST(UINFO, LINK. STAR! ITEM contains the new information to be added to the list. cA ipaseant rk 28.2 9Linked Lists ae INFO LINK STanT | 6 | = 1 | ‘Blaine 2|8 1 re 2 | avait | 7 lee Fig. 5.16 Since our insertion algorithms will use a nede in the AVAIL list, include the following steps: (a) Checking to sce if space is available in the AVAIL list. If not, that is, if AVAIL = NULL, then the algorithm will print the message OVERFLOW. (b) Removing the first node from the AVAIL Using the variable NEW to keep track of the location of the new node, this step can be implemented by the’ pair of assignments (in this order) I of the algorithms will NEW := AVAIL, AVAIL := LINK[AVAIL] (¢) Copying new information into the new node. In other words, INFO[NEW] ‘= ITEM The schematic diagram of the latter two steps is pictured in Fig. 5.17. NEW Frea-storage list Fig. 5.17 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. An ‘Iporithm that does so follows Fe: = eo. j schematic diagram of Steps ? and already been discussed, and the schematic diagra PS 2 and 3 appear. Fig S17, Theschecaic dlagran’ of Sicps 4 aad 5 oppears in Fig, 5.18. 3 (Consider the lists of tests in Fig. 5.10. Suppose the test score 75 is to be added to ‘the beginning of the geometry list. We simulate Algorithm 5,4. Observe that ITEM « 75, INFO TEST and START =GEOM, INSFIRST(TEST, LINK, GEOM, AVAIL, ITEM) 1. Since AVAIL # NULL, control is transferred to Step 2, 2, NEW = 9, then AVAIL = LINK[9] = 10. 3, TESTIS) - 75. ee te ok © bie aol tisk ___ figure 5.19 shows the data structure after 75 i, added to the list. Observe that only three pointers, are changed, AVAIL, GEOM and LINKS} a oes eh BiiiMmipse ts dase iE uci ee ¥, SIP alabos lt rains, pew g eg eee:a Linked Lists Inserting after a Given Node Suppose we are given the value of LOC where either LOC is the location of a node A in a linked UST 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, then N is inserted as the first node in LIST as in Algorithm 5.4. Otherwise, as pictured in Fig. 5.15, we let node N point to sede B (which originally followed node A) by the assignment = LINK[NEW] := LINK(LOC] node A point to the new node N by the assignment Bie ie LINK{LOC] -= NEW PP akeDota Structures FAIL = NULL, then: Write: OVERFL Oy, rn list.] L AVAIL LINK[AVAIL]. E - [Copies new data into new node | first node.) Suppose ITEM is to be inserted jnio a sorted linked LIST. Then ITEM must be inserted nodes A and B so that INFO(A) < ITEM $ INFO(B) The following is a procedure which finds the location LOC of nade A, that is. wliich finds 1 Jocation LOC of the last node in LIST whose yalue is less than ITEM. Traverse the list, using a pointer variable PTR and comparing ITEM with INFO[PTR] at each ‘node. While traversing, keep track of the location of the preceding node by using a pointer vant SAVE, as pictured in Fig. 5.20. Thus SAVE and PTR are updated by the assignments SAVE;= PTR and PTR := LINK(PTR) ‘START SAVE PTR pee et, Fig. 5.20 Pee ig comiindes as long as INFO[PTR] > ITEM, or in other words, the travers fons ITEMS IRFO(ETR| Then PTR piatsio node [Link] SAVE will contain d ‘The formal statement of our procedure follows. The cases where etl < ITEM < INFO|ST; Loc e the list is empty or wher Frees SA ae Tic ac LOG =INULL-faro/Lratod separately, since they do sot involve ty: 1g Stops as Location ofLinked Lists 5.23 4, Repeat Steps § and 6 w vi bes) IFITEM < INFOUPTR, ag a Set LOC := SAVE, and Return ie {End of If structure. 6. Set SAVE := PTR and c [End of Step 4 loop.} 7. ScuLOC := SAVE. 8. Return. PTR := LINK[PTRI. [Updates pointers.} ‘Now we have all the components to present an al, " h ; gorithm which inserts ITEM into a linked list. ‘The simplicity of the algorithm comes from using the previous two procedures INSERT(INFO, LINK, START, AVAIL, ITEM) ‘This algorithm inserts ITEM into a sorted linked list. [Use Procedure 5.6 to find the location of the node preceding ITEM i Call FINDA(INFO, LINK, START, ITEM, LOC). , [Use Algorithm 5.5 to insert ITEM after the node with location LOC.] Call INSLOC(INFO. LINK, START, AVAIL, LOC, ITEM). eee SE as" a Consider the alphabetized list of patients in Fig. 5.9. Suppose Jones is to be added to ‘the list of patients. We simulate Algorithm 5.7, or more specifically, we simulate Procedure 5.6 and then Algorithm 5.5. Observe that ITEM = Jones and INFO = BED. (8) FINDA(BED, LINK, START, ITEM, LOC) 1. Since START # NULL, control is transferred to Step 2. 2. Since BED[S] = Adams < Jones, control is transferred to Step 3. WE = 5 and PTR = LINK(5] = 3. 5 and 6 ate repeated as follows: ‘D[3] = Dean < Jones, so SAVE = 3 and PTR = LINK[3) = 11. Br, = Fields < Jones, so SAVE = 11. and PTR = UNK[11] = 8. ‘(c) BED(8] = Green < Jones, so SAVE = & and PTR = LINK[8] = 1. (4) Since BED[1} ~ Kirk » Jones, we have: LOC = SAVE = 8 and Return. D, LINK, START, AVAIL, LOC, ITEM) [Here LOC = 8) YALL # NULL, control is transferred to Step 2- 40 and AVAIL = LINK[10] = 2+Dota Structures NULL we have: bs i para Suki] = 1 and LINK[8] = NEW = 10. 5. Exit. e structui Jones is added to the patient list. we ee ee ie ee changed, AVAIL, LINK[10] and Linx em a BED LINK stant [5 | oan oa mae oD 3 HEE) | Copying ti ‘by simply choosing a variable name or pointer for the list, such as NAME, and then ‘overed in the problem sections. NAME := NULL. These algorithms are c 5.8 DELETION FROM A LINKED LIST Precedes the nade that is in memory in the form LISTUINFO, LINK, START, AVAIL) Suppose our linked list is maintainedSe = ‘START Boss hoe on (a) Bétore deletion 3 4 norm [me ee (b) After deletion Fig. 5.22 does not take into account the fact that, when a node N is deleted from our list, we will Figure 5.22 i return its memory space to the AVAIL list. Specifically, for easier processing. in will be returned to the beginning of the AVAIL list. Thus a more ‘exact schematic diagram of such a ‘deletion is thé One in Fig. 5.23. Observe that three pointer fields are changed as follows: (1) The nextpointer field of node A now points to node B, where node N previously pointed. a eae eine eld of N now pats Yo the original it node inthe ree pon ete AVAIL previously pointed. (3) AVAIL now points to the deleted node N. Data list Free-storage list Fig. 5.23 ed node N is the first jast node in the node in the list, then START will list, then node A will contain the cases. If the delet « deleted node N is the Ia : ail Dy oapital ward. Suppase Gree Se sae 52, te EIS Tt Ce ay re changes in the pointer fields must be executed: UNK[11] = 10 unk(s] = 2 Por 8 ‘ ds, who originally precede reen, now points t By the int ha Gen The second and third changes add the new bed to the AVAIL List. We emphasize that, before making the deletion, w to find the node BED(12], which © inally pointed to the deleted node (b) Consider Fig. 5.12, the list of brokers and their customers. Suppose ‘eller first customer of Nelson, is deleted from the list of customers. Then, in o maintain the linked lists. the following three changes in the pointer fields must be *porwits) = 10 UNE(S],= 14 AVATL = 9 By the first change, Nelson now points to his original second customer, Jones The second and third changes add the new empty node to the AVAIL list. (c) Suppose the data elements E, B and C are deleted, one after the other, from the list in Fig. 5.16. The new list 4s pictured in Fig. 5,24. Observe that now t! three available nodes are: INFO[3], which originally contained C INFO[2], which originally contained B INFO[s], which originally contained E Observe that the order of the nodes in the AVAIL list is th COCO ara ao al gc ore INFOLINK Fig. 5.24.= Linked Lists a adi few peletion Algorithms gorithms which delete nodes from linked lists ‘i coterie come up in various situations. We discuss two of here, The first one deletes the node following a given node, and the Td eee with a given ITEM of information. All a as pies in the form LIST(INFO, LINK, GRRE eee oa ce ieee all of - Ee Teturn the memory space of the deleted node N to the 7 oes . Accordingly, all of our algorithms will include the following pair of assignments, where is the location of the deleted node N: LINK[LOC] := AVAIL andthen AVAIL := LOC ‘These two operations are pictured in Fig. 5.25. Frea-storage list, Fig. 5.25 LINK[LOC] := AVAIL ond AVAIL := LOC a 5 3 Some of our algorithms may want to delete either the first node or the last node from the list. An ty hat does s0 must check to sec if there is 9 node in the list. If not, ic., if START = NULL, then the’algorithm will print the message UNDERFLOW. Deleting the Node Following a Given Node LALIST be a linked list in memory, Suppose we are given the location LOC of a node N in LIST. Farthermore, suppose we are given the Tepation LOCP of the node preceding N or, when Nis the | = sre given LOCP = NULL. The following algorithm deletes N from the list[ 28 | Data Structures 3 Figure 5.26 is the schematic diagram of the assignment START i= ‘LINK[START] which effectively deletes the first node from the list. This covers [Link] when N is the fips; Fig. 5.26 START = -LINKESTART] = Th bout Figure 5,27 is the schematic diagram of the assignment — LINK(LOCP] := LINKILOC) _ which effectively deletes the node N when N is not the first node. 7 START Locr Loc ah a The simplicity of the algorithm comes from the fact that We are already giyen the location LOCP of the node which precedes node N. In many applications, » ed LOCP.