Linked List Concepts

A Linked List is an ordered collection of data in which each element contains the location of the next element; that is, each element contains two parts: data and link. The data part holds the useful information, the data to be processed. The link is used to chain the data together. It contains a pointer that identifies the next element in the list. In addition, a pointer variable identifies the first element in the list. The name of the list is the same as the name of this pointer variable. This pointer variable to the beginning of the list is known as a head pointer. The simple linked list we describe here is commonly known as a singly linked list because it contains only one link to a single successor.

The major advantage of the general linked list over other restricted list structures is that data are easily inserted and deleted. It is not necessary to shift elements of a linked list to make room for a new element or to delete an element. On the other hand, because the elements are no longer physically sequenced, we are limited to sequential searches: we cannot use a binary search.

Figure 3 shows a linked list, pHead (for pointer to the head of the list), that contains four elements. The link in each element except the last points to its successor. The link in the last element contains a null pointer, indicating the end of the list. We define an empty linked list to be a null head pointer. Figure 3 also contains an example of an empty linked list.

Nodes

The elements in a linked list are traditionally called nodes. A node in a linked list is a structure that has at least two fields: one contains the Data, the other the address of the next node in the sequence. Figure 4 shows three different node structures. The first node contains a single field, number, and a link. The second node contains three data fields, a name, id, and grade points (grdpts), and a link. The third example is the one we recommend. The fields are defined in their own structure, which is then put into the definition of a node structure. The one common element in all examples is the link field.

The nodes in a linked list are called self-referential structures. In a self-referential structure, each instance of the structure contains a pointer to another instance of the same structural type. In Figure 4, the shaded boxes with arrows are the links that make the linked list a self-referential structure.