Linked Structures and Pointers

Linked structures and pointers are essentially containers that give us a way to store items in memory. Whilst linked structures provide the same functionality as an array (search, insertion and deletion), they are quite different in terms of its data structure, how the items are connected together and how the various operations (search, insertion and deletion) are performed.

To generalise, a linked structure contains the following -

1. Item - The item that is to be stored in this structure.
2. Pointer - A pointer to the next structure.

Pointers are the connections that hold linked structures together. As the name suggests, they "point" to the location in memory where the next linked structure is located. This is needed because linked structures can potentially reside in any place in memory and are not necessarily located next to each other like array indices are, therefore a pointer is needed to lead us in the right direction towards the next item.

When a bunch of linked structures are connected together with these pointers, it becomes a linked list.

A real world example of a linked list would be an address book. 

Figure 1 - Linked List representation of address book items (names) and pointers.

To apply the generalisation of a linked structure that we defined above to our address book example, we would have - 

1. Item - The contact information for an individual (John, Sue, Dave)
2. Pointer - A connection that points to the next person in the address book.

Data Structure Representation

Below is the generalised linked structure represented in code.

/**
 * The Node class represents a single node
 * in a linked structure.
 * 
 * A node acts as container to allow us to
 * store data.
 * 
 */
public class Node {

 /**
  * The data that this node stores.
  */
 private String name;

 /**
  * The pointer to the next node.
  */
 private Node nextNode;

 /**
  * The constructor to initialise the new node.
  * @param nameTmp - The name to store in this node.
  */
 public Node(String nameTmp) {
  name = nameTmp;
  nextNode = null;
 }
}

Figure 2 - Generalised linked structure represented in code.

A single linked structure is called a node and contains the following basic properties -

1. Each node can contain one or more fields of data to be stored (i.e - a single contact in an address book can have a name, email, phone number etc.). In the above example, our node only contains a single field for a name.


2. Each node can contain one or more pointers that point to other nodes. In the node above, we only have a pointer to the next node.


3. A pointer to the head of the linked structure is required as it is our point of access to all the other connected nodes.

Because each node in a linked list requires a pointer to its next node, we require additional space in memory dedicated to maintain these connections otherwise. If we didn't, then we wouldn't know how to navigate from one node to another.

List Operations - 

In the simplest of list structures (single and double linked lists), there are three main operations, search, insertion, and deletion. Depending on the chosen list structure, these operations are implemented slightly differently. We shall explore these different implementations in the next post.