Node:Linked lists, Next:Binary trees, Previous:Lists and trees, Up:Lists and trees

Linked lists.

A linked list is a linear sequence of structures joined together by pointers. Each node's pointer links to the next node in the sequence. Linked lists have two main advantages over one dimensional arrays: they can be sorted easily simply by redirecting pointers, and they can be made any length at all dynamically.

Here is an example of a structure type from a linked list:

struct list_node
{
  double value;
  struct list_node *next;
};

Here the value member holds the actual content of the node, in this case a double-precision floating-point number, and the next member points to the next node in the list.

You will often encounter another basic kind of linked list, called a doubly-linked list. Each node in a doubly-linked list contains not only a pointer to the next node, but also to the previous node. This kind of list makes it easier to determine what the node preceding a node is, as well as the node succeeding it.