As a programmer, there are high chances you must have heard of the concept of linked list. But what is a linked list?
Linked list is a form of linear data structure, linked lists are somewhat analogous to arrays in their organization. In contrast to arrays, the members of linked lists are not all stored in the same physical location. Instead, they are linked together through the use of pointers.
They are made up of a network of nodes that are connected in some way. This part includes information from the node that came before it as well as the address of the node that comes after it.
What Does a Linked List Consist Of?
When compared to other linear data storage systems, arrays have several problems, such as:
- Given that the dimensions of reverse an array cannot be altered, the first step is to establish the maximum number of elements that it can hold. The amount of RAM that is available for utilization is frequently limited, regardless of how it is put to use.
- To add or remove entries from an array requires a significant investment of effort and money. To make room in a linked list for new items, the entries that are already existing need to be pushed out of the way first.
Advantages of Linked Lists
Arrays are inferior to linked lists in many ways. Linked lists are superior in many ways.
- An array's variables
- It is simple to either put on or remove a loop in a linked list
Disadvantages of Linked Lists
- The decision to allow access is not made on a whim. You can gather elements by going back through the tree, starting at the trunk (head node). This suggests that a binary search over linked lists cannot be performed quickly with the configuration that is already in place.
- Additional RAM is required to point to each item in the list.
- Not ought to be kept in a cache: Because the components that makeup reverse an array that is close to one another, it has a locality of reference. On the other hand, linked lists do not have it because the components of linked lists are spread apart.
Linked List Types
Simple: This particular kind of linked list can only be navigated in a single direction at a time.
Doubly: By following these links, you can go in either direction through the page (forward and backwards).
Circular: In this type of linked list, the first node (also known as the “head”) has a connection to the final node (also known as the “tail”) in its prior pointer, and the last node (also known as the “tail”) has a connection to the head node in its next pointer.
Representation
A linked list's nature can be determined from the location of the pointer to the list's initial node. The “head” of a linked list is the node that comes first in the list. If the linked list does not have a terminating item, the head value will be set to NULL.
Each list node is made up of at least two components, which are as follows:
- One particular nugget of information (we can store integers, strings, or any type of data).
- Depending on the situation, this can be the address of the next node in a network or the address of a different node.
In C, one way to express a node is through the use of structures.
How To Remove Loop in Linked List?
There is a list that can be used, which is linked together. Return True if the linked list has a loop in it, and then remove the loop in a linked list
When moving the pointer to the next node in a linked list makes it possible to return to the same node multiple times in quick succession, we have a cycle in that list.
Using HashSet
The quickest and easiest answer to this issue is to examine the linked list to determine whether or not each node in the list has been visited. It's possible to accomplish this with the help of a hashmap. If a node has already been constructed, the reference that is now being used should be changed to NULL.
Algorithm
- Make a brand new map out of the hashes.
- Continue iterating over the linked list up until the pointer at the head of the list is no longer NULL.
- A loop will be included in the linked list if the currently selected node is also included in the hashmap. At this juncture, the node in question ought to be labelled as “null.”
- After adding the node to the hash set in the last step, the traverse should go on.
- There are no cycles in the linked list if and only if none of the nodes meets the requirements listed in the last sentence.
Using Floyd’s Cycle Detection Algorithm
A fast pointer and a slow pointer are utilized to assess whether or not the loop is cyclical. Because of this limitation, the slow pointer can only move one node at a time. On the other hand, the rapid pointer enables the simultaneous movement of two nodes.
Both fast and slow pointers will become entangled with one another if the linked list comprises a loop.
Algorithm
- Create two directional arrows, one that moves quickly and one that moves slowly. In the linked list, both of these ought to go before anything else.
- Repeat the process until the fast pointer hits the very last item on the linked list; once it does, the operation will be unsuccessful.
- If the fast pointer travels to the end of the linked list, there will be no cycles. It is expected that the response will be “False” in this case.
- If this is not the case, move the quick pointer forward two nodes (quick = next -> next) while moving the slow pointer forward one node (slow = slow -> next).
- If both the fast and the slow pointers ever point to the same node, the presence of a loop can be determined by setting node->next = NULL and returning True.
Wrapping it up!
The fast and slow pointer approach makes use of a system in which the fast pointer progresses by two nodes and the slow pointer advances by one node. This allows for accurate loop location using the fast and slow pointer methods.
If the linked list has a loop in it, then the fast pointers and the slow pointers are going to run into each other at some point. So, it’s necessary to remove the loop in the linked list.
