pop_back() in Singly Linked List in C++

user_13064645 0
Viewed 1045

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();
}
singly-linked-list data-structures linked-list c++
4 Answers

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.

user_51059490

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.

user_40132580

Sadly, you can't do that in O(1) time, since there is no way to do that, you have to compensate memory for performance and use a Double Linked List. If you have the option to use other data structures, I would suggest you to use Deque

user_111412530

As mentioned in the other answers, adding to the end of a singly-linked list is an O(N) operation. For this reason, I don't include pop_back at all in my API. If the user needs to pop from both ends of the same linked list like a deque, they should use a doubly-linked list instead.

It's not a totally lost cause, however, since you can still use a singly-linked list in reverse for O(1) FIFO and LIFO behavior:

  • For a stack, instead of using push_back and pop_back, use push_front and pop_front, which are O(1) operations.
  • For a queue, instead of using push_front and pop_back, use push_back and pop_front, which are O(1) operations.

In summary, push_front, pop_front, and push_back are O(1) operations, but pop_back is not -- it's O(N).

user_9360300
Related