3.0 Data Structures – Lists .. Part-2

In the last post, we have introduced Lists. We talked about Lists Specifications, Lists Implementation, and how to test what we have implemented. To review what we have come up to, download the full implementation here and the test driver here. Just to mention that this is not the ideal implementation, rather it’s the simplest one. You will find many implementations, and you may create your own one. In this post we will continue with the Lists, specifically implementing them using pointers.

Motivation

We have seen that implementing Lists based on arrays have many drawbacks. The most important one is that the size of the array is fixed. Even if you give the size of the array at run time (i.e. initializing the list size by the user, say in the constructor, and creating the array using new keyword), you will find problems in resizing the Lists (actually the array at the back-end). For example, if we determined that the MAX_ITEMS is 20, and filled all these 20 items. But we need to add more items to the list, how are we going to handle this?! It must be handled in the implementation, by a means of creating a larger array, and copying the 20 items to the new array and add more items. This is very costly. So, the concept of representing the list based on dynamic allocation is the solution I’m going to present.

Linked Nodes

Rather than representing items of the list as array elements, we will represent each item in the list as a Node. But what actually the note represents?! Exactly as the array element represent an item (i.e. int, float,….ItemType), the node will also contain a value that represent an item. We were referencing array elements by indexing (i.e. arr[0], arr[1],…etc.). Here, each node will point to the next node. That is, each item list will be attached to another item. And when adding a new item, a node is created carrying its value and attach this new node to the last element in the list. We will see how this is implemented.
Here is the node written in code.

template<class ItemType>
struct Node{
    ItemType info;
    Node* next;
};

The node contains an elements, info, of type ItemType (remember using templates in C++). It also has a pointer to another node, which will represent the next item in the list.

Linked List Implementation

Remember that our prototype functions were:

void InsertItem (ItemType item);
void RetrieveItem (ItemType item, bool& found);
void DeleteItem (ItemType item);
void GetNextItem (ItemType& item);

So, the class private members will be:

class List{
private:
    Node<ItemType>* start;
    int length;
    Node<ItemType>* currentPos;
}

The class will keep track of the the first element in the list via start node. It’s a pointer that will be null when the list is empty. To retrieve the elements of a list, we use currentPos pointer that will have a reference to the node we are currently referencing. The length is used for easy manipulating the list.
By now, we have defined how we are going to store data in memory. Next is how we are going to manipulate these data.

List<ItemType>::List(){
    length = 0;
    start = NULL;
}

The constructor initializes the list by making the start element points to null and the length is, for sure, zero.

void List<ItemType>::InsertItem(ItemType item){
    Node<ItemType>* location;       //line 1
    location = new Node<ItemType>;  //line 2
    location->info = item;          //line 3
    location->next = start;         //line 4
    start = location;               //line 5
    length++;                       //line 6
}

In line 1 and 2, we created a node. In line 3, we gave it a value by assigning the info the value of item. Remember that the node structure contain a value and a pointer to the next node. And here is the trick, in line 4, we make the new node we just created point to to start element. And, in line 5, we again assign the start pointer to the newly created node. Haaaa !! Have a moment thinking about it!
Let’s track the execution. The first time we call the function, say InsertItem(7), start is null. We create a node that has a value of 7 and pointing to start which is actually null. After that we make the start points to that new node.
We come up to that:
start =>  points to a node with value 7
a node with value 7 => points to null.
Calling the function again, with InsertItem(5), the same steps are repeated. We create a node that has a value of 5 and pointing to start which is now pointing to the node with value 7. After that we make the start points to that new node.
We come up to that:
start =>points to a node with value 5
a node with value 5 => points to a node with value 7
a node with value 7 => points to null.
Again and again, the same steps are repeated for the InsertItem() function. Remember that the length is increased each time we add a new item (line 6).

void List<ItemType>::RetrieveItem(ItemType item,
                                   bool& found){
    Node<ItemType>* location = start;
    int i;
    found = false;
    for(i = 0;i<length;i++){
        if(location->info == item){
            found = true;
            break;
        }
        else
            location = location->next;
    }
}

RetriveItem() is used to check whether an item is found in the list or not, returning the result in the boolean found. In the function we iterate through the nodes by the for loop. Remember that we used length member to be used here. In each node, we check its value, and if it maps to the targeted value, found is true. If not, we move up to the next node using the pointer notation. We iterate until the we find the element or we loop length times, in which case the found is already false.
There is another way to implement the search by while looping and without using length member. But, this is the most straight-forward way.

void List<ItemType> :: DeleteItem(ItemType item){
    Node<ItemType>* location = start;
    Node<ItemType>* tempLocation;
    if(location ->info == item){
        start = location->next;
        delete location;
        length--;
        return;
    }
    tempLocation = location;
    while(location != NULL){
        if(location->info == item){
            tempLocation->next = location->next;
            delete location;
            length--;
            return;
        }
        tempLocation = location;
        location = location->next;
    }
}

The delete operation may seem quite complex, as it has two cases. The first case is when the targeted element to be deleted is the first one. In which, we simply hold a pointer to that first element (to be deleted) and make the start points to the next element in the list. After that we delete that first element referred to by location. The second case is more complex in that we have to keep track of the previous node and the next node, to the node which we are going to delete. We hold a tempLocation pointer that first points to the the first node, so we have location and tempLocation points to the same first node. After that we iterate through the list using a while loop. In each loop, we make sure that tempLocation and Location are pointing to two successive node. In which, one of them (pointed to by Location) will be deleted. In this case, we make the tempLocation (the node previous to the targeted node) points to the NEXT node of the targeted one (location->next). Do you feel confuse ?! Have a look at the picture.

void List<ItemType>::GetNextItem(ItemType& item){
    if(currentPos == NULL)
        currentPos = start;
    else
        currentPos = currentPos->next;
    item = currentPos->info;
}

In the GetNextItem() function, we iterate through the linked list using currentPos. When it’s null (i.e. it’s the first time to call the function), we make it points to the start node. If not, we make it points to the following node. Then, we get the value of the current position. Note that, you must be careful when using this function so as not to reference to a node that doesn’t exist. For example, if the currentPos points to the last element, calling the function will make it points to null which will make the program crash by trying to getinfofrom a null location. You must keep track of the length of the list, or modify the definition of the function to handle this case.

Putting Them All Together

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

Test Driver

Do you think that we have write a test driver ?! For sure, NO! We have just changed how list is implemented, keeping the same functionality. And this is the magic of data structures. Whatever you change in the implementation, the programmer who use this data structure will use the same functionality. So, we will use the same test driver in the previous post (note that there may be some missing tests!). For convenience, you can download it here.

Conclusion

We have come up to two different implementations of Lists. One that uses array as the basic method of storing the data. And the other uses linked structures to do the same task. The difference between the two implementation is in the functions that are used to manipulate the data.
However, in some cases one implementation is preferable on the other. We can notice that arrays have advantages of simplicity, speed access and low memory storage. But arrays are very costly when we need resizing the list making it larger. On the other hand, linked lists have the advantage of being dynamically allocated, which will save memory space as we create a new node just when we add a new item. But linked have a drawback that the node size may be larger. That is, each item we add must reserve a node that has a size of ItemType plus the size of the address of the next node. Any way, both approaches are used in practice according to their properties.

To Be Continued

– Sorting Lists (both approaches).

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

4 thoughts on “3.0 Data Structures – Lists .. Part-2

  1. It’s hard to find your website in google. I found it on 12 spot, you should build quality backlinks ,
    it will help you to get more visitors. I know how to help you, just search
    in google – k2 seo tricks

    Like

  2. I read a lot of interesting articles here. Probably you spend a lot of time writing,
    i know how to save you a lot of time, there is an online tool that creates readable, google friendly posts in minutes, just search in google – laranitas free content source

    Like

leave your feedback

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s