Data-Structures-And-Algorithms-Alfred-V-Aho

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

Table of Contents Go to Chapter 2

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (37 of 37) [1.7.2001 18:58:23]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

Basic Abstract DataTypes

In this chapter we shall study some of the most fundamental abstract data types. We consider lists, which are sequences of elements, and two special cases of lists: stacks, where elements are inserted and deleted at one end only, and queues, where elements are inserted at one end and deleted at the other. We then briefly study the mapping or associative store, an ADT that behaves as a function. For each of these ADT's we consider several implementations and compare their relative merits.

2.1 The Abstract Data Type "List"

Lists are a particularly flexible structure because they can grow and shrink on demand, and elements can be accessed, inserted, or deleted at any position within a list. Lists can also be concatenated together or split into sublists. Lists arise routinely in applications such as information retrieval, programming language translation, and simulation. Storage management techniques of the kind we discuss in Chapter 12 use list-processing techniques extensively. In this section we shall introduce a number of basic list operations, and in the remainder of this chapter present data structures for lists that support various subsets of these operations efficiently.

Mathematically, a list is a sequence of zero or more elements of a given type (which we generally call the elementtype). We often represent such a list by a comma-separated sequence of elements

al, a2, . . . ,an

where n ³ 0, and each ai is of type elementtype. The number n of elements is said to be the length of the list. Assuming n ³ 1, we say that a1 is the first element and an is the last element. If n = 0, we have an empty list, one which has no elements.

An important property of a list is that its elements can be linearly ordered according to their position on the list. We say ai precedes ai+1 for i = 1, 2, . . . , n-1, and ai follows ai-1 for i = 2, 3, . . . ,n. We say that the element ai is at position i. It is also convenient to postulate the existence of a position following the last element on a list. The function END(L) will return the position following position n in an n- element list L. Note that position END(L) has a distance from the beginning of the

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (1 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

list that varies as the list grows or shrinks, while all other positions have a fixed distance from the beginning of the list.

To form an abstract data type from the mathematical notion of a list we must define a set of operations on objects of type LIST.† As with many other ADT's we discuss in this book, no one set of operations is suitable for all applications. Here, we shall give one representative set of operations. In the next section we shall offer several data structures to represent lists and we shall write procedures for the typical list operations in terms of these data structures.

To illustrate some common operations on lists, let us consider a typical application in which we have a mailing list from which we wish to purge duplicate entries. Conceptually, this problem can be solved quite simply: for each item on the list, remove all equivalent following items. To present this algorithm, however, we need to define operations that find the first element on a list, step through all successive elements, and retrieve and delete elements.

We shall now present a representative set of list operations. In what follows, L is a list of objects of type elementtype, x is an object of that type, and p is of type position. Note that "position" is another data type whose implementation will vary for different list implementations. Even though we informally think of positions as integers, in practice, they may have another representation.

1.INSERT(x, p, L). Insert x at position p in list L, moving elements at p and following positions to the next higher position. That is, if L is al, a2, . . . ,an, then L becomes a1, a2,. . . ,ap- 1, x, ap, . . . ,an. If p is END(L), then L becomes a1, a2, . . . , an, x. If list L has no position p, the result is undefined.

2.LOCATE(x, L). This function returns the position of x on list L. If x appears more than once, then the position of the first occurrence is returned. If x does not appear at all, then END(L) is returned.

3.RETRIEVE(p, L). This function returns the element at position p on list L. The result is undefined if p = END(L) or if L has no position p. Note that the elements must be of a type that can be returned by a function if RETRIEVE is used. In practice, however, we can always modify RETRIEVE to return a pointer to an object of type elementtype.

4.DELETE(p, L). Delete the element at position p of list L. If L is a1, a2, . . .

,an, then L becomes a1, a2, . . . ,ap- 1, ap+1, . . . ,an. The result is undefined if L has no position p or if p = END(L).

5.NEXT(p, L) and PREVIOUS(p, L) return the positions following and preceding position p on list L. If p is the last position on L, then NEXT(p, L) = END(L). NEXT is undefined if p is END(L). PREVIOUS is undefined if p is

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (2 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

1. Both functions are undefined if L has no position p.

6.MAKENULL(L). This function causes L to become an empty list and returns position END(L).

7.FIRST(L). This function returns the first position on list L. If L is empty, the position returned is END(L).

8.PRINTLIST(L). Print the elements of L in the order of occurrence.

Example 2.1. Let us write, using these operators, a procedure PURGE that takes a list as argument and eliminates duplicates from the list. The elements of the list are of type elementtype, and a list of such elements has type LIST, a convention we shall follow throughout this chapter. There is a function same(x,y), where x and y are of elementtype, that is true if x and y are "the same" and false if not. The notion of sameness is purposely left vague. If elementtype is real, for example, we might want same(x,y) true if and only if x = y. However, if elementtype is a record containing the account number, name, and address of a subscriber as in

type

elementtype = record acctno: integer;

name: packed array [1..20] of char; address: packed array [1..50] of char

end

then we might want same(x, y) to be true whenever x.acctno=y.acctno.†

Figure 2.1 shows the code for PURGE. The variables p and q are used to represent two positions in the list. As the program proceeds, duplicate copies of any elements to the left of position p have been deleted from the list. In one iteration of the loop (2)-(8), q is used to scan the list following position p to delete any duplicates of the element at position p. Then p is moved to the next position and the process is repeated.

In the next section we shall provide appropriate declarations for LIST and position, and implementations for the operations so that PURGE becomes a working program. As written, the program is independent of the manner in which lists are represented so we are free to experiment with various list implementations.

procedure PURGE ( var L: LIST );

{ PURGE removes duplicate elements from list L } var

p, q: position; { p will be the "current" position

in L, and q will move ahead to find equal elements }

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (3 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

begin

(1)p := FIRST(L);

(2)while p <> END(L) do begin

(3)q := NEXT(p, L);

(4)while q <> END(L) do

end

end; { PURGE }

Fig. 2.1. Program to remove duplicates.

A point worth observing concerns the body of the inner loop, lines (4)-(7) of Fig. 2.1. When we delete the element at position q at line (6), the elements that were at positions q+1, q+2, . . . , and so on, move up one position in the list. In particular, should q happen to be the last position on L, the value of q would become END(L). If we then executed line (7), NEXT(END(L), L) would produce an undefined result. Thus, it is essential that either (6) or (7), but never both, is executed between the tests for q = END(L) at line (4).

2.2 Implementation of Lists

In this section we shall describe some data structures that can be used to represent lists. We shall consider array, pointer, and cursor implementations of lists. Each of these implementations permits certain list operations to be done more efficiently than others.

Array Implementation of Lists

In an array implementation of a list, the elements are stored in contiguous cells of an array. With this representation a list is easily traversed and new elements can be appended readily to the tail of the list. Inserting an element into the middle of the list, however, requires shifting all following elements one place over in the array to make room for the new element. Similarly, deleting any element except the last also requires shifting elements to close up the gap.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (4 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

Fig. 2.2. Array implementation of a list.

In the array implementation we define the type LIST to be a record having two fields. The first field is an array of elements whose length is sufficient to hold the maximum size list that will be encountered. The second field is an integer last indicating the position of the last list element in the array. The i th element of the list is in the ith cell of the array, for 1 ≤ i ≤ last, as shown in Fig. 2.2. Positions in the list are represented by integers, the ith position by the integer i. The function END(L) has only to return last + 1. The important declarations are:

const

maxlength = 100 { some suitable constant }; type

LIST = record

elements: array[1..maxlength] of elementtype; last: integer

end;

position = integer;

function END ( var L: LIST ): position;† begin

return (L.last + 1) end; { END }

Figure 2.3 shows how we might implement the operations INSERT, DELETE, and LOCATE using this array-based implementation. INSERT moves the elements at locations p,p+1, . . . , last into locations p+1, p+2, . . . ,last+1 and then inserts the new element at location p. If there is no room in the array for an additional element, the routine error is invoked, causing its argument to be printed, followed by termination of execution of the program. DELETE removes the element at position p by moving the elements at positions p + 1, p + 2, . . . , last into positions p, p+ 1, . . .

, last-1. LOCATE sequentially scans the array to look for a given element. If the element is not found, LOCATE returns last+ 1.

It should be clear how to encode the other list operations using this implementation of lists. For example, FIRST always returns 1; NEXT returns one more than its argument and PREVIOUS returns one less, each first checking that the result is in range; MAKENULL(L) sets L.last to 0.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (5 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

If procedure PURGE of Fig. 2.1 is preceded by

1.the definitions of elementtype and the function same,

2.the definitions of LIST, position and END(L) as above,

3.the definition of DELETE from Fig. 2.3, and

4.suitable definitions for the trivial procedures FIRST, NEXT, and RETRIEVE,

then a working procedure PURGE results.

At first, it may seem tedious writing procedures to govern all accesses to the underlying structures. However, if we discipline ourselves to writing programs in terms of the operations for manipulating abstract data types rather than making use of particular implementation details, then we can modify programs more readily by reimplementing the operations rather than searching all programs for places where we have made accesses to the underlying data structures. This flexibility can be particularly important in large software efforts, and the reader should not judge the concept by the necessarily tiny examples found in this book.

Pointer Implementation of Lists

Our second implementation of lists, singly-linked cells, uses pointers to link successive list elements. This implementation frees us from using contiguous memory for storing a list and hence from shifting elements to make room for new elements or to close up gaps created by deleted elements. However, one price we pay is extra space for pointers.

In this representation, a list is made up of cells, each cell consisting of an element of the list and a pointer to the next cell on the list. If the list is a1, a2, . . . , an, the cell holding ai has a pointer to the cell holding ai+1, for

procedure INSERT ( x: elementtype; p: position; var L: LIST );

{ INSERT places x at position p in list L } var

q: position; begin

if L.last > = maxlength then error('list is full')

else if (p > L.last + 1) or (p < 1) then error('position does not exist')

else begin

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (6 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

for q := L.last downto p do

{ shift elements at p, p + 1, . . . down one position }

L.elements[q + 1 ]: = L.elements[q];

L.last := L.last + 1;

L.elements[p] := x end

end; { INSERT }

procedure DELETE ( p: position; var L: LIST );

{ DELETE removes the element at position p of list L } var

q: position; begin

if (p > L.last) or (p < 1) then error('position does not exist')

else begin

L.last := L.last - 1; for q := p to L.last do

{ shift elements at p + 1, p + 2,... up one position }

L.elements[q] := L.elements[q + 1]

end

end; { DELETE }

function LOCATE ( x: elementtype; L: LIST ): position; { LOCATE returns the position of x on list L }

var

q: position; begin

for q := 1 to L.last do

if L.elements[q] = x then return (q);

return (L.last + 1) { if not found } end; { LOCATE }

Fig. 2.3. Array-based implementation of some list operations.

i = 1, 2 , . . . , n-1. The cell holding an has a nil pointer. There is also a header cell that points to the cell holding a1; the header holds no element.† In the case of an empty list, the header's pointer is nil, and there are no other cells. Figure 2.4 shows a linked list of this form.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (7 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

Fig. 2.4. A linked list.

For singly-linked lists, it is convenient to use a definition of position that is somewhat different than the definition of position in an array implementation. Here, position i will be a pointer to the cell holding the pointer to ai for i = 2, 3 , . . . , n. Position 1 is a pointer to the header, and position END(L) is a pointer to the last cell of L.

The type of a list happens to be the same as that of a position -- it is a pointer to a cell, the header in particular. We can formally define the essential parts of a linked list data structure as follows.

type

celltype = record element: elementtype; next: − celltype

end;

LIST = − celltype; position = − celltype;

The function END(L) is shown in Fig. 2.5. It works by moving pointer q down the list from the header, until it reaches the end, which is detected by the fact that q points to a cell with a nil pointer. Note that this implementation of END is inefficient, as it requires us to scan the entire list every time we need to compute END(L). If we need to do so frequently, as in the PURGE program of Fig. 2.1, we could either

1.Use a representation of lists that includes a pointer to the last cell, or

2.Replace uses of END(L) where possible. For example, the condition p <> END(L) in line (2) of Fig. 2.1 could be replaced by p −.next <> nil, at a cost

of making that program dependent on one particular implementation of lists.

function END ( L: LIST ): position;

{ END returns a pointer to the last cell of L } var

q: position; begin

(1)q := L;

(2)while q−.next <> nil

do

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (8 of 40) [1.7.2001 18:58:59]

Data Structures and Algorithms: CHAPTER 2: Basic Abstract DataTypes

Fig. 2.5. The function END.

Figure 2.6 contains routines for the four operations INSERT, DELETE, LOCATE, and MAKENULL using this pointer implementation of lists. The other operations can be implemented as one-step routines, with the exception of PREVIOUS, which requires a scan of the list from the beginning. We leave these other routines as exercises. Note that many of the commands do not use parameter L, the list, and we omit it from those that do not.

The mechanics of the pointer manipulations of the INSERT procedure in Fig. 2.6 are shown in Fig. 2.7. Figure 2.7(a) shows the situation before executing INSERT. We wish to insert a new element in front of the cell containing b, so p is a pointer to the list cell that contains the pointer to b. At line (1), temp is set to point to the cell containing b. At line (2) a new list cell is created and the next field of the cell containing a is made to point to this cell. At line (3) the element field of the newlycreated cell is made to hold x, and at line (4) the next field is given the value of temp, thus making it point to the cell containing b. Figure 2.7(b) shows the result of executing INSERT. The new pointers are shown dashed, and marked with the step at which they were created.

The DELETE procedure is simpler. Figure 2.8 shows the pointer manipulations of the DELETE procedure in Fig. 2.6. Old pointers are solid and the new pointers dashed.

We should note that a position in a linked-list implementation of a list behaves differently from a position in an array implementation. Suppose we have a list with three elements a, b, c and a variable p, of type position, which currently has position 3 as its value; i.e., it points to the cell holding b, and thus represents the position of c. If we execute a command to insert x at position 2, the list becomes a, x, b, c, and element b now occupies position 3. If we use the array implementation of lists described earlier, b and c would be moved down the array, so b would indeed occupy the third position.

procedure INSERT ( x: elementtype; p: position); var

temp : position; begin

(1)temp := p −.next;

(2)new(p −.next );

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1202.htm (9 of 40) [1.7.2001 18:58:59]