DaniWeb Forum Index > Software Development > C

C RSS

Linked List problem

•

Join Date: Jun 2006

Posts: 8

Reputation: codergem is an unknown quantity at this point

Solved Threads: 0

codergem

Offline

Newbie Poster

Linked List problem

Jun 4th, 2006

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.

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
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);
}
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);
}

•

Join Date: Aug 2005

Posts: 5,264

Reputation: iamthwee is a splendid one to behold

Solved Threads: 377

iamthwee

Offline

Posting Expert

Re: Linked List problem

Jun 5th, 2006

>i'm having problems in understanding that how every node is added at last.

You do realise there are loads of examples regarding linked lists on the net. You only need to look to realise this.

*Voted best profile in the world*

•

Join Date: Jun 2006

Posts: 8

Reputation: codergem is an unknown quantity at this point

Solved Threads: 0

codergem

Offline

Newbie Poster

Re: Linked List problem

Jun 6th, 2006

•

Originally Posted by iamthwee

>i'm having problems in understanding that how every node is added at last.

You do realise there are loads of examples regarding linked lists on the net. You only need to look to realise this.

what kind of reply was that...???
If you know the answer than post otherwise your suggestions are not invited.
Thanks

•

Join Date: Apr 2004

Posts: 4,341

Reputation: Dave Sinkula has a brilliant future

Solved Threads: 236

Dave Sinkula Dave Sinkula is offline

Offline

long time no c

Re: Linked List problem

Jun 6th, 2006

Post a small but complete snippet of code that demonstrates the issue. Pepper it with some debugging output to make things clear to us and you what it is you are trying to do.

You can make it easier for people to answer you know. Expecting folks to recreate what you have sitting in front of you is somewhat rude. And given the little play that this thread has gotten, I'd say your best bet would be to make it easier to answer.

"One of the methods used by statists to destroy capitalism consists in establishing controls that tie a given industry hand and foot, making it unable to solve its problems, then declaring that freedom has failed and stronger controls are necessary." --Ayn Rand

•

Join Date: Jul 2005

Posts: 1,674

Reputation: Lerner is a name known to all

Solved Threads: 261

Lerner

Offline

Posting Virtuoso

Re: Linked List problem

Jun 6th, 2006

A list is made up of zero to x nodes, where x is limited only by the amount of memory available. If there are nodes in the list then it has a first node and a last node. You have to keep track of the first, as it's the entry point for all other nodes in the list. You don't have to keep track of the last node, but you can if you wish.

Each node in a list is an instance of a struct/class and has one or more node pointers to (an)other node(s), frequently called next, previous, etc. In a singly linked list each node points to just one other node, except the last, which often will have a NULLed pointer. In a doubly linked list, each node points to two other nodes, the one before and the one after, except the first which has no before and the last which has no after.

Usually nodes themselves aren't used in manipulating lists. Rather pointers to nodes are used. So head is usually a pointer to the first node in the list, and tail is a pointer to the last node in the list. Often, in discussions about lists head is referred to as the first node, but it's really not, that's just convenient short hand. All nodes added to the list first need to be created somehow. This is often done using dynamic memory and assigning the address returned by the memory allocation routine to a node pointer, sometimes called newNode.

If there are no nodes in the list, then both head and tail are frequently assigned NULL.
If there is one node in the list, then head and tail contain the same address. If there is more than one node in a list, then the addresses in head and tail are different.

The list can be expanded by adding a new node anywhere within the list at your discretion. For example, if you keep track of tail, and you want to expand the list beyond one node by always adding at the end of the list just assign newNode to the pointer in tail and then assign the pointer in tail to tail, so that in essence newNode becomes the new tail. Then if you want you can assign NULL to newNode and wait for the next new node to be declared.

In effect what happens is that each pointer to node within a given node contains either the address of the next node in the list, if there is one, or, in the case of the last node where the pointer in the node is usually assigned NULL, though I've seen implentations where the last node points to itself instead of being NULL.

Simple as that.