What is Linked List ?

    A linked list is a fundamental data structure in computer science. It consists of nodes where each node contains data and a reference (link) to the next node in the sequence. This allows for dynamic memory allocation and efficient insertion and deletion operations compared to arrays.

    • Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
    • A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
    • The last node of the list contains pointer to the null.

    Singly linked list :

    Singly linked list can be defined as the collection of ordered set of elements.

    • The number of elements may vary according to need of the program.
    • A node in the singly linked list consist of two parts: data part and link part.
    • Data part of the node stores actual information that is to be represented by the node while the link part of the node stores the address of its immediate successor.

    Consider an example where the marks obtained by the student in three subjects are stored in a linked list as shown in the figure.

    Complexity

    Operations in Singly linked list :

    There are various operations which can be performed on singly linked list. A list of all such operations is given below.

    Insertion

    The insertion into a singly linked list can be performed at different positions. Based on the position of the new node being inserted, the insertion is categorized into the following categories.

    Deletion and Traversing

    The Deletion of a node from a singly linked list can be performed at different positions. Based on the position of the node being deleted, the operation is categorized into the following categories.

    Advantages of Singly Linked List

    • Less memory is required for storing the members (2 members – data and next)
    • During execution, we can deallocate or allocate memory very easily.
    • Insertion and Deletion don’t require the shifting of all elements as required in the array.

    Disadvantages of Singly Linked List

    • Insertion and Deletion of element require O(N) time.
    • Accessing the previous node is not possible since we do not have prev pointer.