A Detailed Study Of Linked List In C++



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 node
struct Node
{
   int data;
   struct Node *next;
};
//insert a new node in front of the list
void 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 node
void 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 contents
void 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_node
public 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 it
Node newNode = new Node(new_data);
//next of new Node is next of prev_node
newNode.next = prev_node.next;
//prev_node->next is the new node.
prev_node.next = newNode;
}
    //inserts a new node at the end of the list
public 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 head
if (head == null)
        {
head = new Node(new_data);
return;
        }
        //set next of new node to null as this is the last node
newNode.next = null;
// if not the head node traverse the list and add it to the last
Node last = head;
while (last.next != null)
last = last.next;
//next of last becomes new node
last.next = newNode;
return;
}
//display contents of linked list
public 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 list
class 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 list
Node* 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 list
Node* removeLastNode(struct Node* head)
{
   if (head == NULL)
   return NULL;
   if (head->next == NULL) {
      delete head;
      return NULL;
   }
// first find second last node
Node* second_last = head;
while (second_last->next->next != NULL)
second_last = second_last->next;
// Delete the last node
delete (second_last->next);
// set next of second_last to null
second_last->next = NULL;
return head;
}
// create linked list by adding nodes at head
void push(struct Node** head, int new_data)
{
   struct Node* newNode = new Node;
   newNode->data = new_data;
   newNode->next = (*head);
   (*head) = newNode;
}
// main function
int 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 list
static 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 list
static Node deleteLastNode(Node head)
{
   if (head == null)
   return null;
   if (head.next == null) {
   return null;
}
// search for second last node
Node second_last = head;
while (second_last.next.next != null)
second_last = second_last.next;
// set next of second last to null
second_last.next = null;
return head;
}
// Add nodes to the head and create linked list
static Node push(Node head, int new_data)
{
   Node newNode = new Node();
   newNode.data = new_data;
   newNode.next = (head);
   (head) = newNode;
   return head;
}
//main function
public 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.

Jennifer Thomas
Jennifer Thomas is the Co-founder and Chief Business Development Officer at Cybers Guards. Prior to that, She was responsible for leading its Cyber Security Practice and Cyber Security Operations Center, which provided managed security services.