List Data Structure

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 tutorial, we will see how we use lists in programming.

A list is the collection of items of the same type (grocery items, integers, names, books etc). The data in arrays are also of same type. When we say an array of x[10]; 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 like a dictionary. We have all the elements in the alphabetical order in dictionary.  

It is possible to insert new elements at various positions in the list and remove any element of the list. 

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.

Operation Name	Description
createList()	Create a new list (presumably empty)
copy()	Set one list to be a copy of another
clear();	Clear a list (remove all elements)
insert(X, ?)	Insert element X at a particular position in the list
remove(?)	Remove element at some position in the list
get(?)	Get element at a given position
update(X, ?)	Replace the element at a given position with X
find(X)	Determine if the element X is in the list
length()	Returns the length of the list.

Details of Functions

createList() is a function which  creates a new list. For example to create an array, we use int x[10] or int* y = new int[10]; 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.