8.0 Data Structures – Advanced Lists .. Part-1

In the previous posts, we have discussed Lists. We discussed how to implement them using array, using linked nodes and how to create sorted lists. In this post, I’m gonna discuss some advanced tips in implementing lists. Before continuing reading, make sure to revise the past three posts about lists to get the big picture.

Getting back to implementing sorted linked lists, we notice that we left the private members of the class unchanged and only changed the InsertItem function, which was somewhat complex. Here, we are going to change the private data that represent our list implementation. Also, we are going to use recursion as an easy powerful tool to break the complexity of the implementation. 

Class Definition

In our modified version of sorted linked lists, we will follow the same specifications we have set in this post. The class definition will change to be as follows

class SortedLinkedList{
public:
    SortedLinkedList();
    void Print();
    Node<ItemType>*& GetStart();
private:
    Node<ItemType>* start;
};

The change is that we just removed the functions of InsertItem, DeleteItem, RetrieveItem and GetNextItem. We have just defined a new function GetStart() that simply returns a pointer to the start of the list. Let’s investigate these member functions.

SortedLinkedList<ItemType>::SortedLinkedList(){
    start = NULL;
}

The constructor initializes the pointer to null. And as you expect, the GetStart function will simply return this pointer.

Node<ItemType>*& SortedLinkedList<ItemType>::GetStart(){
    return start;
}

Remember that Node is a structure that contains the node value “info” and a pointer to the next node “next“. Let’s discuss the Print function later.
For now, where are the functions that insert, delete and retrieve items?! Ohhh! seems that I forgot them :D. These core functions will be implemented as helper functions (remember tree implementation!). Yes, using this way allows us to use recursion in implementing them. Let’s go on and see how these are done.

Implementation

Wvoid InsertItem(Node<ItemType>* &listPtr,ItemType item){
    if(listPtr == NULL || item < listPtr->info){
        Node<ItemType>* tempPtr = listPtr;
        listPtr = new Node<ItemType>;
        listPtr->info = item;
        listPtr->next = tempPtr;
    }
    else{
        InsertItem(listPtr->next,item);
    }
}

The InsertItem function takes the pointer to the list. This pointer is the first element of the list. When executing a test diver, we pass the first element of the list which is returned from GetStart function.
We have three cases:
– The first is when the list is initially empty. Then, we make a new pointer tempPtr that has the same value of listPtr, which in this case a null. After that, we create the new node and assign the item value to it. We make the next of that node points to the tempPtr which is null. Yes, it’s the first node in the list and points to nothing after it.
– The second and third cases are when the list already has items in it. These cases matter because we want to keep the list sorted.
If the item to be inserted is less than the listPtr, we insert the new item in the head of the list. It is implemented the same way we implemented the first case. If the item to be inserted is less than the listPtr, we recursively call InsertItem function with the next item in the list passed as a parameter.

void DeleteItem(Node<ItemType>* &listPtr,ItemType item){
    if(item == listPtr->info){
        Node<ItemType>* temp = listPtr;
        listPtr = listPtr->next;
        delete temp;
    }
    else
        DeleteItem(listPtr->next,item);
}

The delete operation in the linked list is illustrated in the following figure.

If the item to be deleted is the first one in the list, we make the list pointer points to the next item. But before we do so, we maintain a temporary pointer to the first item to delete it (release its memory space). If the item to be deleted is not the first item, we recursively call DeleteItem until it’s the first item in the list. Then, we delete it.

The last function we are going to discuss is Print. The print function calls another helper function, which we will call PrintNormal to print the list in order. The PrintNormal definition is as follows.

void PrintNormal(Node<ItemType>* currentPos){
    if(currentPos != NULL){
        cout<<(currentPos->info)<<endl;
        PrintNormal(currentPos->next);
    }
}

This function traverses the list one item by another and print the node’s value. We use this function within the class context as follows.

void SortedLinkedList<ItemType>::Print(){
    PrintNormal(start);
}

You can download the full implementation above from here.

Test Driver

We can make a very simple test driver for the above implementation as the following code illustrates.

SortedLinkedList<int> x;
InsertItem(x.GetStart(),5);
InsertItem(x.GetStart(),3);
InsertItem(x.GetStart(),2);
InsertItem(x.GetStart(),9);
DeleteItem(x.GetStart(),2);
x.Print();

This should print: 3,5,9. Remember that the list is sorted!
By now, we have investigated how to implement sorted linked lists using recursion. This technique is simpler than implementing them without recursion.

Almost done. Stay tuned for part two! We will discuss circular lists.

Don’t forget to leave your valuable feedback below :).