Linked List Data Structure

One of the attributes of a linked list is that there is not a physical relationship between the nodes,

Without a physical relationship between the nodes, we need pointers to distinguish the beginning of the list¾that is, to identify the first logical node in the list and the location of any given node’s immediate successor. The pointer to the beginning of the list is known as a head pointerbecause it points to the node at the head of the list. In Figure 3, we call the head pHead and the pointer that identified a node’s immediate successor link.

Head Node Structure

Although only a single pointer is needed to identify the list, we often find it convenient to create a structure that stores the head pointer and other data about the list itself. When a node contains data about a list, the data are known as metadata; that is, they are data about data in the list. For example, the head structure in Figure 5 contains one piece of metadata: count, an integer that contains the number of nodes currently in the list. Other metadata, such as the maximum number of nodes during the processing of the list and other additional pointers etc are often included when they serve a useful purpose.

Data Node Structure

The data type for the list depends entirely on the application. Node data structure is shown in Figure 5 in detail. It contains the data type and link. Link is a pointer to another data structure of its own type. We can thus create our linked list structure in which one instance of a node points to another instance of the node, making it a self-referential list.

Implementation of Lists

There are two ways to implement linked lists, one is array implementation and the other using dynamic variables with pointers.

a) Array Implementation of Linked Lists

Since a list is a collection of nodes in sequence, an array of nodes can be used for its implementation. However, the nodes cannot be ordered by the array ordering, i.e the nodes of a list need not occupy adjacent elements in arrays. Each node must contain within its structure a pointer to its successor.

Furthermore, more than one list may be maintained in the same array, with each list having its own pointer variable giving the location of its first node.

In C, a group of 500 nodes might be declared as an array node as follows:

#define NUMNODES 500

struct nodetype

{

int data, link;

};

Struct nodetype node [NUMNODES];

In this scheme a pointer to a node is represented by an array index. That is, a pointer is an integer between 0 andNUMNODES -1 that references a particular element of the array node. The null pointer is used to show the end of list. Under this implementation, the C expression node[p] is used to reference node(p), data(p) is referenced by node[p].data, and link(p) is referenced by node[p].link.

For example, suppose that the variable list1 represents a pointer to a list. If list1 has the value 16, node[16] is the first node on the list, and node[16].data is the first data item on the list. The second node of the list is given by node[16].link. Suppose the node[16].link equals 20. The node[20].data is the second data item on the list and node[20].link pointer to the third node.

The nodes of a list may be scattered throughout the array node in any arbitrary order. Each node carries within itself the location of its successor until the last node in the list, whose link field contains Null, which is the null pointer. There is no relation between the contents of a node and the pointer to it. The pointer, p, to a node merely specifies which element of the array node is being referenced; it is node[p].data that represents the information contained within that node.

Figure 6 illustrates a portion of an array node that contains four linked lists. The list list1 starts at node[16] and contains the integers 3, 7, 14, 6, 5, 37, 12. The nodes that contain these integers in their data fields are scattered throughout the array. The link field of each node contains the index within the array of the nodes containing the next element of the list. The last node on the list is node[23], which contains the integer 12 in its data field and the null pointer in its link field, to indicate that it is last on the list.

Similarly, list2 begins at node[4] and contains the integers 17 and 26, list3 begins at node[11] and contains the integers 31, 19 and 32 and list4 begins at node[3] and contains the integers 1, 18, 13, 11, 4, and 15. The variables list1, list2, list3, and list4 are integers representing external pointers to the four lists. Thus, the fact that the variable list2 has the value 4 represents the fact that the list to which it points begins at node[4].