Lists



Abstract Data Type (ADT):Lists

Data type

1 a set of objects + a set of operations

2 Example: integer

A set of whole numbers

operations: +, -, x, /

Abstract data type

1 high-level abstractions (managing complexity through abstraction)

2 Encapsulation:

3 Operation on the ADT can only be done by calling the appropriate function

4 no mention of how the set of operations is implemented

5 Implementation of the ADT is separate from its use

6 in C++:

ADT ( C++: class

method ( C++: member function

Implementation of an ADT: Choose a data structure to represent the ADT

The List ADT

1 A sequence of zero or more elements

A1, A2, A3, … AN

N: length of the list

A1: first element

AN: last element

Ai: position i

If N=0, then empty list

Linearly ordered

Ai precedes Ai+1

Ai follows Ai-1

3 Operations

18 create: create an empty list

19 destroy an list

20 find: locate the position of an object in a list

list: 34,12, 52, 16, 12

find(52) ( 3

21 insert: insert an object to a list

insert(x,3) ( 34, 12, 52, x, 16, 12

22 delete: delete an element from the list

remove(52) ( 34, 12, x, 16, 12

23 findKth: retrieve the element at a certain position

24 printList: print the list

Implementation of the List ADT: two standard implementations for the list ADT

Array-based

Linked list

Array Implementation

27 Elements are stored in contiguous array positions

[pic]

30 Requires an estimate of the maximum size of the list

31 waste space

32 Operation evaluation:

33 printList and find: linear

34 findKth(random access): constant

35 insert and delete: slow

e.g. insert at position 0 (making a new element)

requires first pushing the entire array down one spot to make room

e.g. delete at position 0

requires shifting all the elements in the list up one

On average, half of the lists needs to be moved for either operation

36 Class Definition of list implemented by static array:

const int MAX=100;

class Chain {

public :

Chain();

bool IsEmpty() const;

int Length() const ;

bool Find(int k, int& x) const ;

int Search(int x) const ;

void Delete(int k, int &x, bool &success);

void Insert(int k, int x, bool &success);

…

private :

int list[MAX];

int size;

};

Chain::Chain()

:size(0)

{

}

int Chain::Length() const

{

return size;

}

bool Chain::Find(int k, int & x) const; //find the kth element

{

if (ksize) return false;

x=list[k-1];

return true;

}

int Chain::Search(int x) const //find the index of element x

{

for(int i=0; i=0 && k=0 && k ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download