HomeResourcesSoftware DevelopmentData Structure Tutorial for BeginnersLinked List in Data Structure

Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best and Easiest Way to Understand an Algorithm

Lesson - 21

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 22

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 23

A One-Stop Solution Guide to Understand Data Structure and Algorithm Complexity

Lesson - 24

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 25

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 26

What Is Selection Sort Algorithm In Data Structures?

Lesson - 27

Everything You Need to Know About Radix Sort Algorithm

Lesson - 28

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 29

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 30

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 31

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 32

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 33

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 34

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 35

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 36

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 37

Your One-Stop Solution for Graphs in Data Structures

Lesson - 38

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 39

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 40

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 41

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 42

The Holistic Look at Longest Common Subsequence Problem

Lesson - 43

The Best Article to Understand What Is Dynamic Programming

Lesson - 44

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 45

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 46

One Stop Solution to All the Dynamic Programming Problems

Lesson - 47

Understanding the Fundamentals of Binomial Distribution

Lesson - 48

Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

Lesson - 49

Understanding the Difference Between Array and Linked List

Lesson - 50

The Best Article Out There to Understand the B+ Tree in Data Structure

Lesson - 51

A Comprehensive Look at Queue in Data Structure

Lesson - 52

Your One-Stop Solution to Understand Coin Change Problem

Lesson - 53

The Best Way to Understand the Matrix Chain Multiplication Problem

Lesson - 54

Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

Lesson - 55

The Best Tutorial You'll Ever Need for Queue Implementation Using Linked List

Lesson - 56

All You Need to Know About How to Create a React JS Portfolio Project

Lesson - 57

The Best Guide to Learn How to Make a Wireframe: What is a Wireframe?

Lesson - 58

The Best DSA Projects for Your Resume

Lesson - 59

Top 5 Best Coding Books You Must Read

Lesson - 60

The Working and Implementation of Physical Layer in the OSI Model

Lesson - 61

How to Create an Instagram Clone Using React?

Lesson - 62

ReactJS Vs VueJS

Lesson - 63

Linked List in Data Structure

Lesson 3 of 63By Ravikiran A S

Last updated on Sep 26, 2024262846
All You Need to Know About a Linked List in a Data Structure

Table of Contents

View More

A linked list is the most sought-after data structure when it comes to handling dynamic data elements. A linked list consists of a data element known as a node. And each node consists of two fields: one field has data, and in the second field, the node has an address that keeps a reference to the next node.

What is a Linked List?

  • A linked list is a linear data structure that stores a collection of data elements dynamically.
  • Nodes represent those data elements, and links or pointers connect each node.
  • Each node consists of two fields, the information stored in a linked list and a pointer that stores the address of its next node.
  • The last node contains null in its second field because it will point to no node.
  • A linked list can grow and shrink its size, as per the requirement.
  • It does not waste memory space.

Your Data Analytics Career is Around The Corner!

Data Analyst Master’s ProgramExplore Program
Your Data Analytics Career is Around The Corner!

Representation of a Linked List

This representation of a linked list depicts that each node consists of two fields. The first field consists of data, and the second field consists of pointers that point to another node.

representation-of-linked-list

Here, the start pointer stores the address of the first node, and at the end, there is a null pointer that states the end of the Linked List. 

Key Differences Between Linked Lists and Arrays

Let’s explore the fundamental differences between linked lists and arrays:

  • What Are They?

An array is a data structure that holds a fixed number of elements of the same type in a continuous block of memory. You can think of it as a row of boxes where each box contains a value. In contrast, a linked list is made up of nodes, each containing data and a pointer to the next node. This forms a chain, allowing elements to be scattered throughout memory.

  • Size Matters

Arrays have a fixed size. You decide how many elements to store upfront, and that’s it. If you need more space later, you’ll have to create a new array and move the elements. Linked lists, on the other hand, can grow or shrink as needed. You can easily add or remove nodes without worrying about the total size.

  • Memory Allocation

Arrays use contiguous memory, meaning all elements are stored next to each other. This makes accessing elements fast. Linked lists use separate memory for each node, which can lead to some inefficiency because of the extra memory needed for pointers.

  • Memory Usage

Arrays are generally more memory-efficient since they don’t need extra pointers. Linked lists require more memory due to the pointers that link each node together.

  • Insertion and Deletion

When inserting or deleting elements, arrays can be slow, taking O(n) time, especially if you’re working with elements in the middle or at the beginning. This is because you may need to shift other elements. Linked lists allow for quick insertions at the beginning (O(1)), but inserting at the end can take O(n) time if you don’t have a direct pointer to the last node.

  • Searching for Elements

Searching in arrays can take O(n) time in the worst case. If the array is sorted, you can use binary search, which is faster at O(log n). For linked lists, you also typically spend O(n) time searching since you need to traverse each node until you find what you’re looking for.

  • Accessing Elements

Accessing elements is quick in arrays, with a time complexity of O(1). You can jump directly to any index. In linked lists, accessing an element requires O(n) time because you need to follow the chain of nodes from the start.

  • Deleting Elements

In arrays, deleting an element from the beginning or middle can take O(n) time since other elements need to be shifted. However, deleting from the end can be done in O(1). For linked lists, removing a node at the beginning is O(1), but it takes O(n) to remove from the middle or end, as you have to find the node first.

  • Best Use Cases

Arrays work best when you know how many elements you'll need and require fast access, like storing pixel values in images. Linked lists are great for situations where you frequently add or remove elements, such as managing a list of users in a web application.

Creation of Node and Declaration of Linked Lists

struct node

{

 int data;

 struct node * next;

};

struct node * n;

n=(struct node*)malloc(sizeof(struct node*));

It is a declaration of a node that consists of the first variable as data and the next as a pointer, which will keep the address of the next node.

Here you need to use the malloc function to allocate memory for the nodes dynamically.

Want to Become a Data Analyst? Learn From Experts!

Data Analyst Master’s ProgramExplore Program
Want to Become a Data Analyst? Learn From Experts!

Essential Operation on Linked Lists

  • Traversing: To traverse all nodes one by one.
  • Insertion: To insert new nodes at specific positions.
  • Deletion: To delete nodes from specific positions.
  • Searching: To search for an element from the linked list.

Traversal 

In this operation, you will display all the nodes in the linked list.

When the temp is null, it means you traversed all the nodes, and you reach the end of the linked list and get out from the while loop.

struct node * temp = start;

printf(“\n list empty are-”);

while (temp!= NULL)

{

 printf(‘%d “, temp -> data)

 temp=temp -> next;

}

 Insertion

You can add a node at the beginning, middle, and end.

Insert at the Beginning

  • Create a memory for a new node.
  • Store data in a new node.
  • Change next to the new node to point to start.
  • Change starts to tell the recently created node.

struct node *NewNode;

NewNode=malloc(sizeof(struct node));

NewNode -> data = 40;

NewNode -> next= start;

start= NewNode;

Insert at the End

  • Insert a new node and store data in it.
  • Traverse the last node of a linked list
  • Change the next pointer of the last node to the newly created node.

struct node *NewNode;

NewNode=malloc(sizeof(struct node));

NewNode-> data = 40;

NewNode->next = NULL;

struct node *temp = start;

while( temp->next ! = NULL){

temp=temp -> next;

    }

 temp -> next = NewNode;

Insert at the Middle

  • Allocate memory and store data in the new node.
  • Traverse the node, which is just before the new node.
  • Change the next pointer to add a new node in between.

struct node *NewNode;

NewNode= malloc(sizeof(struct node));

NewNode -> data = 40;

struct node - > temp = start;

for(int i=2; i<position; i++){

if (temp -> next!= NULL)

temp = temp -> next;

}}

NewNode -> next = temp -> next;

temp -> next = NewNode;

Deletion

You can also do deletion in the linked list in three ways either from the end, beginning, or from a specific position.

Delete from the Beginning

  • The point starts at the second node.

start = start -> next;

Delete from the End

  • Traverse the second last element in the linked list.
  • Change its next pointer to null.

struct node * temp = start;

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

temp=temp -> next;

}

temp -> next = NULL;

Delete from the Middle

  • Traverse the element before the element to be deleted.
  • Change the next pointer to exclude the node from the linked list.

for (int i = 2; i, position; i++){

if (temp -> next ! = NULL)

temp = temp -> next;

}

}

temp-> next = temp -> next -> next;

Searching 

The search operation is done to find a particular element in the linked list. If the element is found in any location, then it returns. Else, it will return null.

Operations on Linked-Lists

Code to Insert at the Beginning of the Linked List

void insertatbeg()  

{  

    struct node *NewNode;  

    int item;  

    NewNode = (struct node *) malloc(sizeof(struct node *));  

    if(NewNode == NULL)  

    {  

        printf("\nOVERFLOW");  

    }  

    else  

    {  

        printf("\nEnter value\n");    

        scanf("%d",&item);    

        NewNode->data = item;  

        NewNode->next = start;  

        start = NewNode;  

        printf("\nNode inserted");  

    }    

}  

Code to Insert at the End of the Linked List

void insertatend()  

{  

    struct node *NewNode,*temp;  

    int item;     

    NewNode = (struct node*)malloc(sizeof(struct node));      

    if(NewNode == NULL)  

    {  

        printf("\nOVERFLOW");     

    }  

    else  

    {  

        printf("\nEnter value?\n");  

        scanf("%d",&item);  

        NewNode->data = item;  

        if(start == NULL)  

        {  

            NewNode -> next = NULL;  

            start = NewNode;  

            printf("\nNode inserted");  

        }  

        else  

        {  

            temp = start;  

            while (temp -> next != NULL)  

            {  

                temp = temp -> next;  

            }  

            temp->next = NewNode;  

            NewNode->next = NULL;  

            printf("\nNode inserted");        

        }  

    }  

}  

Code to Insert at the Middle of the Linked List

void insertmiddle()  

{  

    int i,position,item;   

    struct node *NewNode, *temp;  

    NewNode = (struct node *) malloc (sizeof(struct node));  

    if(NewNode == NULL)  

    {  

        printf("\nOVERFLOW");  

    }  

    else  

    {  

        printf("\nEnter element value");  

        scanf("%d",&item);  

        NewNode-> data = item;  

        printf("\n Enter the location after which you want to insert an element ");  

        scanf("\n%d",&position);  

        temp=start;  

        for(i=0;i<position;i++)  

        {  

            temp = temp->next;  

            if(temp == NULL)  

            {  

                printf("\can't insert\n");  

                return;  

            }          

        }  

        NewNode ->next = temp ->next;   

        temp ->next = NewNode;   

        printf("\nNode inserted");  

    }  

}  

Code to Delete From the Beginning of the Linked List

void deleteatbeg()  

{  

    struct node *NewNode;  

    if(start == NULL)  

    {  

        printf("\nList is empty\n");  

    }  

    else   

    {  

        NewNode = start;  

        start = NewNode->next;  

        free(NewNode);  

        printf("\nNode deleted from the beginning\n");  

    }  

}  

Code to Delete From the End of the Linked List

void deleteatend()  

{  

    struct node *NewNode,*NewNode1;  

    if(start == NULL)  

    {  

        printf("\list is empty");  

    }  

    else if(start -> next == NULL)  

    {  

        start = NULL;  

        free(NewNode);  

        printf("\n node of the list deleted\n");  

    }  

           else  

    {  

        NewNode = start;   

        while(NewNode->next != NULL)  

        {  

            NewNode1 = NewNode;  

            NewNode = NewNode ->next;  

        }  

        NewNode1->next = NULL;  

        free(NewNode);  

        printf("\nDeleted Node from the last\n");  

    }     

} 

Code to Delete From the Middle of the Linked List

void deletemiddle()  

{  

    struct node *NewNode,*NewNode1;  

    int position,i;    

    printf("\n what location of the node \n");  

    scanf("%d",&position);  

    NewNode=start;  

    for(i=0;i<position;i++)  

    {  

        NewNode1 = NewNode;       

        NewNode = NewNode->next;              

        if(NewNode == NULL)  

        {  

            printf("\nCan't delete");  

            return;  

        }  

    }  

    NewNode1 ->next = NewNode ->next;  

    free(NewNode);  

    printf("\nDeleted node %d ",position+1);  

}  

Code to Search for an Element From the Linked List.

void search()  

{  

    struct node *NewNode;  

    int item,i=0,flag;  

    NewNode = start;   

    if(NewNode == NULL)  

    {  

        printf("\nEmpty List\n");  

    }  

    else  

    {   

        printf("\nEnter an item which you want to search\n");   

        scanf("%d",&item);  

        while (NewNode!=NULL)  

        {  

            if(NewNode->data == item)  

            {  

                printf("item found at position%d ",i+1);  

                flag=0;  

            }   

            else  

            {  

                flag=1;  

            }  

            i++;  

            NewNode = NewNode -> next;  

        }  

        if(flag==1)  

        {  

            printf("Item not found\n");  

        }  

    }              

}  

Code to Show Data Elements of the Linked-List

void show()  

{  

    struct node *NewNode;  

    NewNode = start;   

    if(NewNode == NULL)  

    {  

        printf("Nothing to print");  

    }  

    else  

    {  

        printf("\nprinting values\n");   

        while (NewNode!=NULL)  

        {  

            printf("\n%d",NewNode->data);  

            NewNode = NewNode -> next; 

        }  

    }  

} 

Jumpstart Your Career in Data Analytics Today!

Post Graduate Program In Data AnalyticsExplore Now
Jumpstart Your Career in Data Analytics Today!

Application of a Linked List

  • A linked list is used to implement stacks and queues.
  • A linked list also helps to implement an adjacency matrix graph.
  • It is used for the dynamic memory location.
  • The linked list makes it easy to deal with the addition and multiplication of polynomial operations.
  • Implementing a hash table, each bucket of the hash table itself behaves as a linked list.
  • It is used in a functionality known as undo in Photoshop and Word.

With that, you have reached the end of this tutorial on Linked Lists.

Linked List vs Other Data Structures

Linked lists stand out when compared to other data structures like stacks and queues. Their dynamic memory allocation gives them the flexibility to adapt to the data needs that arise, hence, they are the most appropriate choice for such situations where one is not sure of the amount of data that will be processed. Nevertheless, one of the downsides is that retrieving particular items can be more time-consuming. You have to start from the beginning of the list to see if you can find the required information.

Memory Management in Linked Lists

Here is how memory is managed in the linked lists:

  • Memory Allocation

Linked lists use dynamic memory allocation. Each node gets its own memory space when needed, which means you can add or remove nodes without any hassle. This is particularly useful when you don’t know how much data you’ll have in advance.

  • Memory Storage

In linked lists, nodes are stored wherever there’s free memory available. Each node contains a pointer to the next one, creating a flexible chain. This setup allows linked lists to make good use of memory, as they don’t need to be stored in a single, continuous block.

  • Memory Usage

Linked lists are great for situations where the amount of data can change. For instance, if you need to store a collection that might grow to a million integers, a linked list can expand as you add more nodes. You only allocate memory for what you need at the moment, which keeps things efficient.

Become an Expert in Data Analytics

With Our Unique Data Analyst Master’s ProgramExplore Program
Become an Expert in Data Analytics

Time and Space Complexity of Linked Lists

Let's break it down for several key actions:

  • Traversal

When you traverse a linked list, you visit each node. This takes O(n) time, where n is the number of nodes in the list. However, you don’t need extra space for this operation, so the space complexity is O(1).

  • Insertion at the Beginning

Inserting a node at the start is quick and straightforward. It takes O(1) time because you only need to change the head reference. The space complexity is also O(1) since you aren’t using additional space.

  • Insertion at the End

Adding a node at the end takes more time, specifically O(n), because you may need to go through the entire list to find the last node. Still, the space complexity remains O(1) as you only need space for the new node.

  • Deletion at the Beginning

Removing the first node is efficient, requiring O(1) time. You just update the head reference, and like the previous operations, the space complexity is O(1).

  • Deletion at the End

Deleting the last node takes O(n) time, similar to inserting at the end, since you need to traverse the list. The space complexity stays O(1) since no extra space is needed beyond the operation.

Want to Become a Data Analyst? Learn From Experts!

Data Analyst Master’s ProgramExplore Program
Want to Become a Data Analyst? Learn From Experts!

Conclusion

If you are looking to build a career in data analytics, do explore Simplilearn’s Data Analytics Certification Program in partnership with Purdue University & in collaboration with IBM. Featuring ask-me-anything sessions from IBM, a masterclass from Purdue, and many great benefits, this program will give you the work-ready data analytics training you need to succeed today. 

FAQs

1. What are the common mistakes when using linked lists?

When working with linked lists, people often forget to release memory, leading to memory leaks. Segmentation faults can happen if you try to access parts of memory that aren’t valid. Mismanaging pointers can cause logic errors, and skipping thorough testing may leave bugs lurking. These pitfalls can make your linked list behave unpredictably.

2. When should I use a circular linked list?

Circular linked lists are great for situations like managing playlists or scheduling tasks. They let you loop through your items endlessly, which means you can keep cycling through without hitting a dead end. This is super handy when you want to keep things flowing smoothly and efficiently without interruptions.

3. How do I detect and remove a loop in a linked list?

To spot and fix a loop in a linked list, you can use a fun trick called Floyd's cycle-finding algorithm, or the tortoise and hare method. You use two pointers: one moves slowly and the other faster. If they meet, there’s a loop! Then, you reset one pointer to find where the loop starts, making it easy to clean up.

About the Author

Ravikiran A SRavikiran A S

Ravikiran A S works with Simplilearn as a Research Analyst. He an enthusiastic geek always in the hunt to learn the latest technologies. He is proficient with Java Programming Language, Big Data, and powerful Big Data Frameworks like Apache Hadoop and Apache Spark.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.