Data Structure : Singly Linked list

Singly linked list is a basic linked list type. Singly linked list is a collection of nodes linked together in a sequential way where each node of singly linked list contains a data field and an address field which contains the reference of the next node. Singly linked list can contain multiple data fields but should contain at least single address field pointing to its connected next node.

Singly linked list

To perform any operation on a linked list we must keep track/reference of the first node which may be referred by head pointer variable. In singly linked list address field of last node must contain a NULL value specifying end of the list.

Basic structure of a singly linked list

Each node of a singly linked list follows a common basic structure. In a node we can store more than one data fields but we need at least single address field to store the address of next connected node.

struct node {
    int data;           // Data 
    struct node * next; // Address 
};

Advantages of Singly linked list

There are several points about singly linked list that makes it an important data structure.

  • Singly linked list is probably the most easiest data structure to implement.
  • Insertion and deletion of element can be done easily.
  • Insertion and deletion of elements doesn’t requires movement of all elements when compared to an array.
  • Requires less memory when compared to doubly, circular or doubly circular linked list.
  • Can allocate or deallocate memory easily when required during its execution.
  • It is one of most efficient data structure to implement when traversing in one direction is required.

Disadvantages of Singly linked list

After seeing the advantages of singly linked list. Singly linked list also has some disadvantages over other data structures.

  • It uses more memory when compared to an array.
  • Since elements are not stored sequentially hence requires more time to access each elements of list.
  • Traversing in reverse is not possible in case of Singly linked list when compared to Doubly linked list.
  • Requires O(n) time on appending a new node to end. Which is relatively very high when compared to array or other linked list.