The List is among the most generic of data

structures.

Real life:

a. shopping list,

b. groceries list,

c. list of people to invite to dinner

d. List of presents to get

# Lists

A list is collection of items that are all of the same

type (grocery items, integers, names)

The items, or elements of the list, are stored in

some particular order

It is possible to insert new elements into various

positions in the list and remove any element of

the list

List is a set of elements in a linear order.

For example, data values a1, a2, a3, a4 can be

arranged in a list:

(a3, a1, a2, a4)

In this list, a3, is the first element, a1 is the second

element, and so

The order is important here; this is not just a

random collection of elements, it is an ordered

collection

List Operations?

Useful operations

1=createList(): create a new list (presumably empty)

2=copy(): set one list to be a copy of another

3=clear(); clear a list (remove all elements)

4=insert(X, ?): Insert element X at a particular position in the list

5=remove(?): Remove element at some position in the list

6=get(?): Get element at a given position

7=update(X, ?): replace the element at a given position with X

8=find(X): determine if the element X is in the list

9=length(): return the length of the list.

List Operations?

We need to decide what is meant by “particular

position”; we have used “?” for this.

There are two possibilities:

1. Use the actual index of element: insert after

element 3, get element number 6. This

approach is taken by arrays

2. Use a “current” marker or pointer to refer to

a particular position in the list.

List Operations?

If we use the “current” marker, the following four

methods would be useful:

1=start(): moves to “current” pointer to the very

first element.

2= tail(): moves to “current” pointer to the very last

element.

3= next(): move the current position forward one

element

4= back(): move the current position backward one

element