Example 88: Implementation of a Linked List

Problem

The elements of an array occupy contiguous memory locations, whereas the linked list elements are not constrained to be stored in adjacent locations.
The individual elements are stored “somewhere” in memory, rather like a family dispersed but still bound together. The order of the elements is maintained by explicit links between them.

The linked list is a collection of elements called nodes, each of which stores two items of information:

• An element of the list
• A link pointing to the next element

A link is a pointer or an address that explicitly indicates the node’s location containing the successor of the list element.

Figure 1a below shows you the node structure, while Figure 1b shows you a complete linked list with 4 nodes. The data stored in each node is the marks obtained by different students. The arrows represent the links that point to the next node in the list. The NULL in the last node indicates that this is the last node in the list.

You can perform several operations on a linked list. In this lesson, you will learn how to:

• Build a linked list by adding new nodes at the beginning, at the end, or in the middle of the linked list.
• Display the contents of each node in a list.
• Delete a node from a linked list.

In this lesson, you will learn how to implement a linked list.