9.0 Data Structures – Advanced Lists .. Part-2

Let’s continue talking about Lists, but first let’s have a quick recap. In the last post, we covered a new way to implement lists, which is using recursion. To use this technique, we changed the underlying data members. In this post, we are continuing with another version of lists, Circular Lists.

The idea behind circular lists is to make the last element in the list points back to the first element. The resulting list will similar to the one in the picture below.

This implies that whenever we get the next item, we will never reach the end of the list. When we want to traverse the list, we must use the length of it to limit going from start again.

Class Definition

The Circular List class will have the same definition of Lists (as usual!). We will just add two properties:
– The list is sorted.
– The last item in the list points to the first one (Circular).
The difference will be in the implementation of the functions. As we don’t need recursion, the implementation of the functions will not be separate from the class definition.

class CircularList{
public:
    CircularList();
    ~CircularList();
    void InsertItem(ItemType item);
    void DeleteItem(ItemType item);
    void GetNextItem(ItemType &item);
private:
    Node<ItemType>* start;
    int length;
    Node<ItemType>* currentPos;
};

The above definition is straightforward. Their functionality is the same we implemented previously.

Class Implementation

Let’s have a closer lock at the code inside.

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

The constructor initializes the length to zero and the start to null.

The insert function is a little bit tricky, because we want the list to be sorted AND circular. The scenario of the insert item goes as shown below.

In the above scenario, I haven’t indicated how to get the predLoc and Location pointers. To break the complexity, we will create another function to do the stuff.

void FindItem(Node<ItemType>* start,ItemType item,Node<ItemType>* &location,Node<ItemType>* &predLoc,bool &found){
    bool moreToSearch = true;
    location = start->next;
    predLoc = start;
    found = false;
    while(moreToSearch && !found){
        if(item < location->info)
            moreToSearch = false;
        else if(item == location->info)
            found = true;
        else{
            predLoc = location;
            location = location->next;
            moreToSearch = (location != start->next);
        }
    }
}

The FindItem function takes a pointer to the list start and an item value as arguments and return the predLoc and location as passed-by-reference variables. Found is passed by reference to indicate whether the item is found or not (can be used as a search function).
First we initialize predLocation to point to start and location to point to the next of start (which may be the same if the list has only one item). We continue moving in the list with the same steps. The searching stops when the item is less than the current location value (this is to sort the list) or when the value is found. When the function executes to the end, we have predLocation and location are set to the appropriate nodes.

Let’s jump now to the InsertItem function definition.

void CircularList<ItemType>::InsertItem(ItemType item){
    Node<ItemType>* newNode;
    Node<ItemType>* predLoc;
    Node<ItemType>* location;
    bool found;
    newNode = new Node<ItemType>;
    newNode->info = item;
    if(start != NULL){
        FindItem(start,item,location,predLoc,found);
        newNode->next = predLoc->next;
        predLoc->next = newNode;
        if(start->info < item)
            start = newNode;
    }
    else{
        start = newNode;
        newNode->next = newNode;
    }
    length++;
}

The above function just implements what we have illustrated in the picture above. If there is no nodes in the list (start = null). we create the new node and set the pointers. If not, we use our FindItem function and set the pointers. There is a case when we insert an item that is the smallest item in the list. We must modify the start pointer to point to the new node.

The scenario of the DeleteItem is simple. We maintain a pointer to the predLoc and Location. Sure, we will use the same FindItem function. Then, we make the next pointer of the predLoc points to the next node of location. And here is the code.

void CircularList<ItemType>::DeleteItem(ItemType item){
    Node<ItemType>* location;
    Node<ItemType>* predLoc;
    bool found;
    FindItem(start,item,location,predLoc,found);
    if(predLoc == location)
        start = NULL;
    else{
        predLoc->next = location->next;
        if(location == start)
            start = predLoc;
    }
    delete location;
    length--;
}

If the predLoc is equal to location, this means that the list has only one item and so we make start equal to null. Otherwise, we make the next pointer of the predLoc points to the next node of location. At the end, we delete the target node and decrease the length.
The above code has a very simple mistake. Try to find it yourself!

To traverse the list, we implement the GetNextItem function.

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

We use the currentPos pointer to get the items of the list one by one. If it is not set at first, we set it to start. Otherwise, we advance it to the next node. Then, we get the node value. Use this function with care to the list length. If the list is empty, the currentPos pointer will return garbage values. And as the list is circular, you may continue looping the list printing the same items. So, use this function along with the length of the list to control its execution.

The last piece of the code we will discuss is the de-constructor.

CircularList<ItemType>::~CircularList(){
    for(int i = 0;i<length;i++){
        Node<ItemType>* temp;
        temp = start;
        start = start->next;
        delete temp;
    }
}

This is a loop on list items. In every node, we maintain a temporary pointer to the current node, advance the start pointer and delete the temporary one. This will ensure that all memory spaces occupied by the list nodes will be freed.

And now, you can download the full implementation here.

What about trying to write the test driver yourself?! It’s the same as the ones we wrote before.

Final Comment

At this point, we have covered most aspects of data structures implementations. Download all the code in this series fro here. I’m feeling very happy writing these final words in the data structure series. See you again in another series ;).

Don’t forget to give me your appreciated feedback below. Write down the topics you want to discuss in the upcoming posts!

🙂 🙂 🙂

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