List data structure

This is a new data structure for you. The List data structure is among the most generic of data structures. In daily life, we use shopping list, groceries list, list of people to invite to a dinner, list of presents to give etc. In this course, we will see how we use lists in programming.

A list is the collection of items of the same type (grocery items, integers, names). 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. The data which we store in list should be of same nature. The items, or elements of the list, are stored in some particular order. What does this mean? Suppose in the list, you have the fruit first which are also in some order. You may have names in some alphabetical order i.e. the names which starts with A should come first followed by the name starting with B and so on. The order will be reserved when you enter data in the list.

It is possible to insert new elements at various positions in the list and remove any element of the list. You have done the same thing while dealing with arrays. You enter the data in the array, delete data from the array. Sometimes the array size grows and at times, it is reduced. We will do this with the lists too.

List is a set of elements in a linear order. Suppose we have four names a1, a2, a3, a4 and their order is as (a3, a1, a2, a4) i.e. a3, is the first element, a1 is the second element, and so on. We want to maintain that order in the list when data is stored in the list. We don’t want to disturb this order. The order is important here; this is not just a random collection of elements but an ordered one. Sometimes, this order is due to sorting i.e. the things that start with A come first. At occasions, the order may be due to the importance of the data items. We will discuss this in detail while dealing with the examples.

Now we will see what kind of operations a programmer performs with a list data structure. Following long list of operations may help you understand the things in a comprehensive manner.
createList() is a function which creates a new list. For example to create an array, we use int x[6] or int* y = new int[20]; we need similar functionality in lists too. The copy() function will create a copy of a list. The function clear() will remove all the elements from a list. We want to insert a new element in the list, we also have to tell where to put it in the list. For this purpose insert(X, position) function is used. Similarly the function remove(position) will remove the element at position. To get an element from the list get(position) function is used which will return the element at position. To replace an element in the list at some position the function update(X, position) is used. The function find(X) will search X in the list. The function length() tells us about the number of elements in the list.

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.

The first option is used in the data structures like arrays. When we have to manipulate the arrays, we use index like x[3], x[6]. In the second option we do not use first, second etc for position but say wherever is the current pointer. Just think of a pointer in the list that we can move forward or backward. When we say get, insert or update while using the current pointer, it means that wherever is the current pointer, get data from that position, insert data after that position or update the data at that position. In this case, we need not to use numbers. But it is our responsibility that current pointer is used in a proper way.

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

In the next lecture, we will discuss the implementation of the list data structure and write the functions discussed today, in C++ language.