4.0 Data Structures – Lists .. Part-3

In the last two posts ( part-1 and part-2 ) of Data Structures, we discussed implementing lists using arrays and linked nodes. Those implementations made lists unsorted, that is items are not stored in a specific order (ascending or descending). In this post I’m going to discuss ways of keeping lists sorted all time.

 Ad-Hoc Technique

To keep the list sorted, we have a very simple way we can use. We add a line to the InsertItem() function, that call a sorting function, which in turn makes the list in order. The sorting function has access to the array of items (or the linked nodes) and runs one of the sorting algorithms on it. We have a lot of sorting algorithms in practice. Some of them are: Bubble Sort, Selection Sort, Heap Sort, Quick Sot, Merge Sort, Counting Sort and Radix Sort. I’ll not dive in them, but you can refer to this document for a complete and simple investigation of some of them.
However, this technique is rarely used as it’s inefficient. Suppose that you have a list of 1000 items and you are about to insert a new item, you insert it at the end of the list (as usual) and then run the sorting algorithm on them. This is very costly in both time and space. Suppose that there are more items than 1000 !! Also, what if the list is already sorted and the new item correct place will be at the end ?! At least, you will iterate through the whole list to guarantee the order (in the fastest algorithm).
So, we need to have a better technique to make lists sorted all the time.

More Sophisticated Technique

The more sophisticated technique is to insert the new item in its correct order. That is, rather than adding the item at the end of the list, we add it in its correct order by providing it a space inside the list. We will see shortly how this is implemented. Using this approach, we guarantee that every item inserted to the list will be in order, and in turn the whole list will be ordered.

You can notice that we will not change list specifications we have written. Rather, we will only change the implementation of InsertItem() function. So, here is the implementation.

– Using Arrays

void List<ItemType>::InsertItem(ItemType  item){
    //The list is empty
    if(length == 0){
        info[0] = item;
        length++;
    }
    else{
        int i ;
        //Search for the correct order place
        for(i = 0;i<length;i++){
            if(item < info[i]){
                //its correct place found, shift items
                //to provide space
                for(int j = length;j>i;j--){
                    info[j] = info[j-1];
                }
                info[i] = item;
                length ++;
                break;
            }
        }
        //The item is the largest one in the list
        if(i == length)
        {
            info[i] = item;
            length++;
        }
    }
}

The above implementation suggests three scenarios. The first is that the list is empty. In this case, we simply add it to the first element and increment the length. The second scenario is that the value of the item is somewhere between the list items. In this case, we search for the place where it will be in order, shift the items to the end of the list and inject it inside its place. The following figure illustrates it. The third one is that the item is the largest element in the list. We detect this by checking for i against the value of length, that is we looped through the whole list an didn’t find the correct place. In this case, we add the item to the end of the list.
This scenario is done for a list to be sorted ascending. To make it sorted descending, we just change the comparison in the if statement form < to >.

– Using Linked Nodes

The same approach is done in the linked nodes list and here is the implementation.

void List<ItemType>::InsertItem(ItemType item){
    Node<ItemType>* newNode, *location, *tempLocation;
    newNode = new Node<ItemType>;
    newNode->info = item;
    newNode->next = NULL;
    location = start;
    tempLocation = NULL;
    //The list is empty OR the new item is the smallest on
    if(location == NULL || item < location->info){
        newNode->next = start;
        start = newNode;
        length++;
        return;
    }
    int i;
    tempLocation = location;
    //Search for the correct order by iterating through 
    //the linked nodes
    while(location->next != NULL){
        if(item < location->info){
            //The correct place found, so inject the node
            newNode->next = location;
            tempLocation->next = newNode;
            length++;
            return;
        }
        else{
            tempLocation = location;
            location = location->next;
        }
    }
    //The item is the largest one in the list
    location->next = newNode;
    length++;
}

As you can see, it has the same three scenarios. The difference is in the implementation. This implementation looks like the implementation of DeleteItem() in the linked list (last post).

Additional Tip

By now, we have a sorted list, implemented in both approaches. Now, we can use the same test driver (Remember that changing the underlying implementation doesn’t affect how we actually use the list.
We have one additional tip we can add. When Searching for an item, we iterate through the whole list, one by one, and when the value is found we trigger the boolean variable found. Now, we know that the list is already sorted. So, we can improve the performance of the searching process using Binary Search. This will find the target value in log(n) time complexity instead of (n) time complexity for the linear search.
The idea of the binary search works as follow:
– check the middle element of the list against the target value. If equal, we are done.
– If they are not equal (the middle element and the item we search for), we compare them.
– If the target value is smaller than the middle element, we repeat the steps again for the left half of the list (Remember that the list is sorted and if the middle element is larger than the target value, for sure we don’t need to search in the right half of the list).
– If the target value is larger than the middle element, we repeat the steps again for the right half of the list (we don’t need to search the left half as all values will be smaller).
– we repeat these steps until the item value is the same as the middle element or the item is not found at all.

Here is the implementation of the above algorithm implemented in the array approach.

void List<ItemType>::RetrieveItem(ItemType item, 
                                  bool& found ){
    int first = 0,last = length -1,middle;
    middle = (first + last)/2;
    for(int i = 0;i<length;i++){
        if(item == info[middle]){
            found = true;
            break;
        }
        else if(item < info[middle]){
            last = middle - 1;
            middle = (first + last)/2;
        }
        else if(item >info[middle]){
            first = middle + 1;
            middle = (first + last)/2;
        }
        found = false;
    }    
}

The implementation is straight forward, as the algorithm suggests.
Can you implement the same algorithm using the linked list approach ?! Open your IDE now and try it yourself.

You will find the complete implementation of sorted lists in these two files: SortedList and SortedLinkedList. They share the same test driver we have provided in the previous posts.

By the end of the this post, we have handled most aspects of lists, implementing them by two different approaches and sorting them. You can investigate the functionalities that are predefined in the C++ libraries (#include<list> using the std namespace). Add your own specifications and implement them.

In the next post, we will discuss Queues. So, stay tuned!

Please, write your feedback in a comment :).

3 thoughts on “4.0 Data Structures – Lists .. Part-3

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