LINKED LIST REPRESENTATION

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;