Sandeep

Posted on Oct 4

Linked list ?

#programming #dsa #tutorial #beginners

What is a Linked List?

A linked list is a linear data structure where elements, called nodes, are connected using pointers. Unlike arrays, linked lists allow easy insertion and deletion of elements without shifting other elements, making them more flexible in certain scenarios.

Where to Use a Linked List vs an Array

Arrays are suitable when:

Random access by index is required frequently.
The size of the data structure is known in advance or changes infrequently.

Linked Lists are preferred when:

Insertions and deletions are the primary operations.
The order of elements must be maintained.
The size of the data is dynamic or unknown.

In general, if you need quick access to elements via indices, use an array; if you need efficient insertions/deletions, use a linked list.

Structure of a Linked List

A linked list is composed of nodes, where each node contains:

Data segment – stores the value or information.
Pointer (reference) segment – points to the next node in the sequence.

This self-referential structure allows nodes to form a chain, enabling dynamic memory allocation and efficient insertion/deletion operations.

Common Operations on Linked Lists

Some basic operations that can be performed on linked lists include:

Insertion – Add a new node at the beginning, end, or any given position.
Deletion – Remove a node by its value or position.
Traversal – Visit each node to access or print data.
Searching – Find a specific element in the list.
Reversing – Reverse the order of nodes in the list.

Types of Linked Lists

Singly Linked List
- Each node has a pointer to the next node only.
- The list starts with a head pointer and ends with null.
- Traversal is one-way, from the head to the last node.
Doubly Linked List
- Each node contains two pointers: one pointing to the next node and one pointing to the previous node.
- Traversal is possible in both directions.
- Updating nodes is easier compared to singly linked lists.
Circular Linked List
- The last node points back to the first node, forming a loop.
- Can be singly or doubly linked.
- Useful in scenarios where the list needs to wrap around or be accessed in a cyclic manner.

Example: Simple Singly Linked List in C

Below is a simple C program demonstrating how to create and traverse a singly linked list.

#include <stdio.h>
#include <stdlib.h>

// Define a node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to print the linked list
void printList(struct Node* n) {
    while (n != NULL) {
        printf("%d -> ", n->data);
        n = n->next;
    }
    printf("NULL\n");
}

int main() {
    // Allocate 3 nodes in the heap
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    // Assign data and connect nodes
    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = NULL;

    // Print the linked list
    printf("Linked List: ");
    printList(head);

    return 0;
}

Output :

Linked List: 10 -> 20 -> 30 -> NULL

Advantages and Disadvantages of Linked Lists

Advantages

Dynamic size – no need to know the number of elements in advance.
Efficient insertion and deletion (no shifting required).
Useful for implementing advanced data structures.

Disadvantages

No random access (you must traverse from the head).
Extra memory is needed for storing pointers.
Traversal and searching take more time compared to arrays.

Why Are Linked Lists Important?

Linked lists are widely used in scenarios where dynamic memory allocation and frequent insertion or deletion are required.

They form the foundation for many advanced data structures such as stacks, queues, hash tables, and graphs.

They are also useful in implementing memory management systems, file systems, and real-time applications where data keeps changing dynamically.

Applications of Linked Lists

Implementing stacks and queues
Managing memory blocks in operating systems
Representing polynomials and sparse matrices
Building adjacency lists for graph representation
Implementing undo/redo functionality in text editors

Conclusion

Linked lists are one of the most fundamental data structures in computer science.

They provide flexibility in handling data that changes frequently and form the basis for many complex structures and algorithms.

Understanding how linked lists work is a great step toward mastering data structures and algorithms.

DEV Community