[isha_005]

Hi
I was going through linked list piece of code . I am unable to understand what the next pointer is actually pointing to . The next node in the list or the head .
when the pointer variable is pointing to -> data i can understand that the next node value .
but when it is pointing temp ->next = head wherever especially next variable is used I am unable to undertsand .what is the head actually the first node of the list .Please help me in this as i simply dont want to memorize the code i want to understand it properly .

    
#include <stdio.h>
#include <stdlib.h>

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

struct node* add(struct node *head, int data){
	struct node *tmp;

	if(head == NULL){
		head=(struct node *)malloc(sizeof(struct node));
		if(head == NULL){
			printf("Error! memory is not available\n");
			exit(0);
		}
		head-> data = data;
		[b]head-> next = head;  /*what does this piece of code mean */[/b]
               [color="#FF0000"][/color]	
            }else{
		tmp = head;
		
		while (tmp-> next != head)
			tmp = tmp-> next;
		tmp-> next = (struct node *)malloc(sizeof(struct node)); 
		if(tmp -> next == NULL)
		{
			printf("Error! memory is not available\n");
			exit(0);
		}
		tmp = tmp-> next;
		tmp-> data = data;
		tmp-> next = head;
	}
	return head;
}

void printlist(struct node *head)
{
	struct node *current;
	current = head;
	if(current!= NULL)
	{
		do
		{
			printf("%d\t",current->data);
			current = current->next;
		} while (current!= head);
		printf("\n");
	}
	else
		printf("The list is empty\n");

}

void destroy(struct node *head) 
{
	struct node *current, *tmp;
	
	current = head->next;
	head->next = NULL;
	while(current != NULL) {
		tmp = current->next;
		free(current);
		current = tmp;
	}
}
void main()
{
	struct node *head = NULL;
	head = add(head,1); /* 1 */
	printlist(head);

	head = add(head,20);/* 20 */
	printlist(head);

	head = add(head,10);/* 1 20 10 */
	printlist(head);

	head = add(head,5); /* 1 20 10 5*/
	printlist(head);
	
	destroy(head);
	getchar();
}

[ishkabible]

in a linked list the 'next' pointer points to the next item in the list (wait don't kill me). the next item is of the same type as the structure that contains the 'next' pointer. so each objects 'next' pointer points to an object that also has a next pointer, thus a list is formed. in you code the structure witch contains the 'next' pointer called node (witch is also very common) so the next pointer points to a dynamically allocated node.

[seeP+]

temp->next = head;

This is connecting one node to another.
Say temp's node contains 5 and head's node contains 4 which points to 8, which points to 2. So the list of head would be 4,8,2. After the above code the list of temp would be 5,4,8,2.

[isha_005]

Hi
I too understand the same thing that next pointer will point to next item in the list . but this head pointer is confusing is this becoz of naming style . Can u explain me the add functn logic .
In the if section
it check if (head == NULL ) i.e if empty list then add the value to it after allocating memory
head->data = data ; i.e 1 got added.
head -> next = head ; /* what is this pointing to can u break ita nd explain*/
like head-> next->data = ??
head-> next ->next = ??

[seeP+]

head -> next = head ; /* what is this pointing to can u break ita nd explain*/

If head is 5 the head->next will be five, thus the new head would be 5,5

[ishkabible]

malloc returns NULL if it cannot allocate the space for one reason or another so this is checking to make sure that the head was allocated and that there are no errors. the part where head is pointed to head implies a circularly linked list. head->next->next would be head and head->next>data would be the same as head->data. looking at the temp->next = head line i can see that this is indeed a circularly linked list.

@seeP+: no it would not be 5,5 it would just be 5. nothing was added to the list after head, that line is only run when the list is empty, e.g. it allocates the first node and links the back to the front (in that order not in reverse) and the head node would be the back and the front in this case

This post has been edited by ishkabible: 15 December 2010 - 03:14 PM

[seeP+]

ishkabible, on 15 December 2010 - 02:09 PM, said:

@seeP+: no it would not be 5,5 it would just be 5. nothing was added to the list after head, that line is only run when the list is empty, e.g. it allocates the first node and links the back to the front (in that order not in reverse) and the head node would be the back and the front in this case

Um no.

#include <iostream>
using namespace std;
struct node
{
	int num;
	node *next;
	node()
	{
		next = NULL;
		num = 0;
	}
	
};//end of struct
int main()
{
    node *head = NULL;
	head = new node;
	head->num = 5;
	head->next = NULL;
	head->next = new node;
	head->next = head;
	cout<<head->num;
	cout<<head->next->num;
	cout<<"\nThe program has terminated!";cin.ignore();
	return 0;
}

[ishkabible]

um yes, you made a new example that dose what you said but not what the OP is referring to. in his example head->next is not allocated but instead points to the head as a circularly linked list would. no where in the condition (when head is NULL) referred to by the OP was head->next allocated.

[NickDMax]

The idea of a linked list is that each node is "linked" to the next node in the list. So this can be done with pointers since the pointer can point to the next node in the list

so for example you get:

            First Node             Node 2                 Node 3 
      +-> +-----------+   +-->  +-----------+    +-->  +-----------+
      |   | Data      |   |     | Data      |    |     | Data      |
Head*-+   | Next*     | --+     | Next*     |  --+     | Next*     | --> NULL
          +-----------+         +-----------+          +-----------+

The head node is the home of the list -- USUALLY it is just the first element in the list, so the pointer head* is generally just a pointer to the first element in the list.

Each "Next*" pointer points to the "next" element in the list. If any node's "next pointer" points to head then you have a circular list - which is actually a viable structure though sometimes it represents and error.

So to keep track of a list you just need is a pointer to the first element in the list, because if you know the head node you can get to all of the nodes in the list just by following the chain down.

[seeP+]

If it was a proper Linked List then it would have been and that is what it is based off of. He doesn't understand what it does if it was proper.

[ishkabible]

why are circularly linked list improper? there is a tutorial one this forum that covers them.

edit: in fact here it is. it's one of the most popular tutorials.

This post has been edited by ishkabible: 15 December 2010 - 04:29 PM

[seeP+]

That was weird. I was signed in and it asked me for name and it made me a guess. lol