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.
No comments:
Post a Comment