C Programming

LINKED LISTS
A linked list is a complex data structure, especially useful in systems or applications programming. A linked list is comprised of a series of nodes, each node containing a data element, and a pointer to the next node, eg,

	 --------           --------
	|  data  |     --->|  data  |
	|--------|    |    |--------|
	| pointer|----     | pointer| ---> NULL
	 --------           --------

A structure which contains a data element and a pointer to the next node is created by,


	struct list {
		int   value;
		struct list  *next;
	};

This defines a new data structure called list (actually the definition of a node), which contains two members. The first is an integer called value. The second is called next, which is a pointer to another list structure (or node). Suppose that we declare two structures to be of the same type as list, eg,


	struct list  n1, n2;

The next pointer of structure n1 may be set to point to the n2 structure by


	/* assign address of first element in n2 to the pointer next of the n1 structure  */
	n1.next = &n2;

which creates a link between the two structures.


	/* LLIST.C    Program to illustrate linked lists */
	#include <stdio.h>
	struct list {
		int         value;
		struct list *next;
	};

	main()
	{
		struct list n1, n2, n3;
		int          i;

		n1.value = 100;
		n2.value = 200;
		n3.value = 300;
		n1.next = &n2;
		n2.next = &n3;
		i = n1.next->value;
		printf("%d\n", n2.next->value);
	}

Not only this, but consider the following


	n1.next = n2.next   	/* deletes n2  */
	n2_3.next = n2.next;	/* adds struct n2_3 */
	n2.next = &n2_3;

In using linked list structures, it is common to assign the value of 0 to the last pointer in the list, to indicate that there are no more nodes in the list, eg,


	n3.next = 0;