Linked List pushback member function implementation

Question

I am a novice programmer and this is my second question on Stack Overflow.

I am trying to implement a pushback function for my Linked List by using a tail pointer. It seems straightforward enough, but I have a nagging feeling that I am forgetting something or that my logic is screwy. Linked Lists are hard!

Here is my code:

template <typename T>
void LinkedList<T>::push_back(const T n)
{
Node *newNode;  // Points to a newly allocated node

// A new node is created and the value that was passed to the function is stored within.
newNode = new Node;
newNode->mData = n;
newNode->mNext = nullptr; 
newNode->mPrev = nullptr;

//If the list is empty, set head to point to the new node.
if (head == nullptr)
{
    head = newNode;
    if (tail == nullptr)
    {
        tail = head;
    }
}
else  // Else set tail to point to the new node.
    tail->mPrev = newNode;
}

Thank you for taking the time to read this.

First, if head is null, tail should also already be null, or something went horribly wrong. Second, if tail points to the last node in the list, shouldn't your newNode->mPrev point to that (tail), then set tail = newNode;? — WhozCraig
– WhozCraig, Commented Sep 21, 2016 at 3:22
Before writing any code, you should have drawn your linked list on paper, using boxes as the data and the lines between the boxes as links. Then translate what you see on paper to code -- if you did that, clearly what you're doing seems to be wrong, as WhozCraig pointed out. — PaulMcKenzie
– PaulMcKenzie, Commented Sep 21, 2016 at 3:24
WhozCraig, you're absolutely right. My else statement should have been newNode-mPrev = tail. I knew I was making a stupid error! Paul, I did write some of it out on paper. I should have written it all out! Thank you for the advice. — Ryan Swanson
– Ryan Swanson, Commented Sep 21, 2016 at 3:30
@RyanSwanson yeah, but you never set tail->mNext = newNode in the case of a non-null tail (which you can infer from a non-null head), which is critical for this to work. See answer below. — WhozCraig
– WhozCraig, Commented Sep 21, 2016 at 3:33

WhozCraig · Accepted Answer · 2016-09-21 03:28:18Z

3

Your pointing the wrong mPrev to the wrong node. And you never set mNext of the prior tail node if it was non-null to continue the forward chain of your list.

template <typename T>
void LinkedList<T>::push_back(const T n)
{
    Node *newNode;  // Points to a newly allocated node

    // A new node is created and the value that was passed to the function is stored within.
    newNode = new Node;
    newNode->mData = n;
    newNode->mNext = nullptr;
    newNode->mPrev = tail; // may be null, but that's ok.

    //If the list is empty, set head to point to the new node.
    if (head == nullptr)
        head = newNode;
    else
        tail->mNext = newNode; // if head is non-null, tail should be too
    tail = newNode;
}

answered Sep 21, 2016 at 3:28

WhozCraig

66.5k11 gold badges82 silver badges148 bronze badges

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

1 Comment

Ryan Swanson Over a year ago

Thanks a bunch, WhozCraig. Really helped me come to grips with this process.

Collectives™ on Stack Overflow

Linked List pushback member function implementation

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related