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.