Single Linked List

Sumit included in DSA

25-12-2022 2066 words 10 minutes

/posts/DSA/single-linked-list/LLdraw.png

Contents

Navigation system works on the concept of linked list.

Note

Use the table of contents to navigate to the portion that you are interested in.

1. Introduction:

Single linked list is a linear data structure. It is slightly different from array. It made by the nodes, each nodes consist a data and the address of the next node and each node are linked using pointers. Here data are not stored in the contiguous memory location, nodes are present anywhere in the memory space but every nodes are linked with eachother that’s why we call this linked list. Main benefit of linked list is that we can insert or delete data from any position in the list.

2. Creation of Node

To create a new node in C++, you will need to define a structure or class that represents a node, and then create an instance of that structure or class. Here we will use structure to create or define a node.

Here is an example of a node structure in C++ or C:

1
2
3
4
5
6
7


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

struct Node *head = NULL;

3. Insertion

An insertion operation in a single linked list involves adding a new node to the list. For this first you have to create a newnode and then insert this node where you want. There are several ways to insert a node in the list:

At the beginning of the list
At the end of the list
At a specific position of the list

3.1 Insertion at Begining

To insert a new node at the beginning of the list, you need to create a newnode and set it’s next pointer to point to the current head of the list. Then, you can set the head of the list to the newnode. You also have to check whether the first node is present or not in the list or we can say list is empty or not.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// insertion at begining
void insertAtBeg(int value)
{
    struct Node *newnode;
    newnode = (struct Node *)malloc(sizeof(struct Node));
    newnode->data = value;
    if (head == NULL)
    {
        newnode->next = NULL;
        head = newnode;
    }
    else
    {
        newnode->next = head;
        head = newnode;
    }
    printf("%d is inserted at beginning.\n", value);
}

3.2 Insertion at Last

To insert a new node at the end of the list, you need to traverse the list until you reach the last node. Then, you can set the next pointer of the last node to point to the newnode. If the list is empty then set the head to the newnode.

temp is just a temporary node just like count variable, after the operation it does’nt have any importance.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


// insertation at end
void insertATend(int value)
{
    struct Node *newnode;
    newnode = (struct Node *)malloc(sizeof(struct Node));
    newnode->data = value;
    if (head == NULL)
    {
        newnode->next = NULL;
        head = newnode;
    }
    else
    {
        struct Node *temp;
        temp = head;
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = newnode;
        newnode->next = NULL;
    }
    printf("%d is inserted at the end.\n", value);
}

Traversal Technique

Traversal is the process or technique of visiting and processing each node in a data structure, such as a linked list, tree, or graph. There are several way to traverse. Here we use the simple traversal technique in which we form a temp variable or node and traverse the each node one by one just pointing to the next pointer to the temp. temp=temp->next;

3.3 Insertion at Any Position

To insert a new node at a desired position in the list, first you need to make a temporary node say temp initialise with head then traverse the list until you reach the node before the position where you want to insert the newnode. Then, you can set the next pointer of the newnode to point to the node at the desired position, and set the next pointer of the node before the position to point to the newnode.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// insertion at any position
void insertAtPos(int pos, int value)
{
    struct Node *newnode;
    newnode = (struct Node *)malloc(sizeof(struct Node));
    newnode->data = value;

    struct Node *temp = NULL;
    int i = 1;
    temp = head;
    while (i < pos - 1)
    {
        temp = temp->next;
        i++;
    }
    newnode->next = temp->next;
    temp->next = newnode;
    printf("%d is inserted at the %dth position.\n", value, pos);
}

Seg Fault

Here you get a segmentation fault if you enter that position which are not exist in the list. For this first you have to check whether the position is present or not in the list then insert the node at that position.

4. Deletion

A deletion operation in a single linked list involves removing a node from the list and free the space. First make a temp node, traverse to that node and do the operation. There are several ways to delete a node from the list:

Deleting the head node
Deleting the last node
Deleting a node from the specific position of the list

4.1 Deletion from Begining

To delete the head node or first node, first you have to make a temp node initialise with head then set the head of the list to the next node in the list. Now free the temp.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// deletion at begining
void deleteatBeg()
{
    if (head == NULL)
    {
        printf("The list is empty.\n");
    }
    else
    {
        struct Node *temp;
        temp = head;
        head = head->next;
        printf("%d is deleted from the begining\n", temp->data);
        free(temp);
    }
}

4.2 Deletion from End

To delete the last node, make a temp node traverse the list until you reach the second-to-last node. Set the temp to the last node of the list. Then, you can set the next pointer of the second-to-last node to null. Now free the temp.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


// deletion at end
void deleteatEnd()
{
    if (head == NULL)
    {
        printf("The list is empty.\n");
    }
    else
    {
        struct Node *temp, *prev;
        prev = temp = head;
        while (temp->next != NULL)
        {
            prev = temp;
            temp = temp->next;
        }
        prev->next = NULL;
        printf("%d is deleted from the end\n", temp->data);
        free(temp);
    }
}

4.3 Deletion from Any Position

To delete a node in the middle of the list, you need to traverse the list until you reach the node before the one you want to delete. Set the temp to the node to be deleted in the list. Then, you can set the next pointer of the previous node to point to the node after the one you want to delete. Free the temp.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// deletion at any position
void deleteatPos(int pos)
{
    struct Node *nextnode, *temp;
    int i = 1;
    nextnode = temp = head;
    while (i < pos)
    {
        temp = nextnode;
        nextnode = nextnode->next;
        i++;
    }
    temp->next = nextnode->next;
    printf("%d is deleted from the %dth position.\n", nextnode->data, pos);
    free(nextnode);
}

Seg Fault

Here also you get a segmentation fault if you delete that position which are not exist in the list. For this first you have to check whether the position is present or not in the list then delete the node from that position.

5. Sorting

There are several way to sort the list.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// sorting of linked list
void sortlist()
{
    struct Node *ptr, *cpt;
    ptr = head;
    int temp;
    while (ptr->next != NULL)
    {
        cpt = ptr->next;
        while (cpt != NULL)
        {
            if (ptr->data > cpt->data)
            {
                temp = ptr->data;
                ptr->data = cpt->data;
                cpt->data = temp;
            }
            cpt = cpt->next;
        }
        ptr = ptr->next;
    }
    printf("The list is sorted successfully.\n");
}

6. Reversing

To reverse the linked list, You have to iterate the linked list and for each node, changing the next pointer to point to the previous node instead of the next node as it traverses the linked list. This effectively reverses the order of the nodes in the linked list. The function returns the reversed linked list by returning the last node in the original linked list as the new head.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// to reverse the list
void reverse()
{
    struct Node *current = head;
    struct Node *prev = NULL, *next = NULL;

    while (current != NULL)
    {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    head = prev;
    printf("The list is reversed successfully.\n");
}

7. Print Function

To print the list you have to travarse the list and print each node one by one. For this make a temp node initialise with head, travarse and print.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// printing of linked list
void display()
{
    printf("The list is: ");
    struct Node *temp;
    temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n\n");
}

8. To Find Length

To find the length of the list, first make a temp node initialise with head than travarse the list and increment the count by 1 on every travarsal until you reach to the last node. At last print the count value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// length of the linked
int getlength()
{
    int count = 0;
    struct Node *temp = head;
    while (temp != NULL)
    {
        count++;
        temp = temp->next;
    }
    printf("Total nodes present in the list is: %d\n", count);
}

9. Main Function

In the main function. we check all the function whether they are working or not, call all the functions one by one.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


// main function
int main()
{

    insertAtBeg(34);
    insertAtBeg(45);
    insertAtBeg(72);
    insertAtBeg(50);
    insertAtBeg(89);
    insertAtBeg(99);
    insertATend(23);
    insertATend(55);
    insertATend(13);
    insertATend(41);
    insertAtPos(6, 8992);
    display();
    deleteatBeg();
    deleteatEnd();
    deleteatPos(3);
    display();
    sortlist();
    display();
    insertATend(58);
    display();
    reverse();
    display();
    insertAtBeg(99);
    insertATend(23);
    display();
    getlength();
    return 0;
}

Note

It will be a better practice if you take the input from the user in the output terminal. In this case the main function will be:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


// main function
int main()
{
    int choice,value,pos;

    printf("1) Insert at begining\n");
    printf("2) insert at last\n");
    printf("3) Insert at any position\n");
    printf("4) Delete from the begining\n");
    printf("5) Delete from the end\n");
    printf("6) Delete from any position\n");
    printf("7) Sort the list\n");
    printf("8) Reverse the list\n");
    printf("9) Fint the length of the list\n");
    printf("10) Display the list\n");
    printf("11) Exit\n")

    do
    {
        printf("Enter Choice: ");
        scanf("%d",&choice);
        switch (choice)
        {
        case 1:
            printf("Enter value to be inserted: ");
            scanf("%d",&value);
            insertAtBeg(value);
            break;
        case 2:
            printf("Enter value to be inserted: ");
            scanf("%d",&value);
            insertATend(value);
            break;
        case 3:
            printf("Enter the position and the value to be inserted respectively: ");
            scanf("%d%d",&pos,&value);
            insertAtPos(pos,value);
            break;
        case 4:
            deleteatBeg();
            break;
        case 5:
            deleteatEnd();
            break;
        case 6:
            printf("Enter the position of the node to be deleted: ");
            scanf("%d",&pos);
            deleteatPos(pos);
            break;
        case 7:
            sortlist();
            break;
        case 8:
            reverse();
            break;
        case 9:
            getlength();
            break;
        case 10:
            display();
            break;
        case 11:
            printf("Exit");
            break;
        default:
            break;
        }
    } while (choice!=11)
    return 0;
}

Complete Code of Single Linked List: Code

Fun Dose

Problems

Linked List 1 (CodeChef) Linked List 2 (CodeChef) Reversed Linked List (HackerEarth) Remove Friends (HackerEarth)