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. 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. 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. 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. 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.
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.
