Linked List Data Structure

⌚What are Linked List?

A Linked List in data structure is a collection of objects connected by a sequence of links. Each connection has a distinct link tied to it. The linked list is the most commonly used data structure after the array. The terms listed below are important to understand in order to grasp the concept of Linked List.

🚀Each link in a linked list can store an element, which is a piece of data.
🚀In a linked list, each link has a Next link that leads to the next link.
🚀The connecting link to the first link in a Linked List is referred to as First.

A Linked List is a collection of things known as nodes that are randomly stored in memory. A node has two fields: data recorded at that address and a pointer to the memory's next node. The list's last node contains a null pointer.

⌚Definition of a Node in various languages

The value of the head points to NULL if the linked list is empty.
The nodes in a list are made up of at least two components:

1) information (we can store integer, strings or any type of data).
2) A reference to the next node (or a pointer to it) (connects one node to another)

In C and C++, a node can be represented as a structure.
In Java or C#, a LinkedList can be expressed as a class, and a Node can be stated as a separate class.

In C :

// A linked list node
struct Node {
    int data;
    struct Node* next;
};    

In C++ :

// A linked list node
struct Node {
    int data;
    Node* next;
};    

In Java :

class LinkedList {
    Node head; // head of the list
 
    /* Linked list Node*/
    class Node {
        int data;
        Node next;
 
        // Constructor to create a new node
        // Next is by default initialized
        // as null
        Node(int val) { data = val; }
    }
}

⌚Basic Operations on Linked List

The basic operations that a list enables are as follows.

🚀 Insertion : Insertion adds a new element to the list's beginning.
🚀 Deletion : It is the process of removing an item from the top of a list.
🚀 Display :The complete list will be displayed.
🚀 Search : The supplied key is used to search for an element.
🚀 Deletes : It an element whose key is supplied.

⌚Uses of Linked List

🚀 The list does not have to be kept in order in the memory.
🚀The node can be located anywhere in memory and linked to form a list.
🚀This results in optimal space usage.
🚀The list size is restricted by memory and does not need to be announced ahead of time.
🚀The linked list cannot include an empty node.
🚀In a singly linked list, we can store values of primitive types or objects.

⌚Why use linked list over array?

Until now, we've used an array data structure to organise a collection of elements that need to be stored separately in memory. Array, on the other hand, has a number of pros and disadvantages that must be considered when deciding on the data structure that will be utilised throughout the programme.

The following restrictions apply to the array:
🚀Before using an array in a programme, the size of the array must be known ahead of time.
🚀The process of increasing the array's size takes time.
🚀It's practically difficult to expand the array's size during runtime.
🚀The elements of the array must be stored in memory in the correct sequence.
🚀Any element in the array must have all of its predecessors shifted before it can be inserted. A linked list is a data structure that can overcome all of an array's restrictions.

The use of a linked list is advantageous because:

🚀It dynamically allocates memory.
🚀The nodes of a linked list are kept in memory in a non-contiguous manner and are connected together via pointers.
🚀Because we don't have to describe its size at the time of declaration, sizing is no longer an issue.
🚀The list expands in response to the program's needs and is constrained by the amount of memory available.

⌚ Drawbacks of Linked List

🚀 It is not permitted to have unrestricted access.
🚀Beginning with the first node, we must access elements progressively (head node). As a result, the default implementation of binary search with linked lists is inefficient.
🚀Each element of the list requires additional memory space for a pointer.
🚀This isn't cache-friendly.
🚀There is locality of reference in array items, which is not present in linked lists, because they are continuous locations.

⌚ Types of Linked List

Below is a list of the various forms of linked lists.

🚀 Singly Linked List : The only way to navigate through an item in a simple linked list is to go ahead.
🚀 Doubly Linked List : A Doubly Linked List's items can be shifted forward and backward.
🚀 Circular Linked List : A circular linked list's last item links to the first element labelled next, whereas the first element links to the last element labelled previous.

⌚Operations on Linked List

Operation	Process
Insertion at the beginning	It entails moving any element to the top of the list. To make the new node the top of the list, we only need to make a few link modifications.
Insertion at the end	Insertion at the end of the linked list is required. The new node might either be the lone one in the list or the last one. In each case, different logics are implemented.
Insertion after specified node	It entails inserting after the linked list's selected node. To get to the node where the new node will be inserted, we must skip the desired number of nodes.
Deletion at beginning	It entails removing a node from the list's beginning. This is the simplest of all the operations. It only requires a few tweaks to the node pointers.
Deletion at the end of the list	It entails removing the list's last node. It's possible for the list to be empty or full. For each circumstance, a separate logic is implemented.
Deletion after specified node	It entails deleting the node in the list following the given node. To get to the node, we must skip the desired amount of nodes, after which the node will be destroyed. This necessitates going down the list.
Traversing	We simply visit each node of the list at least once during traversal in order to do a specified function on it, such as printing the data section of each node present.
Searching	We match each element of the list with the specified element when searching. If an element is located on any of the locations, the element's location is returned; otherwise, null is returned.

⌚Insertion Operation

Inserting a new node to a linked list is a multi-step process.
Assume we're inserting a node B (NewNode) between A (LeftNode) and C (CenterNode) (RightNode). Then, next to C, place B.

new_node.next −> right_node;

The new node should now be pointed to by the following node on the left.

left_node.next −> new_node;

The new node will be placed in the midst of the two.

The second last node of the list should point to the new node, and the new node will point to NULL when it is inserted at the end.

⌚Deletion Operation

Deletion is a multi-step process as well. Visual representation will be used to teach us. To begin, utilise searching strategies to locate the node to be eliminated as a target.

left_node.next −> target_node.next;

The left (previous) node of the target node should now point to the target node's next node.

As a result of this action, the link relating to the target node will be erased. With the code below, we'll remove what the target node is pointing at.

target_node.next −> NULL;

The node that was removed must be utilised. We have the option of leaving things in memory or dealinglocating memory and completely wiping out the target node.

⌚Reversing Operation

This is a thorough operation. The last node must be directed by the head node, and the entire linked list must be reversed.
We start by going to the end of the list. It's supposed to point to NULL. We'll now make it point to the previous node.
We must ensure that the last node is not the final node. So we'll have a temporary node that resembles the head node and points to the last node.
Using the temp node, we'll point the head node to the new first node.

⌚ Singly Linked List

A singly linked list is a collection of elements that are arranged in a specific order. The number of elements may vary depending on the program's requirements. In a single linked list, a node is made up of two parts: data and link. The data component of the node stores the actual data that the node will represent, while the link part stores the address of the node's immediate successor. To put it another way, we may say that each node has only the next pointer, therefore we can't traverse the list backwards.

The marks earned by the student in each topic are stored in the data section of each node. The null pointer in the address part of the last node identifies it as the last node in the list. In the data section of the list, we can have as many elements as we like.

⌚ Circular Linked List

In a circular motion The last node of a singly linked list carries a pointer to the list's first node. Circular singly linked lists and circular doubly linked lists are also possible.
We traverse a circular singly linked list until we reach the starting node. There is no beginning or conclusion to the circular list of singlely liked items. In the following part of any of the nodes, there is no null value.
A circular singly linked list is depicted in the image below.

⌚Doubly Linked List

A doubly linked list is a more advanced type of linked list that has a pointer to both the previous and next node in the sequence. As a result, a node in a doubly linked list has three parts: node data, pointer to the next node in the sequence (next pointer), and pointer to the prior node (previous pointer). The graphic depicts a sample node in a doubly linked list.

The first node's previous portion and the last node's next part will always be null, signifying the end of each direction.

Structure of a node in doubly linked list in C can be given as :

    struct node   
    {  
        struct node *prev;   
        int data;  
        struct node *next;   
    }           

Because each node contains the address of the next node and has no record of its previous nodes, we can only navigate in one way in a singly linked list. The limitation of a singly linked list is overcome by a doubly linked list. We can obtain all the facts about the previous node by using the previous address stored inside the previous section of each node because each node of the list has the address of its previous node.

⌚ Why Linked List?

If we want to store the data in linear way then we can use array , however they have the following drawbacks.

1) Because the size of the arrays is fixed, we must know the maximum number of elements ahead of time. In addition, regardless of consumption, the allotted memory is always equal to the higher limit.
2) Adding a new element to an array of elements is costly since space must be made for the new elements, and current elements must be adjusted to make room. However, in a linked list, if we have the head node, we can traverse to any node through it and insert a new node at the desired location.

For example, suppose we have a sorted collection of IDs in an array called id[].
[1000, 1010, 1050, 2000, 2040]
And if we want to add a new ID 1005, we'll have to shift all the components after 1000 to keep the sorted order (excluding 1000).
Arrays are also expensive to delete unless you employ some particular procedures. To delete 2000 in id[], for example, everything after 2000 must be shifted, which adds a lot of work to the code and reduces its efficiency.

🚀Conclusion

We have cover linked list in this page, We have see that A linked list is a linear data structure that must be traversed starting at the top and ending at the bottom. Unlike arrays, where random access is available, a linked list requires sequential traversal to reach its nodes. Many applications need traversing a linked list.

---