CODEWITHSUNDEEP
c++clinked-listsingly-linked-list
Anonymous Guy
Anonymous Guy

Reputation: 307

Linked list - Insert at end using a rear pointer

I'm learning about linked list insertions and encountered the following code to insert a node at the end of a linked list (in a rather old and obsolete book for C++ still used I don't know why):

void Insert_End(Node * np){
    if (start == NULL){
        start = rear = np;
    }
    else{
        rear -> next = np;
        rear = np;
    }
}

My question is shouldn't it be np -> next = rear;

PS : np is the new node being inserted at the end, rear points to the last node, start points to the first node.

Upvotes: 0

Views: 644

Answers (2)

kiran Biradar
kiran Biradar

Reputation: 12732

My question is shouldn't it be np -> next = rear;

No,following pictures may help you understand easily.

When you do start = rear = np; for the first time all the 3 nodes may look like below.

  ------
  |  np  |
   ------
  ^      ^
  |       |
 ----      ----
|start|   | rear|
 ----      ----

for the successive insertion:

when you do rear -> next = np; your list may look like below.

note: rear is still pointing to previous last node of the list and np1 is pointing to np2.

  ------         -----
  |  np1 | ---> | np2 |
   ------        -----
  ^       ^
  |       |
 ----      ----
|start|   | rear|
 ----      ----

when you do rear = np; your rear gets updated to point current last node.

  ------         -----
  |  np1 | ---> | np2 |
   ------        -----
  ^              ^
  |              |
 ----           ----
|start|        | rear|
 ----           ----

Upvotes: 3

eerorika
eerorika

Reputation: 238311

My question is shouldn't it be np -> next = rear;

No, because then no node would be pointing to np, and therefore it wouldn't be part of any list (other than the list whose head is np). Furthermore, np wouldn't be at the rear, since its next would be pointing at a node (the node that was rear previously). The example is a correct implementation.

Upvotes: 1

Related Questions