Before understanding the linked list concept, we first look at why there is a need for a linked list. If we want to store the value in a memory, we need a memory manager that manages the memory for every variable. For example, if we want to create a variable of integer type like: int x;   In the above example, we have created a variable 'x' of type integer. As we know that integer variable occupies 4 bytes, so 'x' variable will occupy 4 bytes to store the value. Suppose we want to create an array of integer type like: int x[3];   In the above example, we have declared an array of size 3. As we know, that all the values of an array are stored in a continuous manner, so all the three values of an array are stored in a sequential fashion. The total memory space occupied by the array would be 3*4 = 12 bytes. There are two major drawbacks of using array: We cannot insert more than 3 elements in the above example because only 3 spaces are allocated for 3 elements. In the case of an array, lots of wastage of memory can occur. For example, if we declare an array of 50 size but we insert only 10 elements in an array. So, in this case, the memory space for other 40 elements will get wasted and cannot be used by another variable as this whole space is occupied by an array. In array, we are providing the fixed-size at the compile-time, due to which wastage of memory occurs. The solution to this problem is to use the linked list. What is Linked List? A linked list is also a collection of elements, but the elements are not stored in a consecutive location. Suppose a programmer made a request for storing the integer value then size of 4-byte memory block is assigned to the integer value. The programmer made another request for storing 3 more integer elements; then, three different memory blocks are assigned to these three elements but the memory blocks are available in a random location. So, how are the elements connected?. These elements are linked to each other by providing one additional information along with an element, i.e., the address of the next element. The variable that stores the address of the next element is known as a pointer. Therefore, we conclude that the linked list contains two parts, i.e., the first one is the data element, and the other is the pointer. The pointer variable will occupy 4 bytes which is pointing to the next element. A linked list can also be defined as the collection of the nodes in which one node is connected to another node, and node consists of two parts, i.e., one is the data part and the second one is the address part, as shown in the below figure: In the above figure, we can observe that each node contains the data and the address of the next node. The last node of the linked list contains the NULL value in the address part. How can we declare the Linked list? The declaration of an array is very simple as it is of single type. But the linked list contains two parts, which are of two different types, i.e., one is a simple variable, and the second one is a pointer variable. We can declare the linked list by using the user-defined data type known as structure. The structure of a linked list can be defined as: struct node   {      int data;      struct node *next;   }   In the above declaration, we have defined a structure named as a node consisting of two variables: an integer variable (data), and the other one is the pointer (next), which contains the address of the next node. Advantages of using a Linked list over Array The following are the advantages of using a linked list over an array: Dynamic data structure: The size of the linked list is not fixed as it can vary according to our requirements. Insertion and Deletion: Insertion and deletion in linked list are easier than array as the elements in an array are stored in a consecutive location. In contrast, in the case of a linked list, the elements are stored in a random location. The complexity for insertion and deletion of elements from the beginning is O(1) in the linked list, while in the case of an array, the complexity would be O(n). If we want to insert or delete the element in an array, then we need to shift the elements for creating the space. On the other hand, in the linked list, we do not have to shift the elements. In the linked list, we just need to update the address of the pointer in the node. Memory efficient Its memory consumption is efficient as the size of the linked list can grow or shrink according to our requirements. Implementation Both the stacks and queues can be implemented using a linked list. Disadvantages of Linked list The following are the disadvantages of linked list: Memory usage The node in a linked list occupies more memory than array as each node occupies two types of variables, i.e., one is a simple variable, and another is a pointer variable that occupies 4 bytes in the memory. Traversal In a linked list, the traversal is not easy. If we want to access the element in a linked list, we cannot access the element randomly, but in the case of an array, we can randomly access the element by index. For example, if we want to access the 3rd node, then we need to traverse all the nodes before it. So, the time required to access a particular node is large. Reverse traversing In a linked list, backtracking or reverse traversing is difficult. In a doubly linked list, it is easier but requires more memory to store the back pointer. Applications of Linked List The applications of the linked list are given below: With the help of a linked list, the polynomials can be represented as well as we can perform the operations on the polynomial. We know that polynomial is a collection of terms in which each term contains coefficient and power. The coefficients and power of each term are stored as node and link pointer points to the next element in a linked list, so linked list can be used to create, delete and display the polynomial. A sparse matrix is used in scientific computation and numerical analysis. So, a linked list is used to represent the sparse matrix. The various operations like student's details, employee's details or product details can be implemented using the linked list as the linked list uses the structure data type that can hold different data types. Stack, Queue, tree and various other data structures can be implemented using a linked list. The graph is a collection of edges and vertices, and the graph can be represented as an adjacency matrix and adjacency list. If we want to represent the graph as an adjacency matrix, then it can be implemented as an array. If we want to represent the graph as an adjacency list, then it can be implemented as a linked list. To implement hashing, we require hash tables. The hash table contains entries that are implemented using linked list. A linked list can be used to implement dynamic memory allocation. The dynamic memory allocation is the memory allocation done at the run-time. What are Linked Lists? The linked list is just a very simple data structure that represents a sequence of nodes. Each node is just an object that contains a value and a pointer to the next node. For example, In the example here we have a node that contains the data 12 and points to the next node 99. Then 99 points to node 37 and so on until we encounter a NULL Node. There are also doubly linked lists in which each node contains the address of the next as well as the previous node. But why would we ever need Linked Lists? We all have worked with Lists in Python. But have you ever thought of the insertion time for the list data structure? Lets say we need to insert an element at the start of a list. Inserting or removing elements at the start in a python list requires an O(n) copy operation What if we are faced with the problem in which there are a lot of such inserts and we need a data structure that actually does inserts in constant O(1) time? There are many practical applications of a linked list that you can think about.  One can use a doubly-linked list to implement a system where only the location of previous and next nodes are needed. For example, the previous page and next page functionality in the chrome browser. Or the previous and next photo in a photo editor. Another benefit of using a linked list is that we don’t need to have contiguous space requirements for a linked list i.e. the nodes can reside anywhere in the memory while for a data structure like an array the nodes need to be allocated a sequence of memory. Types of Linked List Following are the types of Linked List 1. Singly Linked List 2. Doubly Linked List 3. Circular Linked List 4. Doubly Circular Linked List 1. Singly Linked List Each node has a single link to another node is called Singly Linked List. Singly Linked List does not store any pointer any reference to the previous node. Each node stores the contents of the node and a reference to the next node in the list. In a singly linked list, last node has a pointer which indicates that it is the last node. It requires a reference to the first node to store a single linked list. It has two successive nodes linked together in linear way and contains address of the next node to be followed. It has successor and predecessor. First node does not have predecessor while last node does not have successor. Last node have successor reference as NULL. It has only single link for the next node. In this type of linked list, only forward sequential movement is possible, no direct access is allowed. In the above figure, the address of the first node is always store in a reference node known as Head or Front. Reference part of the last node must be null. 2. Doubly Linked List Doubly linked list is a sequence of elements in which every node has link to its previous node and next node. Traversing can be done in both directions and displays the contents in the whole list. In the above figure, Link1 field stores the address of the previous node and Link2 field stores the address of the next node. The Data Item field stores the actual value of that node. If we insert a data into the linked list, it will be look like as follows: Important Note: First node is always pointed by head. In doubly linked list, previous field of the first node is always NULL (it must be NULL) and the next field of the last must be NULL. In the above figure we see that, doubly linked list contains three fields. In this, link of two nodes allow traversal of the list in either direction. There is no need to traverse the list to find the previous node. We can traverse from head to tail as well as tail to head. Advantages of Doubly Linked List Doubly linked list can be traversed in both forward and backward directions. To delete a node in singly linked list, the previous node is required, while in doubly linked list, we can get the previous node using previous pointer. It is very convenient than singly linked list. Doubly linked list maintains the links for bidirectional traversing. Disadvantages of Doubly Linked List In doubly linked list, each node requires extra space for previous pointer. All operations such as Insert, Delete, Traverse etc. require extra previous pointer to be maintained. 3. Circular Linked List Circular linked list is similar to singly linked list. The only difference is that in circular linked list, the last node points to the first node in the list. It is a sequence of elements in which every element has link to its next element in the sequence and has a link to the first element in the sequence. In the above figure we see that, each node points to its next node in the sequence but the last node points to the first node in the list. The previous element stores the address of the next element and the last element stores the address of the starting element. It forms a circular chain because the element points to each other in a circular way. In circular linked list, the memory can be allocated when it is required because it has a dynamic size. Circular linked list is used in personal computers, where multiple applications are running. The operating system provides a fixed time slot for all running applications and the running applications are kept in a circular linked list until all the applications are completed. This is a real life example of circular linked list. We can insert elements anywhere in circular linked list, but in the array we cannot insert elements anywhere in the list because it is in the contiguous memory. 4. Doubly Circular Linked List Doubly circular linked list is a linked data structure which consists of a set of sequentially linked records called nodes. Doubly circular linked list can be conceptualized as two singly linked lists formed from the same data items, but in opposite sequential orders. The above diagram represents the basic structure of Doubly Circular Linked List. In doubly circular linked list, the previous link of the first node points to the last node and the next link of the last node points to the first node. In doubly circular linked list, each node contains two fields called links used to represent references to the previous and the next node in the sequence of nodes. Applications of Linked List data structure Linked Lists can be used to implement Stacks , Queues. Linked Lists can also be used to implement Graphs. (Adjacency list representation of Graph). Implementing Hash Tables :- Each Bucket of the hash table can itself be a linked list. (Open chain hashing). Undo functionality in Photoshop or Word . Linked list of states. A polynomial can be represented in an array or in a linked list by simply storing the coefficient and exponent of each term. However, for any polynomial operation , such as addition or multiplication of polynomials , linked list representation is more easier to deal with. Linked lists are useful for dynamic memory allocation. The real life application where the circular linked list is used is our Personal Computers, where multiple applications are running. All the running applications are kept in a circular linked list and the OS gives a fixed time slot to all for running. The Operating System keeps on iterating over the linked list until all the applications are completed.