CODEWITHSUNDEEP
c++linked-list
pinbox
pinbox

Reputation: 83

Need for 'back pointer' in linked List push back operation

I am trying to figure out the following code to implement a push_back function for a linked list but I'm not quite sure why we need back_ptr->next and back_ptr to both point to p. I believe back_ptr->next could just point to NULL for it work, is there any advantage of implementing it as such that I'm missing?

void LinkedList::push_back(int element) {
    Node *p = new Node;
    p->element = elememt;
    p->next = 0;
    if (empty()) {
        front_ptr = back_ptr = p;
    } else {
        back_ptr->next = p;
        back_ptr = p;
    }
}

The following is the LinkedList class prototype. The back_ptr is being used to point to the end of the list for implementing the copy constructor (push_back makes it a lot easier to copy the list).

class LinkedList {
    void push_back(int element);
    // other member functions

    private:
    struct Node {
        Node *next;
        int element;
    };
    Node *front_ptr;
    Node *back_ptr;
};

Upvotes: 1

Views: 443

Answers (2)

ephemient
ephemient

Reputation: 204876

push_back(1);
push_back(2);
Node *p = new Node;
p->element = 3;
p->next = nullptr;

 front_ptr      back_ptr         p
     ↓             ↓             ↓
┌────┬────┐   ┌────┬────┐   ┌────┬────┐
| #1 |next| → | #2 |next|   | #3 |next| → nullptr
└────┴────┘   └────┴────┘↘  └────┴────┘
                          nullptr

back_ptr->next = p;

 front_ptr      back_ptr         p
     ↓             ↓             ↓
┌────┬────┐   ┌────┬────┐   ┌────┬────┐
| #1 |next| → | #2 |next| → | #3 |next| → nullptr
└────┴────┘   └────┴────┘   └────┴────┘

back_ptr = p;

 front_ptr             back_ptr  p
     ↓                         ↘ ↓
┌────┬────┐   ┌────┬────┐   ┌────┬────┐
| #1 |next| → | #2 |next| → | #3 |next| → nullptr
└────┴────┘   └────┴────┘   └────┴────┘

Upvotes: 1

Amit Kumar
Amit Kumar

Reputation: 1517

Let me explain if the list is not empty at the time of push back, the node which is currently tail should point its next to new node and finally tail should point to new node.

     Before push back 
     tail-> node x // tail points to node x
        x->next = null // as it is tail
     After push back new node y
       tail->next = y 
     As x was earlier pointed by tail ,this means x->next = p,

This step ensures the list remains connected.

     Finally , point the tail to the new node  
     tail -> y

Upvotes: 0

Related Questions