Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 39
Текст из файла (страница 39)
It must be given apointer to x, and it then "splices" x out of the list by updating pointers. If we wish to delete anelement with a given key, we must first call LIST-SEARCH to retrieve a pointer to theelement.LIST-DELETE(L, x)1 if prev[x] ≠ NIL2then next[prev[x]] ← next[x]3else head[L] ← next[x]4 if next[x] ≠ NIL5then prev[next[x]] ← prev[x]Figure 10.3(c) shows how an element is deleted from a linked list. LIST-DELETE runs inO(1) time, but if we wish to delete an element with a given key, Θ(n) time is required in theworst case because we must first call LIST-SEARCH.SentinelsThe code for LIST-DELETE would be simpler if we could ignore the boundary conditions atthe head and tail of the list.LIST-DELET′ (L, x)1 next[prev[x]] ← next[x]2 prev[next[x]] ← prev[x]A sentinel is a dummy object that allows us to simplify boundary conditions.
For example,suppose that we provide with list L an object nil[L] that represents NIL but has all the fields ofthe other list elements. Wherever we have a reference to NIL in list code, we replace it by areference to the sentinel nil[L]. As shown in Figure 10.4, this turns a regular doubly linked listinto a circular, doubly linked list with a sentinel, in which the sentinel nil[L] is placedbetween the head and tail; the field next[nil[L]] points to the head of the list, and prev[nil[L]]points to the tail. Similarly, both the next field of the tail and the prev field of the head pointto nil[L]. Since next[nil[L]] points to the head, we can eliminate the attribute head[L]altogether, replacing references to it by references to next[nil[L]].
An empty list consists ofjust the sentinel, since both next[nil[L]] and prev[nil[L]] can be set to nil[L].Figure 10.4: A circular, doubly linked list with a sentinel. The sentinel nil[L] appears betweenthe head and tail. The attribute head[L] is no longer needed, since we can access the head ofthe list by next[nil[L]]. (a) An empty list. (b) The linked list from Figure 10.3(a), with key 9 atthe head and key 1 at the tail. (c) The list after executing LIST-INSER′(L, x), where key[x] =25. The new object becomes the head of the list.
(d) The list after deleting the object with key1. The new tail is the object with key 4.The code for LIST-SEARCH remains the same as before, but with the references to NIL andhead[L] changed as specified above.LIST-SEARC′(L, k)1 x ← next[nil[L]]2 while x ≠ nil[L] and key[x] ≠ k3do x ← next[x]4 return xWe use the two-line procedure LIST-DELET′ to delete an element from the list. We use thefollowing procedure to insert an element into the list.LIST-INSER′ (L, x)1 next[x] ← next[nil[L]]2 prev[next[nil[L]]] ← x34next[nil[L]] ← xprev[x] ← nil[L]Figure 10.4 shows the effects of LIST-INSER′ and LIST-DELET′ on a sample list.Sentinels rarely reduce the asymptotic time bounds of data structure operations, but they canreduce constant factors.
The gain from using sentinels within loops is usually a matter ofclarity of code rather than speed; the linked list code, for example, is simplified by the use ofsentinels, but we save only O(1) time in the LIST-INSER′ and LIST-DELET′ procedures. Inother situations, however, the use of sentinels helps to tighten the code in a loop, thusreducing the coefficient of, say, n or n2 in the running time.Sentinels should not be used indiscriminately. If there are many small lists, the extra storageused by their sentinels can represent significant wasted memory.
In this book, we usesentinels only when they truly simplify the code.Exercises 10.2-1Can the dynamic-set operation INSERT be implemented on a singly linked list in O(1) time?How about DELETE?Exercises 10.2-2Implement a stack using a singly linked list L. The operations PUSH and POP should stilltake O(1) time.Exercises 10.2-3Implement a queue by a singly linked list L. The operations ENQUEUE and DEQUEUEshould still take O(1) time.Exercises 10.2-4As written, each loop iteration in the LIST-SEARC′ procedure requires two tests: one for x ≠nil[L] and one for key[x] ≠ k. Show how to eliminate the test for x ≠ nil[L] in each iteration.Exercises 10.2-5Implement the dictionary operations INSERT, DELETE, and SEARCH using singly linked,circular lists.
What are the running times of your procedures?Exercises 10.2-6The dynamic-set operation UNION takes two disjoint sets S1 and S2 as input, and it returns aset S = S1 S2 consisting of all the elements of S1 and S2. The sets S1 and S2 are usuallydestroyed by the operation. Show how to support UNION in O(1) time using a suitable listdata structure.Exercises 10.2-7Give a Θ(n)-time nonrecursive procedure that reverses a singly linked list of n elements. Theprocedure should use no more than constant storage beyond that needed for the list itself.Exercises 10.2-8:Explain how to implement doubly linked lists using only one pointer value np[x] per iteminstead of the usual two (next and prev).
Assume that all pointer values can be interpreted ask-bit integers, and define np[x] to be np[x] = next[x] XOR prev[x], the k-bit "exclusive-or" ofnext[x] and prev[x]. (The value NIL is represented by 0.) Be sure to describe what informationis needed to access the head of the list. Show how to implement the SEARCH, INSERT, andDELETE operations on such a list. Also show how to reverse such a list in O(1) time.10.3 Implementing pointers and objectsHow do we implement pointers and objects in languages, such as Fortran, that do not providethem? In this section, we shall see two ways of implementing linked data structures withoutan explicit pointer data type. We shall synthesize objects and pointers from arrays and arrayindices.A multiple-array representation of objectsWe can represent a collection of objects that have the same fields by using an array for eachfield.
As an example, Figure 10.5 shows how we can implement the linked list of Figure10.3(a) with three arrays. The array key holds the values of the keys currently in the dynamicset, and the pointers are stored in the arrays next and prev. For a given array index x, key[x],next[x], and prev[x] represent an object in the linked list. Under this interpretation, a pointer xis simply a common index into the key, next, and prev arrays.Figure 10.5: The linked list of Figure 10.3(a) represented by the arrays key, next, and prev.Each vertical slice of the arrays represents a single object. Stored pointers correspond to thearray indices shown at the top; the arrows show how to interpret them. Lightly shaded objectpositions contain list elements. The variable L keeps the index of the Head.In Figure 10.3(a), the object with key 4 follows the object with key 16 in the linked list.
InFigure 10.5, key 4 appears in key[2], and key 16 appears in key[5], so we have next[5] = 2 andprev[2] = 5. Although the constant NIL appears in the next field of the tail and the prev fieldof the head, we usually use an integer (such as 0 or -1) that cannot possibly represent an actualindex into the arrays. A variable L holds the index of the head of the list.In our pseudocode, we have been using square brackets to denote both the indexing of anarray and the selection of a field (attribute) of an object. Either way, the meanings of key[x],next[x], and prev[x] are consistent with implementation practice.A single-array representation of objectsThe words in a computer memory are typically addressed by integers from 0 to M - 1, whereM is a suitably large integer.
In many programming languages, an object occupies acontiguous set of locations in the computer memory. A pointer is simply the address of thefirst memory location of the object, and other memory locations within the object can beindexed by adding an offset to the pointer.We can use the same strategy for implementing objects in programming environments that donot provide explicit pointer data types. For example, Figure 10.6 shows how a single array Acan be used to store the linked list from Figures 10.3(a) and 10.5. An object occupies acontiguous subarray A[j k]. Each field of the object corresponds to an offset in the rangefrom 0 to k - j, and a pointer to the object is the index j. In Figure 10.6, the offsetscorresponding to key, next, and prev are 0, 1, and 2, respectively.
To read the value of prev[i],given a pointer i, we add the value i of the pointer to the offset 2, thus reading A[i + 2].Figure 10.6: The linked list of Figures 10.3(a) and 10.5 represented in a single array A. Eachlist element is an object that occupies a contiguous subarray of length 3 within the array. Thethree fields key, next, and prev correspond to the offsets 0, 1, and 2, respectively. A pointer toan object is an index of the first element of the object. Objects containing list elements arelightly shaded, and arrows show the list ordering.The single-array representation is flexible in that it permits objects of different lengths to bestored in the same array.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
