Link List

 Linked list is a linear data structure. It is a collection of data elements, called nodes pointing to the next node by means of a pointer.

Linked list is used to create trees and graphs.

In linked list, each node consists of its own data and the address of the next node and forms a chain.

The above figure shows the sequence of linked list which contains data items connected together via links. It can be visualized as a chain of nodes, where every node points to the next node.

Linked list contains a link element called first and each link carries a data item. Entry point into the linked list is called the head of the list.

Link field is called next and each link is linked with its next link. Last link carries a link to null to mark the end of the list.

Note: Head is not a separate node but it is a reference to the first node. If the list is empty, the head is a null reference.

Linked list is a dynamic data structure. While accessing a particular item, start at the head and follow the references until you get that data item.

Linked list is used while dealing with an unknown number of objects:

In the above diagram, Linked list contains two fields - First field contains value and second field contains a link to the next node. The last node signifies the end of the list that means NULL.

The real life example of Linked List is that of Railway Carriage. It starts from engine and then the coaches follow. Coaches can traverse from one coach to other, if they connected to each other.

Advantages of Linked List

• Linked list is dynamic in nature which allocates the memory when required.
• In linked list, stack and queue can be easily executed.
• It reduces the access time.
• Insert and delete operation can be easily implemented in linked list.

Disadvantages of Linked List

• Reverse traversing is difficult in linked list.
• Linked list has to access each node sequentially; no element can be accessed randomly.
• In linked list, the memory is wasted as pointer requires extra memory for storage.

Types of Linked List

Following are the various types of linked list.

• Simple Linked List − Item navigation is forward only.

• A singly linked list is the most common type of linked list. Each node has data and an address field that contains a reference to the next node.

• 

• Doubly Linked List − Items can be navigated forward and backward.

• There are two pointer storage blocks in the doubly linked list. The first pointer block in each node stores the address of the previous node. Hence, in the doubly linked inventory, there are three fields that are the previous pointers, that contain a reference to the previous node. Then there is the data, and last you have the next pointer, which points to the next node. Thus, you can go in both directions (backward and forward).

• Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

       Basic Operations

          Following are the basic operations supported by a list.

Traversal 

In this operation, you will display all the nodes in the linked list.

When the temp is null, it means you traversed all the nodes, and you reach the end of the linked list and get out from the while loop.

struct node * temp = start;

printf(“\n list empty are-”);

while (temp!= NULL)

{

 printf(‘%d “, temp -> data)

 temp=temp -> next;

}

• Insertion − You can add a node at the beginning, middle, and end.

• Insert at the Beginning

  Create a memory for a new node.

  Store data in a new node.

  Change next to the new node to point to start.

  Change starts to tell the recently created node.

  Insert at the End

  Insert a new node and store data in it.

  Traverse the last node of a linked list

  Change the next pointer of the last node to the newly created node.

  Insert at the Middle

  Allocate memory and store data in the new node.

  Traverse the node, which is just before the new node.

  Change the next pointer to add a new node in between.

• Deletion - You can also do deletion in the linked list in three ways either from the end, beginning, or from a specific position.

• Delete from the Beginning

  The point starts at the second node.

  Delete from the End

  Traverse the second last element in the linked list.

  Change its next pointer to null.

  Delete from the Middle

  Traverse the element before the element to be deleted.

  Change the next pointer to exclude the node from the linked list.

• Searching 

  The search operation is done to find a particular element in the linked list. If the element is found in any location, then it returns. Else, it will return null.