A linked list in C/C++ is basically a linear data structure based on the concept of dynamic memory allocation. It is implemented with the help of pointers. The linked list in C and C++ tutorial is specially designed for the beginners, who are not aware of the importance of linked lists. By the end of this tutorial, you can easily implement the linked list.
Why Wait? Explore Now!
1. What is a Linked List in C/C++?
As the name itself suggests, the linked list is a linear collection of similar data types in C. A linked list is nothing but a linear data structure with elements pointing to the next elements in a sequence, formally referred to as nodes. Just like arrays support the feature of static allocation of memory, linked list support the feature of dynamic memory allocation.
Key takeaway: Linked lists do not store their data elements contiguously, unlike arrays.
We saw that every linked list is associated with a node. Every node in a linked list is divided into two parts:
- The first part contains the information of the data element.
- The second part contains the memory address of the next node in the form of a pointer, called the link.
This is how a node looks like:
Here is a diagrammatic representation of how a linked list looks like:
Technology is evolving rapidly!
Stay updated with DataFlair on WhatsApp!!
From the above diagrams, it is evident that the first node is called the head.
Before we start the example, you must know about Arrays in C/C++
2. Real Life Example of Linked List
Let us understand the meaning of a linked list through a simple scenario:
A student coordinator is given the responsibility to manage 20 students taken to a hill station on a school trip. Each student has his own allocated room. Their rooms are on the same floor adjacent to each other.
Now, the student coordinator is supposed to distribute the tour plan to each student. The only thing the student coordinator needs to remember is the floor and room number of the first student. The room numbers of the next 19 students can easily be found out as the rooms are adjacent to each other.
Now, the next day, due to some disparency, the hotel manager has to shuffle the rooms of the 20 students. This time they have been given random rooms that are not sequentially arranged. This time the student coordinator is supposed to distribute carnival tickets to each student but has no idea how to find all the students as they are randomly scattered in different rooms.
The student coordinator finds a solution to this problem. He finds out the room number of the first student and asks him to remember the room number of the next student, who then asks to remember the room number of the student next to him. This process goes on until each student knows the room number of the student next to him except the last student.
Employing this method helps the student coordinator to solve this problem.
In the above-stated situation, the first case is clearly analogous to that of arrays, where there is a contiguous arrangement of students. Here, the data item is the student and their memory addresses are their room numbers. By finding out the memory address of one data element, the rest of the data elements can easily be accessed.
In contrast to the first case, the second case is analogous to a linked list. Here, the first data element stores the address of its next data element to access it.
Enhance Your Fundamental Skills with Operators in C and C++
Here is a diagrammatic representation of how the above-stated situations look like:
3. What is the Requirement of Implementing a Linked List in C/C++?
We already know how to work with arrays in C/C++, which is also a linear data structure. Now, the question arises: What is the requirement of learning how to implement a linked list in C and C++ when the same purpose is served?
Here are some of the reasons why:
3.1 DMA
DMA stands for Dynamic Memory Allocation. The linked list supports this concept which proves to be quite helpful when the number of elements and their sizes are not predetermined. The memory can be allocated during processing as and when required.
3.2 Easy modifications
Since the linked list supports the concept of dynamic memory allocation and data modifications such as insertion and deletion prove to quite easy to implement.
4. C/C++ Linked List Implementation
We can implement a linked list with the help of structures in C.
In other programming languages, like Java, classes are generally used to represent linked lists as these languages support the feature of object-oriented programming.
4.1 Declaration
Before we learn how to implement a linked list in C/C++, let us see how it to declare it. Its declaration is as follows:
struct node
{
int data_element;
struct node *next;
};
4.2 Creating a node
This is how we create a linked list in C/C++ consisting of two data elements:
struct node *first = NULL; struct node *second = NULL; /* Dynamic memory allocation */ first = (struct node*)malloc(sizeof(struct node)); second = (struct node*)malloc(sizeof(struct node)); first->data_element = 10; // Assigning data to the first node first->next = second; // Linking the first node with the second node second->data_element = 20; // Assigning data to the second node second->next = NULL; // Since third is the last node, it does not point to any other data element. // NULL denotes the termination of the linked list
Before we move ahead, you should know how functions in C work?
4.3 Displaying
We have created the following function to display the linked list in C:
void display(struct node *n) // Function to display the linked list
{
while (n != NULL)
{
printf("%d\n", n->data_element);
n = n->next;
}
}
We have created the following function to display the linked list in C++:
void display(struct node *n) // Function to display the linked list
{
while (n != NULL)
{
cout<< n->data_element << endl;
n = n->next;
}
}
5. Example of Linked List in C
Here is a program in C that illustrates the use of a linked list:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data_element;
struct node *next;
};
void display(struct node *n) // Function to display the linked list
{
while (n != NULL)
{
printf("%d\n", n->data_element);
n = n->next;
}
}
int main()
{
printf("Welcome to DatafLair tutorials!\n\n");
/* Linked list with 3 pointers: first, second, and third */
struct node *first = NULL;
struct node *second = NULL;
struct node *third = NULL;
/* Dynamic memory allocation */
first = (struct node*)malloc(sizeof(struct node));
second = (struct node*)malloc(sizeof(struct node));
third = (struct node*)malloc(sizeof(struct node));
first->data_element = 10; // Assigning data to the first node
first->next = second; // Linking the first node with the second node
second->data_element = 20; // Assigning data to the second node
second->next = third; // Linking the second node with the third node
third->data_element = 30; // Assigning data to the third node
third->next = NULL; // Since third is the last node, it does not point to any other data element.
// NULL denotes the termination of the linked list
display(first);
return 0;
}
Code-
Output-
6. Example of Linked List in C++
Here is a program in C++ that illustrates the use of linked lists:
#include <iostream>
using namespace std;
struct node
{
int data_element;
struct node *next;
};
void display(struct node *n) // Function to display the linked list
{
while (n != NULL)
{
cout<< n->data_element <<endl;
n = n->next;
}
}
int main()
{
cout<<"Welcome to DatafLair tutorials!" << endl;
/* Linked list with 3 pointers: first, second, and third */
struct node *first = NULL;
struct node *second = NULL;
struct node *third = NULL;
/* Dynamic memory allocation */
first = (struct node*)malloc(sizeof(struct node));
second = (struct node*)malloc(sizeof(struct node));
third = (struct node*)malloc(sizeof(struct node));
first->data_element = 10; // Assigning data to the first node
first->next = second; // Linking the first node with the second node
second->data_element = 20; // Assigning data to the second node
second->next = third; // Linking the second node with the third node
third->data_element = 30; // Assigning data to the third node
third->next = NULL; // Since third is the last node, it does not point to any other data element.
// NULL denotes the termination of the linked list
display(first);
return 0;
}
Code-
Output-
7. Types of Linked List in C/C++
There are basically three types of linked lists in C/C++, namely:
- Singly linked list- In this discussion, we will mainly focus on singly-linked lists. A singly linked list has only one reference, that is, ‘next’ that points to the memory address of the next element in the linked list.
- Doubly linked list- Just as a singly linked list has one reference, that is, ‘next’ that points to the memory location of the next element, a doubly linked list has two references, called ‘next’ and ‘previous’ which refers to the next node and previous node respectively.
- Circular linked list- A circular linked list is different from singly and doubly linked lists with respect to the memory occupied by the pointer in the last node. In a circular linked list, the last node does not contain the NULL pointer. It rather contains the memory address of the first node and hence called a circular linked list.
8. Limitations of Linked List
With positive aspects, comes negative ones as well. Here are some of the drawbacks of C/C++ linked lists:
8.1 No random access to elements
As the name “linked list” itself suggests, every data item in the list is linked to its next data item. Therefore, it is not possible to randomly access any element inside the linked list. Only the sequential access of elements is permitted in a linked list.
Arrays support the easy implementation of binary search to find an element but it is not the case with a linked list. Binary search in a linked list is quite complicated.
It’s time to uncover the concept of Multi-dimensional array in C/C++
8.2 Use of pointers
The implementation of pointers is considered to be relatively difficult, which most programmers struggle with, as it proves to be quite dangerous if left uninitialized. Moreover, pointers occupy extra space in computer memory.
9. Quiz on Linked List in C/C++
0 of 15 Questions completed Questions: You have already completed the quiz before. Hence you can not start it again.
Quiz is loading… You must sign in or sign up to start the quiz. You must first complete the following:
0 of 15 Questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 point(s), (0)
Earned Point(s): 0 of 0, (0) #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printL(Node *node) { while (node != NULL) { cout<<” “<<node->data; node = node->next; } } int main() { Node* head = NULL; addl(&head, 3); addl(&head, 9); printL(head); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addel(Node* prev_node, int new_data) { if (prev_node == NULL) return; Node* new_node = new Node(); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void printL(Node *node) { while (node != NULL) { cout<<” “<<node->data; node = node->next; } } int main() { Node* head = NULL; addl(&head, 3); addl(&head, 6); addel(head->next, 5); addel(head->next, 2); printL(head); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addel(Node* prev_node, int new_data) { if (prev_node == NULL) return; Node* new_node = new Node(); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void addend(Node** head_ref, int new_data) { Node* new_node = new Node(); Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } void printL(Node *node) { while (node != NULL) { cout<<” “<<node->data; node = node->next; } } int main() { Node* head = NULL; addl(&head, 3); addl(&head, 6); addel(head->next, 5); addend(&head, 10); printL(head); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void Delete(Node** head_ref, int key) { Node* temp = *head_ref; Node* prev = NULL; if (temp == NULL) return; if (temp != NULL && temp->data == key) { *head_ref = temp->next; delete temp; return; } else { while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } prev->next = temp->next; delete temp; } } void printL(Node *node) { while (node != NULL) { cout<<” “<<node->data; node = node->next; } } int main() { Node* head = NULL; addl(&head, 3); addl(&head, 6); Delete(&head, 3); addl(&head, 10); printL(head); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void search(Node* head, int key) { Node* temp = head; while (temp != NULL) { if (temp->data == key) { cout<<“found”; return;} temp = temp->next; } cout<<“not found”; return; } int main() { Node* head = NULL; addl(&head, 3); addl(&head, 6); search(head, 13); addl(&head, 10); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void length(Node* head) { int count=0; Node* temp = head; while (temp != NULL) { count++; temp = temp->next; } cout<<count; return; } int main() { Node* head = NULL; addl(&head, 3); addl(&head, 6); length(head); addl(&head, 10); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addel(Node* prev_node, int new_data) { if (prev_node == NULL) return; Node* new_node = new Node(); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void addend(Node** head_ref, int new_data) { Node* new_node = new Node(); Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } void printL(Node *node) { while (node != NULL) { cout<<” “<<node->data; node = node->next; } } int main() { Node* head = NULL; addl(&head, 3); addend(&head, 10); addel(head->next, 5); addl(&head, 6); printL(head); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addel(Node* prev_node, int new_data) { if (prev_node == NULL) return; Node* new_node = new Node(); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void addend(Node** head_ref, int new_data) { Node* new_node = new Node(); Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } void Delete(Node** head_ref, int key) { Node* temp = *head_ref; Node* prev = NULL; if (temp == NULL) return; if (temp != NULL && temp->data == key) { *head_ref = temp->next; delete temp; return; } else { while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } prev->next = temp->next; delete temp; } } void printL(Node *node) { while (node != NULL) { cout<<” “<<node->data; node = node->next; } } int main() { Node* head = NULL; addl(&head, 3); addend(&head, 10); addel(head->next, 5); addl(&head, 6); Delete(&head, 5); printL(head); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addel(Node* prev_node, int new_data) { if (prev_node == NULL) return; Node* new_node = new Node(); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void addend(Node** head_ref, int new_data) { Node* new_node = new Node(); Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } void length(Node* head) { int count=0; Node* temp = head; while (temp != NULL) { count++; temp = temp->next; } cout<<count; return; } void Delete(Node** head_ref, int key) { Node* temp = *head_ref; Node* prev = NULL; if (temp == NULL) return; if (temp != NULL && temp->data == key) { *head_ref = temp->next; delete temp; return; } else { while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } prev->next = temp->next; delete temp; } } void printL(Node *node) { while (node != NULL) { cout<<” “<<node->data; node = node->next; } } int main() { Node* head = NULL; addl(&head, 3); addend(&head, 10); addel(head->next, 5); addl(&head, 6); Delete(&head, 5); length(head); // printL(head); return 0; } #include<iostream> using namespace std; class Node { public: int data; Node *next; }; void addel(Node* prev_node, int new_data) { if (prev_node == NULL) return; Node* new_node = new Node(); new_node->data = new_data; new_node->next = prev_node->next; prev_node->next = new_node; } void addl(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } void addend(Node** head_ref, int new_data) { Node* new_node = new Node(); Node *last = *head_ref; new_node->data = new_data; new_node->next = NULL; if (*head_ref == NULL) { *head_ref = new_node; return; } while (last->next != NULL) last = last->next; last->next = new_node; return; } void delfull(Node** head_ref) { Node* temp = *head_ref; Node* next = NULL; while (temp != NULL) { next = temp->next; free(temp); temp = next; } *head_ref = NULL; } void Delete(Node** head_ref, int key) { Node* temp = *head_ref; Node* prev = NULL; if (temp == NULL) return; if (temp != NULL && temp->data == key) { *head_ref = temp->next; delete temp; return; } else { while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } prev->next = temp->next; delete temp; } } void printL(Node *node) { while (node != NULL) { cout<<” “<<node->data; node = node->next; } } int main() { Node* head = NULL; addl(&head, 3); addend(&head, 10); addel(head->next, 5); addl(&head, 6); Delete(&head, 5); delfull(&head); printL(head); return 0; } Which among the following is the disadvantage of linked list as compared to array? Identify the type of linked list whose last pointer contains the address of the first node. Identify the linked list in which each node contains the pointer to the next and previous node. Which among the following is the advantage of linked lists? Which among the following operations is not possible in a linked list but possible in an array?
Quiz Summary
Information
Results
Results
0 Essay(s) Pending (Possible Point(s): 0)
Categories
1. Question
2. Question
3. Question
4. Question
5. Question
6. Question
7. Question
8. Question
9. Question
10. Question
11. Question
12. Question
13. Question
14. Question
15. Question
10. Summary
Linked lists in C/C++ are the 2nd most used data structure after arrays. A linked list is a dynamic data structure that came into existence to overcome the limitations of Arrays. The concept of linked lists is a must for every C/C++ programmer. Now, you are acquainted with the concept of a linked list.
We have much more amazing and exciting tutorials for C Programming, that you can’t afford to miss.
Don’t forget to provide us your precious reviews by commenting below.