pop_back() in Singly Linked List in C++

Question

I wrote the following implementation of the Singly Linked List. One problem that I am facing is that I want pop_back() to delete the last node and then set the tail to the second last node in O(1). Now, the problem is it's not a doubly-linked list and so I don't have access to the second last node without running a loop. I have done the push_back() in O(1). How do I make pop_back() in O(1) in this code?

#include <iostream>
using namespace std;

template <class T>
class LinkedList {
private:
    T data;
    LinkedList *next, *head, *tail;
public:
    LinkedList() : next(nullptr), head(nullptr), tail(nullptr){}
    LinkedList* get_node(T);
    void push_back(T);
    void insert(int, T);
    void pop_back();
    void erase(int);
    void print();
};

template <typename T>
LinkedList<T>* LinkedList<T>:: get_node(T element) {
    auto* new_node = new LinkedList;
    new_node -> data = element;
    new_node ->next = nullptr;
    return new_node;
}

template <typename T>
void LinkedList<T>:: push_back(T element) {
    if(head == nullptr) {
        head = get_node(element);
        tail = head;
    } else {
        LinkedList *node = get_node(element);
        tail->next = node;
        tail = node;
    }
}

template <typename T>
void LinkedList<T>:: insert(int position, T element) {
    LinkedList *node = get_node(element);
    if(position == 1){
        node->next = head;
        head = node;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        node->next = start->next;
        start->next = node;
    }
}
template <typename T>
void LinkedList<T>:: pop_back() {

}


template <typename T>
void LinkedList<T>:: erase(int position) {
    LinkedList *temp;
    if(position == 1){
        temp = head;
        head = head ->next;
        delete temp;
    } else {
        LinkedList *start = head;
        int it = 1;
        while (it < position - 1) {
            start = start->next;
            ++it;
        }
        temp = start -> next;
        start ->next = start ->next->next;
        delete temp;
    }
}

template <typename T>
void LinkedList<T>:: print() {
    LinkedList *start = head;
    while(start != nullptr) {
        cout << start->data << " ";
        start = start->next;
    }
}

int main() {
    LinkedList<int> lt;
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);
    lt.insert(1, 34);
    lt.print();
}

Answer 1

It's not possible.

Explanation

If you really want to do it in O(1) and want to keep the list single linked, you could think about storing the second last node in addition to the last node.

But, aside from becoming an organisational horror, it still won't work. Sure, in pop_back you could simply delete tail; and set the tail to the second last element. But now you would still require a loop to determine the new second last element.

Is that even bad?

I don't think so. Every datastructure has it's advantages and disadvantages. In my opinion a datastructure that does some things really well, but suck at others is better than a datastructure that does all things medium fast. Better keep your class slim, optimize it for specific scenarios and accept it's drawbacks.

Answer 2

You can't with a single linked list, lets implement your

template <typename T>
void LinkedList<T>:: pop_back() {
   tail = find(pos); 
   erase_next(tail); // erase tail's next.
}

You need a function to find a position, which would imply you also need know how many are in it, in which case pos is size-1 (-2 if you use zero offset) or search for a node that has pos as its next node. You can use most of the code in erase to implement it.

Now this new find will have an O(n) which is the curse of singled linked lists.