C++ Data Structures and Algorithms

Removing an element

As we discussed earlier, in the DoublyLinkedList, we can have O(1) for the complexity of the RemoveTail() operation. This can happen now since we have the Previous pointer in each element. To do so, we just need to pick the current Tail node and then assign the previous node of the current Tail as the new Tail. After that, we can safely remove the last element. The implementation of the RemoveTail() operation will be as follows:

template <typename T>void DoublyLinkedList<T>::RemoveTail(){    // Do nothing if list is empty    if(m_count == 0)        return;    // If List element is only one    // just simply call RemoveHead()    if(m_count == 1)    {        RemoveHead();        return;    }    // Save the current Tail    // to a new node DoublyNode<T> * node = Tail; ...