A Detailed Study Of Linked List In C++ – A linked list is a data structure that stores data elements in a linear, dynamic manner. Arrays have already been discussed in prior fundamental C++ topics. Arrays are a linear data structure that stores data objects in contiguous regions, as well.
The linked list, unlike arrays, does not store data in contiguous memory locations.
A linked list is made up of elements called “Nodes,” each of which has two components. The first portion contains the data, while the second contains a pointer to the next node. This structure is commonly referred to as a “singly linked list.”
Linked List In C++
We will take a look at the singly linked list in detail in this tutorial.
Operations
The linked list, like other data structures, can be used to perform a variety of operations. We can’t achieve the same random access with a linked list as we can with an array because we can access the element using subscript directly even if it’s somewhere in the middle.
To get to any node, we must first traverse the linked list from the beginning, and only then can we get to the requested node. As a result, reading data from the linked list at random is costly.
A linked list can be used to do the following operations:
Insertion
The linked list’s insertion action adds a new item to the list. Though it may appear straightforward, we know that everytime a data item is added to the linked list, we must alter the next pointers of the previous and next nodes of the new item that we have put.
The location where the new data item will be added is the second factor to consider.
In C++, we can declare a linked list as a structure or as a class. Declaring linked list as a structure is a traditional C-style declaration. A linked list as a class is used in modern C++, mostly while using standard template library.
In the following program, we have used structure to declare and create a linked list. It will have data and pointer to the next element as its members.
#include <iostream>using namespace std;// A linked list nodestruct Node{ int data; struct Node *next;};//insert a new node in front of the listvoid push(struct Node** head, int node_data){ /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode;}//insert new node after a given nodevoid insertAfter(struct Node* prev_node, int node_data){ /*1. check if the given prev_node is NULL */if (prev_node == NULL){ cout<<"the given previous node is required,cannot be NULL"; return; } /* 2. create and allocate new node */ struct Node* newNode =new Node; /* 3. assign data to the node */ newNode->data = node_data; /* 4. Make next of new node as next of prev_node */ newNode->next = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode;}/* insert new node at the end of the linked list */void append(struct Node** head, int node_data){/* 1. create and allocate node */struct Node* newNode = new Node;struct Node *last = *head; /* used in step 5*//* 2. assign data to the node */newNode->data = node_data;/* 3. set next pointer of new node to null as its the last node*/newNode->next = NULL;/* 4. if list is empty, new node becomes first node */if (*head == NULL){*head = newNode;return;}/* 5. Else traverse till the last node */while (last->next != NULL)last = last->next;/* 6. Change the next of last node */last->next = newNode;return;}// display linked list contentsvoid displayList(struct Node *node){ //traverse the list to display each node while (node != NULL) { cout<<node->data<<"-->"; node = node->next; }if(node== NULL)cout<<"null"; } /* main program for linked list*/int main() { /* empty list */struct Node* head = NULL; // Insert 10.append(&head, 10); // Insert 20 at the beginning. push(&head, 20); // Insert 30 at the beginning. push(&head, 30); // Insert 40 at the end. append(&head, 40); // Insert 50, after 20. insertAfter(head->next, 50);cout<<"Final linked list: "<<endl;displayList(head);return 0;} |
Output:
Final linked list:
30–>20–>50–>10–>40–>null
Next, we implement the linked list insert operation in Java. In Java language, the linked list is implemented as a class. The program below is similar in logic to the C++ program, the only difference is that we use a class for the linked list.
class LinkedList{ Node head; // head of list //linked list node declaration class Node{ int data; Node next; Node(int d) {data = d; next = null; }}/* Insert a new node at the front of the list */public void push(int new_data){ //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode;}// Given a node,prev_node insert node after prev_nodepublic void insertAfter(Node prev_node, int new_data){ //check if prev_node is null. if (prev_node == null) { System.out.println("The given node is required and cannot be null"); return; }//allocate node and assign data to itNode newNode = new Node(new_data);//next of new Node is next of prev_nodenewNode.next = prev_node.next;//prev_node->next is the new node.prev_node.next = newNode;} //inserts a new node at the end of the listpublic void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the headif (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last nodenewNode.next = null; // if not the head node traverse the list and add it to the lastNode last = head;while (last.next != null)last = last.next;//next of last becomes new nodelast.next = newNode;return;}//display contents of linked listpublic void displayList(){ Node pnode = head; while (pnode != null){ System.out.print(pnode.data+"-->"); pnode = pnode.next;}if(pnode == null)System.out.print("null");}}//Main class to call linked list class functions and construct a linked listclass Main{public static void main(String[] args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println("\nFinal linked list: "); lList. displayList (); }} |
Output:
Final linked list:
10–>20–>30–>40–>50–>null
In both the program above, C++ as well as Java, we have separate functions to add a node in front of the list, end of the list and between the lists given in a node. In the end, we print the contents of the list created using all the three methods.
Deletion
Delete a node from a linked list, like insertion, requires a variety of points from which the node might be eliminated. From the linked list, we can delete the first, last, or kth node at random. To maintain the linked list intact after deletion, we must update the next pointer and the other pointers in the linked list correctly.
We’ve provided two deletion methods in the following C++ implementation: removing the first node in the list and deleting the final node in the list. We begin by adding nodes to the head of the list. The contents of the list are then displayed after each insertion and deletion.
#include <iostream>using namespace std;/* Link list node */struct Node { int data; struct Node* next; };//delete first node in the linked listNode* deleteFirstNode(struct Node* head){ if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head;}//delete last node from linked listNode* removeLastNode(struct Node* head){ if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; }// first find second last nodeNode* second_last = head;while (second_last->next->next != NULL)second_last = second_last->next;// Delete the last nodedelete (second_last->next);// set next of second_last to nullsecond_last->next = NULL;return head;}// create linked list by adding nodes at headvoid push(struct Node** head, int new_data){ struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode;}// main functionint main(){ /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<"Linked list created "<<endl; for (temp = head; temp != NULL; temp = temp->next) cout << temp->data << "-->"; if(temp == NULL) cout<<"NULL"<<endl; //delete first node head = deleteFirstNode(head); cout<<"Linked list after deleting head node"<<endl; for (temp = head; temp != NULL; temp = temp->next) cout << temp->data << "-->"; if(temp == NULL) cout<<"NULL"<<endl; //delete last node head = removeLastNode(head); cout<<"Linked list after deleting last node"<<endl; for (temp = head; temp != NULL; temp = temp->next) cout << temp->data << "-->"; if(temp == NULL) cout<<"NULL"; return 0;} |
Output:
Linked list created
10–>8–>6–>4–>2–
>NULL
Linked list after deleting head node
8–>6–>4–>2–
>NULL
Linked list after deleting last node
8–>6–>4–>NULL
Next is the Java implementation for deleting nodes from the linked list. The implementation logic is the same as used in the C++ program. The only difference is that the linked list is declared as a class.
class Main {// Linked list node /static class Node { int data; Node next; };// delete first node of linked liststatic Node deleteFirstNode(Node head){ if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head;}// Delete the last node in linked liststatic Node deleteLastNode(Node head){ if (head == null) return null; if (head.next == null) { return null;}// search for second last nodeNode second_last = head;while (second_last.next.next != null)second_last = second_last.next;// set next of second last to nullsecond_last.next = null;return head;}// Add nodes to the head and create linked liststatic Node push(Node head, int new_data){ Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head;}//main functionpublic static void main(String args[]){ // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println("Linked list created :"); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + "-->"); if(temp == null) System.out.println("null"); head = deleteFirstNode(head); System.out.println("Linked list after deleting head node :"); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + "-->"); if(temp == null) System.out.println("null"); head = deleteLastNode(head); System.out.println("Linked list after deleting last node :"); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + "-->"); if(temp == null) System.out.println("null"); }} |
Output:
Linked list created :
9–>7–>5–>3–>1–
>null
Linked list after deleting head node :
7–>5–>3–>1–
>null
Linked list after deleting last node :
7–>5–>3–>null
Count The Number Of Nodes
While traversing the linked list, the operation to count the number of nodes can be done. As we saw in the previous approach, we must traverse the linked list from the beginning anytime we wish to insert/delete a node or display the contents of the linked list.
We may count the number of nodes in the linked list by keeping a counter and incrementing it as we explore each node. This programme will be implemented by the readers.
Arrays And Linked Lists
Let’s analyse how arrays and linked lists stack up against each other now that we’ve seen the operations and implementation of the linked list.
| Arrays | Linked lists |
|---|---|
| Arrays have fixed size | Linked list size is dynamic |
| Insertion of new element is expensive | Insertion/deletion is easier |
| Random access is allowed | Random access not possible |
| Elements are at contiguous location | Elements have non-contiguous location |
| No extra space is required for the next pointer | Extra memory space required for next pointer |
Applications
Because arrays and linked lists are both linear data structures that are used to hold objects, they can be utilised in comparable ways in most applications.
The following are some examples of linked list applications:
- Stacks and queues can be implemented using a linked list.
- When we need to express graphs as adjacency lists, we can use a linked list to implement them.
- A linked list can be used to hold a mathematical polynomial.
- The buckets utilised in hashing are implemented using linked lists in the case of hashing technique.
- We can use a linked list whenever a programme requires dynamic memory allocation because linked lists are more efficient in this scenario.
Conclusion
Linked lists are data structures that are used to hold data items in a sequential but non-contiguous manner. A linked list is a set of nodes that each have a data component and a next pointer that points to the memory address of the list’s next member.
The next pointer of the last entry in the list is set to NULL, signifying the end of the list. The Head is the first element in the list. Insertion, deletion, traversal, and other actions are supported by the linked list. Linked lists are preferable over arrays when dynamic memory allocation is required.
Because we can’t access the elements randomly as we do with arrays, traversing linked lists is expensive. When compared to arrays, however, insertion-deletion procedures are less expensive.
In this tutorial, we learned everything there is to know about linear linked lists. Circular or doubly linked lists are also possible. In our forthcoming tutorials, we’ll take a closer look at these lists.
