Introduction to Linked List

Linked List is a data structure, which contains a collection of data elements (generally termed as Nodes) in such a way that any node except the last one, holds the address of its next node.

Hence, every node in the linked list has two parts, one to store the actual data and the other to hold the memory address of the next node. The following figure depicts the structure of a node.

The following figure shows the relationship among the nodes. The address of each node is written below the respective nodes. The first field of a node represents data and the second field represents the address of the next node.

So, the list can be represented as below.

In the rest of the tutorials, we will represent linked lists like this.

The main advantage of a linked list is that the data elements need not be stored in contiguous memory locations. Hence, instead of declaring the chunk of memory with a large size, in a linked list, memory can be better utilized by allocating or deallocating at run-time according to the application requirement.

Though in this tutorial, for the sake of simplicity, we will consider a linked list node having only one integer element, in real applications a node might contain any data.

---

How to define a Node?

---

As we have discussed, a linked list node will have the info and an address part. The address part will be realized by a pointer and the info part will be realized by corresponding primitive or derived or even an Abstract Data Type based on the nature of the application. For example, the node of the linked list shown in the above Figures will have its info part as a primitive data type int. Hence the node as a whole must store two heterogeneous data, hence we must use a derived data type structure to implement a linked list node.

A node of the linked list shown in the above figures could be defined as follow

struct Node {
	int info;
	struct Node *next;
};				

Please note that the node is being realized by a structure with a name Node. The info part of Node is realized by a int type variable info. Similarly, the address part is realized by a pointer variable next of type struct Node.

As a node of a linked list contains a pointer of the same type, hence a liked list is also termed a Self Referential Data Structure.

---

Linked List as a Linear Data Structure

---

Linked List is an example of Linear Data Structure. The linked list shown in the above Figure reveals that to access the first data, we need to do one reference traversal, to access the second and third data, we need to do two and three reference traversals respectively, and so on. Hence the data access curve as discussed here represents a Linear Function.

There are three types of linked lists we generally use. Single linked list, Double linked list, and Circular linked list are the three different types that we will discuss next.

---

Happy Exploring!