Introduction to Single Linked List

Today we are going to talk about a frequently used data structure called Linked list. The linked list is a data structure for storing lists of elements. Now the question arises when we have array data structure to store list why do we need to use linked lists.

  1. In array, elements are stored in contiguous memory locations while in linked lists, it is not necessary elements are stored in contiguous memory locations.
  2. .Cost of insertion/deletion is expensive while it is comparatively easy to delete/insert element in linked list. To insert an element in the beginning or somewhere in between the list, first, we need to shift complete list to the right side and then insert element. Same is the case with deletion of the element .
  3. Arrays are of fixed size while linked lists are of dynamic size.
Single Linked List

Fig: 1 This is how a typical single linked list looks (Picture credit: geeksforgeeks.org)

In a linked list, an element is usually referred to as a node which stores the data value and a pointer Next to next element. The first node of the list is called head node which stores data value of first node and a pointer to the second node. Now, what makes single linked list different from a double or circular linked list is its traversal.

Every node in a single linked list points only to its next element and it is traversed in forwarding direction while in the double linked list, anode stores a pointer to its next as well as the previous element which means it can be traversed in forward and backward direction.

Here is how to create a linked list-

struct node {
            int value;  //data value 
            struct node *next;  //pointer to next node.
           };
typedef struct node node;
int main()
{ 
// assign three nodes in the list
   node *first=NULL;
   node *second=NULL;
   node *third=NULL;
  
// allocate memory to each of the three nodes and assigning the data and making a list
//first node
   first=(node*)malloc(sizeof(node));
   first->value=1;
   first->next=second;     //pointing to decond node

//second node
   second=(node*)malloc(sizeof(node));
   second->value=2;
   second->next=third;     //pointing to third node

//third node
   third=(node*)malloc(sizeof(node));
   third->value=3;
   third->next=NULL;      //marks the end of the list
   
return 0;
}

Operations that can be performed on a single linked list are:

1. Insertion
2.Deletion

 

Also, read:

 

Now insertion can also be further categorized as:

  • ¬†Insertion in the beginning
  • The insertion in between of two elements
  • Insertion at the end of list

Similarly, we can also categorize deletion as:

  • ¬†Deletion from the beginning
  • Deletion from the end of the list
  • The deletion from somewhere in between

Implementation of insertion, deletion and traversal in linked list will be discussed in further posts.

Leave a Reply

Your email address will not be published. Required fields are marked *