C++ Data Structures and Algorithms

Fetching an item in the LinkedList class

The first operation we are going to discuss is Get(). It will return the Node of the selected index, however, it will return NULL if the selected index is out of bounds. The implementation of the Get() method should be as follows:

template <typename T>Node<T> * LinkedList<T>::Get(int index){    // Check if the index is out of bound    if(index < 0 || index > m_count)        return NULL;    // Start from the Head    Node<T> * node = Head;    // Iterate through the linked list elements    // until it finds the selected index    for(int i = 0; i < index; ++i)    {        node = node->Next;    }    // Simply return the node result    return node;}

As we can see, the complexity of the Get() operation is O(N) since it has to iterate through the N elements ...