Singly Linked List

A Singly Linked List is a simple and dynamic linear data structure in which elements are stored in separate nodes connected through links. Each node contains data and the address of the next node. Unlike arrays, nodes in a linked list are not stored in contiguous memory locations.

The singly linked list allows traversal in only one direction, from the first node to the last node.

Linked lists are widely used when the size of data changes frequently during program execution. In arrays, insertion and deletion are costly because elements need to be shifted. Singly linked lists solve this problem by connecting nodes using pointers.

In a singly linked list:

  • The first node is called the head
  • The last node points to NULL
  • Traversal is possible only in forward direction

Because of its simple structure and efficient memory usage, singly linked lists are one of the most important data structures in computer science.

Structure of Singly Linked List

Each node in a singly linked list contains two parts:

PartDescription
DataStores the actual value
Next PointerStores address of next node

Example

[10 | * ] → [20 | * ] → [30 | NULL]

Here:

  • 10, 20, and 30 are data values
  • The pointer connects nodes together
  • NULL indicates the end of the list

A singly linked list node is commonly represented using structure in C language.

C Structure

struct Node {
    int data;
    struct Node* next;
};

Here:

  • data stores the value
  • next stores the address of next node

Features of Singly Linked List

  • Dynamic memory allocation
  • Efficient insertion and deletion
  • Memory is utilized as needed
  • Nodes can be stored anywhere in memory
  • Traversal possible only in one direction

Operations on Singly Linked List

The common operations performed on singly linked list are:

  • Creation
  • Traversal
  • Insertion
  • Deletion
  • Searching
  • Display

1. Creation of Singly Linked List

Creation means making a new node and assigning data to it. Initially, the next pointer is set to NULL.

Algorithm

CREATE_NODE(value)

1. Allocate memory for new node
2. Store value in node
3. Set next = NULL
4. Return node

C Program

struct Node* createNode(int value) {

    struct Node* newNode =
        (struct Node*)malloc(sizeof(struct Node));

    newNode->data = value;
    newNode->next = NULL;

    return newNode;
}

Example

[10 | NULL]

2. Traversal Operation

Traversal means visiting each node one by one from the beginning to the end.

Traversal is used to:

  • Display nodes
  • Count nodes
  • Access all elements

Example

10 → 20 → 30 → NULL

Traversal Output:

10 20 30

Algorithm

TRAVERSE(head)

1. temp = head
2. While temp ≠ NULL
       Print temp.data
       temp = temp.next
3. Stop

C Program

void traverse() {

    struct Node* temp = head;

    while(temp != NULL) {

        printf("%d ", temp->data);
        temp = temp->next;
    }
}

3. Insertion Operation

Insertion means adding a new node into the linked list.

Insertion can be performed:

  • At beginning
  • At end
  • At specific position

A. Insertion at Beginning

In this method, a new node becomes the first node of the list.

Example

Before insertion:

20 → 30 → NULL

After inserting 10:

10 → 20 → 30 → NULL

Algorithm

INSERT_BEGIN(head, value)

1. Create new node
2. new.next = head
3. head = new

C Program

void insertBegin(int value) {

    struct Node* newNode =
        createNode(value);

    newNode->next = head;
    head = newNode;
}

B. Insertion at End

In this method, the new node is added after the last node.

Example

Before insertion:

10 → 20 → NULL

After inserting 30:

10 → 20 → 30 → NULL

Algorithm

INSERT_END(head, value)

1. Create new node
2. Traverse to last node
3. last.next = new node

C Program

void insertEnd(int value) {

    struct Node* newNode =
        createNode(value);

    if(head == NULL) {
        head = newNode;
        return;
    }

    struct Node* temp = head;

    while(temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = newNode;
}

4. Deletion Operation

Deletion removes nodes from the linked list.

Deletion can occur:

  • From beginning
  • From end
  • From specific position

A. Delete from Beginning

The first node is removed and the head moves to the next node.

Example

Before deletion:

10 → 20 → 30 → NULL

After deletion:

20 → 30 → NULL

Algorithm

DELETE_BEGIN(head)

1. temp = head
2. head = head.next
3. Delete temp

C Program

void deleteBegin() {

    if(head == NULL)
        return;

    struct Node* temp = head;

    head = head->next;

    free(temp);
}

B. Delete from End

The last node is removed from the linked list.

Example

Before deletion:

10 → 20 → 30 → NULL

After deletion:

10 → 20 → NULL

Algorithm

DELETE_END(head)

1. Move to second-last node
2. Delete last node
3. Set next = NULL

C Program

void deleteEnd() {

    if(head == NULL)
        return;

    if(head->next == NULL) {

        free(head);
        head = NULL;
        return;
    }

    struct Node* temp = head;

    while(temp->next->next != NULL) {
        temp = temp->next;
    }

    free(temp->next);
    temp->next = NULL;
}

5. Searching Operation

Searching means finding whether an element exists in the linked list.

Since linked lists do not support direct indexing, nodes are checked one by one.

Example

10 → 20 → 30 → 40 → NULL

Search key = 30

Result:

  • Element Found

Algorithm

SEARCH(head, key)

1. temp = head
2. While temp ≠ NULL
       If temp.data == key
            Return Found
       temp = temp.next
3. Return Not Found

C Program

void search(int key) {

    struct Node* temp = head;

    while(temp != NULL) {

        if(temp->data == key) {

            printf("Element Found");
            return;
        }

        temp = temp->next;
    }

    printf("Element Not Found");
}

6. Display Operation

Display operation prints all nodes of the linked list sequentially.

Example

15 → 25 → 35 → NULL

Display Output:

15 25 35

Algorithm

DISPLAY(head)

1. Start from head
2. Print each node
3. Move to next node
4. Stop at NULL

C Program

void display() {

    struct Node* temp = head;

    while(temp != NULL) {

        printf("%d -> ", temp->data);
        temp = temp->next;
    }

    printf("NULL");
}

Time Complexity of Singly Linked List Operations

OperationTime Complexity
TraversalO(n)
Insertion at BeginningO(1)
Insertion at EndO(n)
Deletion at BeginningO(1)
Deletion at EndO(n)
SearchingO(n)

Advantages of Singly Linked List

  • Dynamic size
  • Efficient insertion and deletion
  • Better memory utilization
  • Easy implementation

Disadvantages of Singly Linked List

  • Sequential access only
  • Extra memory required for pointers
  • Backward traversal not possible
  • Searching is slower than arrays

Applications of Singly Linked List

Singly linked lists are used in,

  • Music playlists
  • Browser history
  • Dynamic memory management
  • Stack implementation
  • Queue implementation

Conclusion

A singly linked list is one of the most fundamental and important data structures in computer science. It stores data dynamically using nodes connected through pointers. Because of its flexible structure, it supports efficient insertion and deletion operations. Understanding singly linked lists is important before learning advanced data structures such as doubly linked lists, circular linked lists, trees, and graphs.