Linked List Data Structure
A linked list is a linear data structure used to stores similar data in memory. The elements in the linked list are not stored in adjacent memory locations but are stored randomly. The linked list is a collection of elements known as nodes which contains two fields of information. One contains the data items and the other contains the link or address of the successor list element. A node can be represented as,
There are different types of linked lists that are formatted by changing the link position. They are,
 Singlylinked list
 Double linked list
 Circular linked list
Table of Contents
Difference between the linked list and an array
Array  Linked list 


Singly Linked List
A singly linked list is a list in which each node is linked with others. A node is a structure element containing data and link field.
What is Node?
The node in the list need not be stored in the contiguous memory location. A node can contain any number of data fields but only one link field.
Advantage Of Single Linked List
 The singly linked list is simple to implement compared to a circular and doubly linked list.
Disadvantages Of Single Linked List
 If the address of the first node is lost, then the linked list can’t be accessed.
 For deletion operation, in addition to the address X of the node to be deleted we also need the address of the first node to reach predecessor of X. So it is not efficient to perform deletion operation.
Suppose we want to delete an element at the position i, we need the node at position (i1) to link to (i+1) node. This can only be obtained by traversal from the first addressed node to (i1) position.
 Every node is not accessible by its successor. A linked list can be traversal only in one direction.
 In the above diagram of a singly linked list, the address of the 3rd node is stored in the link field of the second node, address of the second node is stored in the link field of the first node and the address of the first node is stored in a pointer called as root. This pointer is not a part of the list rather list holds the value NULL in its link field, indicating the end of the list.
Basics Operations on the Singly Linked List
 Traversal
 Insertion
 Deletion
Single Lined list traversal
The singly linked list can be traversed in the direction from the first node to the last node using the pointer root or head or FIRST.
Algorithm: Traversal (FIRST)
 Step 1: temp=FIRST [ temp is a temporary pointer for traversing the tree]
 Step 2: Till
temp > link != NULL
repeat through step 3.  Step 3:
temp=temp > link
 Step 4: return
Single Lined list Insertion
The insertion of a node into a singly linked list can be at different locations i.e., at beginning of list at a specified location in the list, or at the end of the list.
Insertion of the node at the Beginning of list
To inserts a node at the beginning. Make the link field of new node point to the first node and make the FIRST pointer to point to the new node.
Algorithm: insert at the beginning (element, FIRST)
 Step 1: create a new node ( i.e. allocate memory, returning a pointer ‘new’)
 Step 2: new > data=element[insert data into node created]
 Step 3: new – > link=FIRST[New node pointer to the first node]
 Step 4: FIRST=new[FIRST pointer pointing to new node]
 return
Insertion of node at the Specified Position
To insert a new node between the ith and (i+1)th node, the list should be initially traversed up to ith node, then the link field of ith node should be made to point to a new node and the link field of the new node is made to point to (i+1)th node.
Algorithm: insert at a specified location (element, FIRST, loc)
 Step 1: create a new node
 Step 2: new > data=element
 Step 3: temp=FIRST[temp is a temporary pointer for traversing the list]
 Step 4: if loc=1 then call insert at the beginning(FIRST)
 Step 5: if loc=n+1 then call insert at ending(FIRST)
 Step 6: otherwise for i=1 to i=loc1
temp=temp > link[traversing the list up to ith position][repeat step 6 until i=loc1]
new > link=templink
temp > link=new[inserting the node at the specified location]
 return
Insert of node at the End of List
To insert a node at the end of the singly linked list traverse the list up to the last node, then make the link of the last node point to a new node. Make the link field of new node point to NULL.
Algorithm: insert at the end (element, FIRST)
 Step 1: create a new node
 Step 2: new > link=NULL
 Step 3: new > data=element
 Step 4: temp=FIRST
 Step 5: until temp!=NULL repeat step 6
 Step 6: temp=temp > link[traversing]
 Step 7: temp > link=new[inserting node at end]
 Step 8: return
Single Lined list Deletion
A node can be deleted from the singly linked list in two ways, i.e., logically, physically. In logical deletion, the node is no more present in the list (i.e., reference to the node is broken) but physically present in the memory. But, in physical deletion of the node, the node is permanently deleted by deallocating (free) the memory allocated to the node.
The deletion of a node at different locations in the list, i.e., in the beginning, at the specified location, at the end can be implemented through the following algorithms.
Deletion of node at the Beginning
Algorithm: delete at the Beginning (FIRST)
 Step 1: if FIRST=NULLprint “list is empty” deletion not possible return
 Step 2: else
FIRST=FIRSTlink[making the FIRST pointer to point to the second node]
[logically deleting the first node]
 Step 3: return
 Deletion of Node at Specified Location
 In order to delete ith node, we have to traverse the list upto (i+1)th node.
 Step 1: declare a variable i=1 and a pointer variable temp
 Step 2: check, if FIRST=NULL, then print “deletion not possible” return
 Step 3: assign temp=FIRST[temp is a pointer for traversing]
 Step 4: check if loc==1 [if the node to be deleted is the first node] then, call delete at the beginning(FIRST) else, if loc==n[if the node to be deleted is the last node] then, call delete at the end(FIRST)
 Step 5: check, if (loc>1 and loc<n) then, until i<loc1 go through step 6 and step 7.
 Step 6: increment I by 1
 Step 7: temp=templink[traversing the list]
 Step 8: temp > link=NULL [logically deleting the specified node]
 Step 9: return
Deletion of node at End
To delete a node at the end, traverse the list up to last but one node and store and store NULL in its link field.
Algorithm: delete at the end (FIRST)
 Step 1: if FIRST =NULL print “deletion not possible, list empty” return
 Step 2: temp=FIRST [temp is temporary pointer]
 Step 3: until templink!=NULL, repeat step 4[traverse the list up to last but one node]
 Step 4: temp=templink
 Step 5: templink=NULL[logically deleting the last node]
 Step 6: return