List data structure

What is list?

“A list is the collection of items of the same type (grocery items, integers, names etc)”.

The data in arrays are also of same type. When we say int x[6]; it means that only the integers can be stored in it. The same is true for list. So, we can say that this is another name of array!

Some properties of list data structures: –

• We can delete or add data in the list same as in arrays.
  • Delete: shifting elements to fill the empty space in the list.
  • Add: shifting elements of the list to make the space for insertion of new data.
• The order is important here; this is not just a random collection of elements but an ordered one. In the list (a3, a1, a2, a4), a3 is the 1^st element and a1 is the 2^nd elements and so on. We don’t want to the change this order.

Operations in list data structures: –

We need to know what is meant by “particular position” we have used “?” for this in the above table. There are two possibilities:

• Use the actual index of element: i.e. insert it after element 3, get element number 6. This approach is used with arrays.
• Use a “current” marker or pointer to refer to a particular position in the list.

If we use the “current” marker, the following four methods would be useful:

List implementation

Add Method

Let,

List: (2, 6, 8, 7, 1)

Current position = 3

Call to add 9 = add(9)

First, we will make the space to add element 9.

Then, we’ll add 9 to the blank space.

Next Method

“It moves the current position one position forward”

Basically, the “next” is used to check the boundary conditions. It makes assure that you’re not trying to access the 101^st position of array containing 100 elements implemented as list.

Remove Method

“It removes the element residing at the current position.”

In this case, we have to fill the gap where the element was deleted.

Let,

Remove(7) from the list (2, 6, 8, 9, 7, 1):

Now, fill the gap by shifting 1 to the left:

Find Method

“It find a specific element in the list”

See the find() code given below: –

int find(int x) {
	int j;
	for (j = 1; j < size + 1; j++) {
		if (A[j] == x) break;
	}
	if (j < size + 1) {
		current = j;
		return 1;
	}
	return 0;
}

Other Methods

A rapid overview of some of the other methods that we can use.

Let “A” is an array/list;

get() { return A[current];}

update(x) { A[current] = x; }

length() { return size; }

back () {
    current--;
}

end() { current = size; }

REFERENCE: CS301 Handouts (page 9 to 16)