C program To Reverse Linked List

C Program To Reverse Linked List With Example

Today’s topic of discussion will be C Program To Reverse Linked List. We will use C Programming Language to achieve our goal. For the simplicity of our tutorial C programming language will be more suitable for us to solve this problem. Choosing C programming Language before Python programming is just a preference nothing more than that. This tutorial may help you in understanding the Linked List Data Structure in a more simple way. But before jumping into the topic let us know more about the Linked List data structure.

What is a Linked List Data Structure?

A linked List is a linear data structure. This means the elements are not stored at contiguous or say at the same group of memory locations. A linked list can store the data dynamically. When it comes to managing dynamic data items, a linked list is by far the most suitable data structure. A node is a type of data element in a linked list. Additionally, each node has two fields: one field contains data, and the other field contains an address that maintains a link to the node after it. The elements in the linked list are together with the help of pointers as shown below the diagram:

linked list
linked list
  • Links or pointers connect each of the nodes, which represent the data elements.
  • A linked list of data and a pointer that contains the address of the node after it makes up each node’s two fields.
  • Since the final node will point to nothing, its second field is null.
  • A linked list’s size can change depending on the situation.

Types of Linked Lists | Alos C Program To Reverse Linked List

C program to Reverse Linked List. We can find three types of Linked List:

  1. Singly Linked List
  2. Doubly Linked List
  3. Circular Linked List
Singly Linked List

The most typical kind of linked list is a singly linked list. Each node has information and an address field with a reference to the node after it. For our topic C program To Reverse Linked List, we will use the above structure.

Doubly Linked List

There are two pointer storage blocks in the doubly linked list. The first pointer block in each node stores the address of the previous node. Hence, in the doubly linked inventory, there are three fields that are the previous pointers, that contain a reference to the previous node. Then there is the data, and last you have the next pointer, which points to the next node. Thus, you can go in both directions (backward and forward).

C Program To Reverse Linked List | How To Achieve This?

when a linked list is reversed, the head pointer points to the final node, often known as the terminal node, while the current. If a linked list is reversed the head pointer points to the final node, often known as the terminal node.

Steps To C Program To Reverse Linked List

1: Create three nodes, one of which should be the head node and the other two should be NULL.

2: Execute a loop that will traverse the linked list once up until the point where the following node does not become NULL.

3: The first NULL node is now as the head node’s neighbor inside the loop.

4: The second NULL node is now the head node’s next node.

5: The node that carries the reference to the head node from step 1 is now at the second NULL node from step 4 again.

6: Lastly, the node carrying the reference to the head node from Step 1 is made to hold the reference to the next node in the linked list; as a result, the pointer now points to the node that was before it in the linked list.

#include<bits/stdc++.h>

using namespace std;

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

/* Function to push nodes in a linked list. */
void push(struct node **head_ref, int data) {
    struct node *node;
    node = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->next = (*head_ref);
    (*head_ref) = node;
}
 
/* Function to reverse the nodes in a linked list. */
void reverse(struct node **head_ref) {
    struct node *temp = NULL;
    struct node *prev = NULL;
    struct node *current = (*head_ref);
    while(current != NULL) {
        temp = current->next;
        current->next = prev;
        prev = current;
        current = temp;
    }
    (*head_ref) = prev;
}

/* Function to print the nodes in a linked list. */
void printnodes(struct node *head) {
    while(head != NULL) {
        cout<<head->data<<" ";
        head = head->next;
    }
}

/* Driver function to check the above algorithm. */
int main() {
    struct node *head = NULL;
    push(&head, 10);
    push(&head, 11);
    push(&head, 18);
    push(&head, 60);
    push(&head, 94);
    push(&head, 100);
    cout << "List before reversing" << endl;
    printnodes(head);
    reverse(&head);
    cout << endl;
    cout << "List after reversing"<<endl;
    printnodes(head);
    return 0;
}
List before reversing

100 94 60 18 11 10

List after reversing

10 11 18 60 94 100

time complexity is: O(n)

Explanation of the above C program to reverse linked list

Now let us explore more about what is happening here.

1 Make the first node the one that is currently holding a reference to the head node.

2 We will now iterate through the entire linked list until the next head node does not become NULL. To accomplish this, we’ll set the head node’s subsequent node to temp.

3 As seen in the preceding diagram, the temp node now stores the reference to the head node’s subsequent node. Then, as shown by the arrow heading to the null node on the left of the node with data, we will link the subsequent node of the current (in this example, NULL) to the preceding.

4 Then, after moving the current node one node forward and setting the prev pointer to the newly formed NULL node, which is also the previous of the current node, the loop will restart with the temp pointer being moved to the next of the current pointer. will also move the current to the next and the previous to the next, changing the arrow’s direction, and making the next of the current point to the prior.

Conclusion

So that is it for today’s C program to Reverse Linked List example. It’s just a mere example only. You can use the Linked List Data Structure for creating many fun mini-projects. Learning them helps you in getting concepts of data structure more concisely. Moreover, you can enhance your learning experience while you give job interviews.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.