2.0 Data Structures – Lists .. Part-1

In the last post, we have introduced the basic concept behind data structures. In this post, I’m going to start with the first and the simplest data structure, Lists. Lists have many variations and too many implementations. We will handle them step by step.

Lists Specification

– We want to group some items together.
– No matter what is the order of them.
– The list must provide us with a way to insert items, delete, retrieve and search for them.
– We don’t care how items are stored in the list. All we care about is that there are some ways to call the above functions.
– Example: you will go shopping at night, and you have to prepare a list of what you need to buy. You get a paper and a pen and begin typing. What you care about is that you write down some items. In the market, you search your list, retrieve items’ names and after putting them in the cart, you delete them one by one from the list. This is exactly what will be implemented in our list data structure.

First have a look at the specs written in code.

template<class ItemType> 
class List        
{                        
public:                 
    List();
    void InsertItem (ItemType item);
    void RetrieveItem (ItemType item, bool& found);
    void DeleteItem (ItemType item);
    void GetNextItem (ItemType& item);
};

Looking at the above functions prototype, we notice their role from their name. What may be strange, is the words template and ItemType. These are the concepts of using templates in C++. Simply, it’s used to determine the type of the list items (int, float, char,…etc) when we want to use it. This concept is very important when writing data structures. We don’t want to implement a list that can only hold integers or only floats. Using templates, as above, when we are about to use the list, we will give it a type. Examples will clarify the use of templates, in the upcoming lines. However, you can refer to this documentation.

Lists Implementation

There are two approaches to implement any data structure: using arrays or using pointers. In my posts I’m going to show both approaches, starting with the simpler one, using arrays.

const int MAX_ITEMS = 20;
class List        
{
private:
    int length;           
    ItemType info[MAX_ITEMS];
    int currentPos;
};

Looking at the above private data members, this is how we are going to store the items, in an array (the info[ ] array). The maximum size of the list is determined in the the constant variable MAX_ITEMS. We keep track of the length of the list and the item we are currently pointing to (we will use this to retrieve items. remember: in the shop, you retrieve one item after the other). Again, we are using ItemType as the type of the array items. ItemType will be replaced by int, float, char …etc. We will see when it is replaced.

By now, we have settled on how we will store the data in memory. But, where is the magic ?! OK. The prototype above will be nearly used in any data structure we will implement. The real difference is in the implementation of the public functions. This implementation is what will differentiate a List from a Stack or a Queue. So, let’s dive in them.

List<ItemType>::List(){length = 0;
                       currentPos = -1;}

In the constructor, we just initialize the length to be zero. Don’t be confused that the array already has MAX_ITEMS elements (20 in our case), the values existed in these elements are garbage. Actually, the user of the list will not deal with array directly.

void List<ItemType>::InsertItem(ItemType item){
        info[length] = item ;
        length++ ;
}

The insert function simply put the new item in the array element with index length. This work as follows: the first time we insert an item, length is 0, so it will be inserted in the first array element. Then we increment the length. When we insert an item again, it will be inserted in info[1] and again the length is incremented. And so on.

void List<ItemType>::RetrieveItem(ItemType item,
                                  bool& found){
    int i;
    found=false;
    for(i=0;i<length;i++){
        if(item == info[i]){
            found = true;
            break;
        }
    }
}

In the above function, we search for an item and if it is in the list, the found boolean variable will be true. And if not found, it is false. We use this function to search for an item and know whether it exists or not. There are many variations to implement this function. It may have a different prototype.

void List<ItemType>::DeleteItem(ItemType item){
        for(int i=0;i<length;i++){
            if(item == info[i]){
                info[i] = info[length-1];
                length--;
            }
        }
}

In the above function, we want to delete an item. We search for it, and if found we overwrite it with the value in the last element in the array. After that, we decrement the value of length. Notice that the value of the last element in the array (in the previous state before deleting) still exists but is not accessible as we don’t allow the user to deal with the array directly.

void List<ItemType>::GetNextItem(ItemType& item){
        currentPos++;
        item = info[currentPos] ;
}

We use the above function to iterate through the items of the list, one after the other. As we mentioned before, we use a currentPos variable. We return the result in the passed-by-reference variable.

These are the basic specifications of any list data structure. For sure, there are too many utility functions that help us identify the current state of the list (e.g. length, clear lists, ..etc.)

Putting Them All Together

You can download the full header file of list data structure from here! Note: there are many added functions, try understanding them and add yours to the file.

Test Driver

void main(){
    List<int> x;

    // InsertItem() function
    x.InsertItem(4);
    x.InsertItem(3);
    x.InsertItem(7);
    x.InsertItem(9);
    x.InsertItem(13);
    x.InsertItem(2);
    x.InsertItem(6);

    // Delete() function
    x.DeleteItem(3);
    x.DeleteItem(9);
    cout<<endl<<"After deletion process ..."<<endl
        <<"length is "<<x.LengthIs()<<endl;
    cout<<"the list contains : "<<endl;
    x.ResetList();
    for(int i = 0;i<x.LengthIs();i++){
        int temp ;
        x.GetNextItem(temp);
        cout<<temp<<"  "<<endl;
    }

    // RetrieveItem() function
    cout<<endl<<"searching for item 13 "<<endl;
    bool found;
    x.RetrieveItem(13,found);
    if(found)
        cout<<"found "<<endl;
    else
        cout<<"not found "<<endl;
    cout<<endl<<"searching for item 1 "<<endl;
    x.RetrieveItem(1,found);
    if(found)
        cout<<"found "<<endl;
    else
        cout<<"not found "<<endl;
}

What I will mention here is List<int>. Remember that we used ItemType as the type of the array, in the implementation. Here, we determine the type that the list will hold. What actually happens under the hood is that each ItemType is replaced by int in our class definition. If we wrote List<float> in our main() function, the same case will happen.
You can download the full test driver file from here! Note: I tested many functions, that I added in the header file, try understanding them and add your test cases to the main function.

Conclusion

A list data structure is just a store that we use to keep track of unsorted items. It’s a way to make the process easier for a programmer to store data, rather than using direct arrays. The main difference between a data structure and another is how you implement its utility functions (insert, delete, retrieve, …etc.) We will see in the next posts that we will use the same array, but change the implementation of the functions to meet the specifications.

To Be Continued

– Implementing Sorted Lists.
– Implementing Lists (Unsorted, Sorted)Using Pointers.

Your questions are very welcomed and I will be glad to receive your feedback :).