Linked List problem

[codergem]

Helo friends!!
I m having problems in understanding that how every node is added at
last.Could anyone explain me this in much better manner.
Well here it is....
we use a local "reference pointer" which always points to the last
pointer in the list instead of to the last node. All additions to the
list are made by following the reference pointer. The reference pointer
starts off pointing to the head pointer.
Later, it points to the .next field inside the last node in the list.


Code:
struct node* BuildWithLocalRef() {
struct node* head = NULL;
struct node** lastPtrRef= &head; // Start out pointing to the head
pointer
int i;
for (i=1; i<6; i++) {
Push(lastPtrRef, i); // Add node at the last pointer in the list
lastPtrRef= &((*lastPtrRef)->next); // Advance to point to the
// new last pointer
}
// head == {1, 2, 3, 4, 5};
return(head);
}

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Helo friends!!
I m having problems in understanding that how every node is added at
last.Could anyone explain me this in much better manner.
Well here it is....
we use a local "reference pointer" which always points to the last
pointer in the list instead of to the last node. All additions to the
list are made by following the reference pointer. The reference pointer
starts off pointing to the head pointer.
Later, it points to the .next field inside the last node in the list.

This is, if I understand you question right, not so much a C++ but
rather a general programming question and might be better answered
elsewhere. But anyway...

Why use a pointer to a pointer? Why not point to the last element instead?

If we assume a double-linked list your list-structure/class would have
two pointers; one for the head and one for the tail (last node). Each
node-structure/class would have two pointers too; one for the previous
node and one for the next node in the list, it would also contain the
data stored in the node.

So to start the list has both head and tail set to 0. Then you do an
insert/push_back and both head and tail is set to the new node, both
pointers in the node is set to 0 (previous is 0 to indicate that it's
the first and next is 0 to indicate that it's the last node in the list.

Next you do a new insert and this time you follow the list's tail-
pointer to find the last node, set it's next-pointer to the new node and
the new node's previous-pointer to the node pointed to by tail. After
this is done you update the tail-pointer to point to the new node.

Short example:

struct node // a node stores integers
{
node* next;
node* prev;
int i;
}

class list
{
private:
node* head;
node* tail;

public:
list(): head(0), tail(0) {}

void add(node* n)
{
tail->next = n; // Update the last nodes next-pointer
n->prev = tail; // update n's prev-pointer
tail = n; // make tail point to n
}
};

Erik Wikström