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

Question

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;
};

Possible duplicate of Linked List pushback member function implementation — Amit Kumar
– Amit Kumar, Commented Feb 4, 2017 at 6:58

ephemient · Accepted Answer · 2017-02-04 07:16:41Z

1

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
└────┴────┘   └────┴────┘   └────┴────┘

edited Feb 4, 2017 at 7:16

answered Feb 4, 2017 at 7:11

ephemient

207k39 gold badges292 silver badges402 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Amit Kumar Over a year ago

Just curious , how did you come up with the graphic

ephemient Over a year ago

@AmitKumar I arranged Unicode block drawing characters and arrows manually. You can see the source in the revision history. (It's not very interesting.)

pinbox Over a year ago

Wow the visuals make it a lot easier to understand. I guess I was missing the ordering of back_ptr->next and back_ptr updates (I thought they could have been written in any order). Thanks!

Remy Lebeau Over a year ago

Next time, please use an actual graphic made in an image editor, do not use text art. It doesn't always look good on everyone's screen. A simple bitmap created in something like MSPAINT would look much cleaner than what you have shown.

Amit Kumar · Accepted Answer · 2017-02-04 07:08:52Z

0

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

answered Feb 4, 2017 at 7:08

Amit Kumar

1,5371 gold badge17 silver badges28 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related