head pointer(linked list)

[Ausandy]

Hi, I want to define a pointer, but I am very confused about head pointer, if i define a struct, like
typedef struct name{
int i;
struct node *next;
// should I define a head here?
// like: struct node *head;
}node;
// I'm not sure should I define the head outside or inside, like
typedef node ptr;
ptr head;
can you give me some example for how should I use the head pointer? thank you

[Cshot]

Here's the tutorial on this site:
http://www.cprogramming.com/tutorial/lesson15.html

No, you shouldn't declare the head pointer there. It should go outside the structure. You don't want all of your structures to have a head pointer, just one global one to manipulate your list.

[Prelude]

The most straightforward way is to declare two structures, one for each node in the list and one which contains an entire list by way of a head pointer.

struct link
{
  void *data;
  struct link *next;
};

struct list
{
  struct link *head;
  int n_links;
};

Now you simply create an instance of the list struct and add new nodes as usual to the head pointer.

-Prelude

[Sayeh]

Where did this 'specialized' idea of a head pointer come from? that's not how it's normally done.

Maybe you're confusing two separate issues-- linked lists and circular queues. 'Head' pointers aren't the same as 'root' node pointers, in conversation.

Both can have head and tail pointers, but usually it's implemented like this:

For a circular queue:

typedef struct
   {
   long                     data;
   long                     moreData;
   . . .
   }node,*nodeP;

node      queue[10];
nodeP    headPtr;
nodeP    tailPtr;

/* Create 10 nodes as an array         */


headPtr = &queue[0];                    /* init head */
tailPtr = &queue[0];                       /* init tail */

/* as data is added to the queue, the
 * head pointer is incremented to the
 * next element.  If the head pointer
 * pointer ever == the tail (swallows
 * the tail), the queue is overrun/full
 * The idea is that something else is
 * following along, pulling data out of
 * the tailptr and incrementing it so
 * it tries to catch up (or run at the
 * same rate) with the headptr.  If
 * the tail catches up to the head
 * pointer, the queue is empty.
 */

And for a linked list, like this:

typedef struct nodeStruc
   {
   struct nodeStruc *next;
   long                     data;
   long                     moreData;
   . . .
   }node,*nodeP;

nodeP   nodeListP[10];

/* allocate 10 (or however many needed) nodes
 * and link them together (or created and link them
 * as needed
 */

nodeP headPtr;
headPtr = nodeListP[0];

I mean, in terms of 'head pointers', usually that mechanism is used only when working with an array or an array of structures.

I hope this was not too far off what you were looking for.

[Troll_King]

struct card_t
{
	int suit, face;
};

struct node_t
{
	struct node_t *next;
	struct card_t card;
	int size;
};

node_t * AddNode(node_t *);

int main()
{
	//This is a pointer to the first node in the list
	//and is used to reference the entire list
	struct node_t *headp;

	//add one node to the list
	headp = AddNode(headp);
	return 0;
}

node_t * AddNode(node_t *returnp) {  
	node_t *newp;
	//allocate space for new node
	//fill new node with information
	//add new node to the head of the list 
	newp->next = returnp; 
	//reassign the returned pointer to the head
	returnp = newp;
	//return the return pointer to the head
	return returnp; 
}

The head pointer node is just used to reference the list. It is your only connection to a singly linked list and is the first node in the list.

[Ausandy]

Thanx, all ! And I still have a question on my case, for example, if I want to create a function which need to insert node into a linked list, which each node hodes a row header of another linked list, like a sparse matrix, I can declare the function prototype like void matrix(matrix *, int row_num, int col_num, int value), how should I define structrue, can I define like following?
typedef struct row_header{
struct dataNode *rowhead;
struct row_header *next;
int rowNum;
}SparseMatrix;

typedef SparseMatrix *rowHeaderPtr;

typedef struct data_node{
struct dataNode *next;
float data;
int colNum;
}dataNode;
thanks to give me a little comments!