The List ADT

The List ADT

A list is a linear structure

• Each item except the first (front, head) has a unique predecessor

 • Each item except the last (end, tail) has a unique successor

• First item has no predecessor, and last item has no successor

• An item within a list is specified by its position in the list

1.               Possible Operations on a List

•     List - Create an empty list

•     isEmpty - Determine whether the list is empty

•     isFull - Determine whether the list is full

•     getLength - Return number of items in the list

•     insert - Add an item to the list

•     remove- Remove a specified item from list retrieve - Get the list item at a specified pos’n

List ADT

• Often, we could just use an array

• May wish to separate what a list does from its implementation (abstraction)

• Allows for a variety of implementations:

• Fixed versus arbitrary capacity

• Array-based versus linked lists (later in course)

• More natural to work with than an array: first position is location 1 in a list, but at index 0 in

an array

2. List ADT Implementation 1

• We’ll store either simple types (int, char, etc) or pointers to simple types or to more complex

objects - to avoid copying complex objects

• Underlying structure is an array with a fixed maximum size remove and retrieve will return the

item at a specified position; precondition: the position must be one that currently exists in the list

• replace will change the item stored at a specified position, and return the displaced item;

precondition: the position must be one that currently exists in the list

• swap will change positions of 2 items stored at 2 specified positions, precondition: the positions

must currently exist in the list Adding an item to a list will change, at most, the predecessor of one item and the successor of one item

• Removing an item will change, at most, the predecessor of one item and the successor of one item

Add value 5 at loc 3 of the list 7,0,23,16,8,4 to get 7,0,5,23,16,8,4

Delete 1st item from 9,3,6,0,7 to get 3,6,0,7;

delete 3rd item from this list to get 3,6,7

code:

constint DEFAULT_LIST = 200;

template<class Item>

class List {

public:

List(unsigned capacity = DEFAULT_LIST);

 ~List( ); // destructor

boolisEmpty( ) const;

boolisFull( ) const;

unsignedgetLength( ) const;

void insert (unsigned pos, Item item);

Item remove (unsigned pos);

Item replace(unsigned pos, Item item );

Item retrieve (unsigned pos) const;

void swap (unsigned i, unsigned j);

replace() in the List ADT

• Replacing a value in a given list position can be accomplished by removing the current value,

and then inserting the new value at the same position

• This process can be inefficient, depending on the underlying list implementation. In our array-based list, using remove and insert to replace a list item can be slow.

To replace first item:

removes shifts all following items one place left, and insert moves them back to original positions :

1.replace() accomplishes the same task without all the shifting

2.swap(i,j) allows to switch positions of 2 Items without unnecessary shifting that would take place if we used code (e.g. for List<Card> a)

Card tmp=a.remove(i); // assuming 1 <= j <i

a.insert(i-1,a.remove(j));

a.insert(j,tmp);

that achieves the same result very inefficiently