understanding how to add new node at end of link list

Question

struct Node
{
    int data;
    Node *next;
};

//function to add node
.
.
.
ListNode <NODETYPE> *newPtr = getNewNode(value);
if( isEmpty() ) //function to check if list is empty
    firstPtr = lastPtr = newPtr;
else
{
    lastPtr->next = newPtr; // 1 what does this do?
    lastPtr = newPtr;  // 2 and this?
}

This is a piece of code from my textbook. Im having a hard time understanding the 2 lines marked with numbers above. I understand that if the list is empty then we point the first and last pointer to our newly created node. However, if there is already a node in the list, how does it work?

The thing that confused me was both the lines pointed to the newPtr created. What is the difference between the line marked 1 and 2?

Here is my take on it.

For 1: we are telling the pointer part of lastPtr to point to the new node

For 2: we then point lastPtr to newPtr? why did we point to newPtr twice?

Can someone please explain?

Answer 1

lastPtr->next = newPtr; // 1 what does this do

At this stage, lastPtr points to the node that is currently at the end of the list. Its next member is null, because nothing follows after it yet. next is updated to point at the new node because the new node now follows after the previous node, so the previous node has to be updated to point at the next node in the list - the new node being inserted.

lastPtr = newPtr; // 2 and this?

This is telling the list that the new node is now the last node in the list.

Answer 2

A node holds the data and a pointer to the next node, so that the list can be linked:

struct Node
{
    int data;
    Node *next;
};

Assuming NodeType is Node, it creates a new node. After creating a new node, lastPtr is a pointer to the last inserted element, so this will add newPtr to the end of the list.

ListNode <NODETYPE> *newPtr = getNewNode(value);
if( isEmpty() ) //function to check if list is empty
    firstPtr = lastPtr = newPtr;
else
{
    lastPtr->next = newPtr; //This links your newPtr to the next field of the node that was last before and still is.
    lastPtr = newPtr;  // This updates lastPtr to point to the new last node, which is the one you just inserted.
}

Answer 3

Your code from your textbook is seemingly trying to engrain one-track purpose rather than encompassing what you should be thinking about, namely managing the list.

1. This step wires the new node to the next pointer of the current end of list node.
2. This step establishes a new end of list.

That said, the linked list in this code is emulating a queue, where firstPtr always points to the "front" of the queue, and lastPtr always points to the "back" of the queue where the new arrivals go. If one is NULL, they both better be. Thus you can assume:

if (lastPtr == NULL) // if this is true, the list is empty.

Thus consider this upon a new arrival:

• If the list is empty, both firstPtr and lastPtr should point to the new node.
• Otherwise, firstPtr remains unchanged and lastPtr->next is set to the new node, then lastPtr is set to the new node.

Note that in both of these cases, lastPtr is going to reference the new node when finished. therefore the entire thing becomes:

if (lastPtr == nullptr)
    firstPtr = newPtr;       // list is empty, first must point to new arrival
else
    lastPtr->next = newPtr;  // list is not empty, wire to end of list

lastPtr = newPtr;            // regardless, establish new end-of-list

Removing nodes is somewhat similar, btw.

if (firstPtr != nullptr)
{
    victim = firstPtr;
    firstPtr = firstPtr->next;
    delete victim;

    if (firstPtr == nullptr)
        lastPtr = nullptr;
}

A picture speaks a thousand words. The following actions will generate the corresponding diagrams:

1. Start with an empty list
2. Add NODE0
3. Add NODE1
4. Add NODE2
5. Remove NODE0
6. Add NODE3
7. Remove NODE1
8. Remove NODE2
9. Remove NODE3

1. Start with an empty list

firstPtr ----> NULL
lastPtr  ----> NULL

2. Add NODE0

firstPtr ------> NODE0 ---> NULL
                   |
lastPtr ------------

3. Add NODE1

firstPtr ----> NODE0 ---> NODE1 ----> NULL
                            |
lastPtr ---------------------

4. Add NODE2

firstPtr ----> NODE0 ---> NODE1 ----> NODE2 ----> NULL
                                        |
lastPtr ---------------------------------

5. Remove NODE0

firstPtr ----> NODE1 ----> NODE2 ----> NULL
                             |
lastPtr ----------------------

6. Add NODE3

firstPtr ----> NODE1 ----> NODE2 ----> NODE3 ----> NULL
                                         |
lastPtr ----------------------------------

7. Remove NODE1

firstPtr ----> NODE2 ----> NODE3 ----> NULL
                             |
lastPtr ----------------------

8. Remove NODE2

firstPtr ----> NODE3 ----> NULL
                 |
lastPtr ----------

9. Remove NODE3

firstPtr ----> NULL
lastPtr  ----> NULL

I honestly can't think of a better way to express it.

Answer 4

if( firstPtr == NULL) //function to check if list is empty
   firstPtr = lastPtr = newPtr; // if its empty then it assigns both firstPtr and  lastPtr to newPtr
else
{
   lastPtr->next = newPtr; // if its not the first node then it will b added at last
   lastPtr = newPtr;  // now lastPtr will be updated to point newPtr
}

for example suppose you have to make link list 1-2-3-NULL

here newPtr will point to node having data as 1 and initially firstPtr and lastPtr both are NULL

firstPtr = lastPtr = newPtr // all will be pointing to 1

now next node newPtr = 2

list is not not empty So now lastPtr->next = newPtr // this will make list as 1-2

lastPtr = newPtr // now lastPtr will point to 2

similarly, You can add other nodes in the linked list.