From implementing stacks to storing abstract types of data, the linked lists carry the functions with the utmost efficiency.
But, did you know that the linked lists can be categorized in terms of their structures also?
Well, a linked list is typically the form of data structure that stores the elements in a series that do not have any correlation with their prior sequence.
Read along till the end of this blog to learn more about linked lists while enhancing your knowledge base of the concepts of the first and last occurrences of x and how you can flatten a linked list.
Types Of Reinforced Concrete Molds Structures
Types of linked lists in Data Structures
The types of linked lists that we have discussed below are based on the structure of the lists. But, that does not imply the fact that you cannot change or modify the structure of the linked lists.
The beginner-level programmers should be aware of the fact that you can implement your own type of linked list as per the solution of the problem.
With that said, there are typically four types of linked lists that are crucial for the study of data structure:
- Singly-linked lists: This sort of linked list only follows a certain direction. This means that you can only navigate this list in one direction, from the head node to the tail node of the list. The nodes of the list consist of two basic pieces of information, we have the pointer containing the address of the next node and the data stored in the node.
This structure of the linked list is used most often when it comes to implementing data for your solution. Typically if you are starting out with studying a linked list, more often than not it will be a singly-linked list.
- Doubly linked list: As the name suggests this list can be navigated in both directions. Quite different from the singly linked list the doubly linked list consists of an extra pointer which is referred to as the “previous pointer”. This is the pointer that points towards the previous node.
Every single node present in a doubly linked list consists of three different parts, i.e the data part and the two address parts of the node. Since it is a doubly linked list we can observe two different pointers, one of them will be pointing towards the previous node while the other will point towards the next one.
- Circular linked list: When the last node of a linked list is pointing towards its first node it is known as a circular linked list. This explains the reason why this list can only be navigated in a certain direction. Also, while you are navigating this list you have to keep in mind that the list will reach the head node after a few strings.
You can state that each node in a circular linked list points to its next node. Due to this, we observe that the structure represents a circle because the last node stores the address for the very first node of the list.
- Circular doubly linked list: This list is quite a tricky one because it shares the features of both a doubly linked list and a circular linked list.
Hence, this linked list also shares an extra pointer, and similar to the circular linked list the first and last nodes of this are joined too. You can navigate this list in two different directions much like the doubly linked list because of the presence of the pointer.
7 Types of Data That Every Demand Forecasting Expert Needs
Flatten a linked list
In order to flatten a linked list, you can use the concept of Merge(). This concept effectively describes how you can create several smaller subproblems in order to solve a relatively bigger problem in a much faster process.
Flattening a linked list basically relates to creating a series of lists by converting various linked lists into a singular unit. This way if you are trying to traverse through the list it will make it a lot easier now that they are in the format of a series.
Coming back to the merge sort procedure, it basically breaks down a complicated problem into simpler problems which in return makes it easier to solve.
In the end after attaining the solution, all you have to do is combine the solutions, and voila! There you will have a fully sorted solution for the complicated problem.
Now we will look into a problem related to the first and last occurrences of x.
First and last occurrences of x
Problem:
Search for 10 in the given array:
0 3 2 3 4 5 6
2 4 10 10 10 18 20
Answer: So we can see from the above problem that 10 is present in indexes- 2, 3, and 4. And we have to find the first occurrence in the array. Later on, we’ll figure out the last occurrence.
1st
10 is the mid occurrence in the array and we have to make sure that it is the first occurrence.
Starting with the lowest and the highest occurrence:
0+6/2 = 3 (this is the mid occurrence)
We have to find out if the left-hand side occurrences from 6 contain 10 as the first occurrence Or not. In order to find that we have to subtract high from mid.
0+2/2 = 1 (mid)
Now, start = mid+1 = 2
res= 2
So use the following syntax for finding the first occurrence:
int start = 0
int end = size-1
int res = -1
while (start <= end)
2
int mid = start + (end – start/2)
if (end = mid)
res = mid
end = mid – 1
elseif (end < mid)
end = mid – 1
else
start = mid – 1
You have to follow this syntax in order to find the first and the last occurrences as well. In the given problem we have to figure out whether 10 is present in the first and the last occurrence Or not.
Steps for Implementing a Linked List In JavaScript
When you conclude what sort of linked list you wish to execute. You should adhere to a particular arrangement of directions to carry out it in JavaScript. The interaction incorporates particular advances and works that you really want to learn.
Learning these will likewise assist you in removing loop in linked list and resolve the painter’s partition problem.
The following are the steps for Implementing a Linked List In JavaScript
1: Create A Specific Function For Creating A New Node
2: Create Linked List Class
3: Add Insert And Print Method
4: Add Remove Method For Linked List Class
Example Problem
Consider a problem on a singly linked list of nodes, where we would be given a linked list of integers, which may contain a cycle, remove the cycle if present.
For example, in the following linked list, we have a cycle in when remove loop in linked list should look like the following:
In order to solve the above problem we need to approach the following:
- Detect the cycle in the linked list and confirm whether it is even present or not.
- Remove the cycle if it is present in the linked list.
Conclusion
Wrapping up the above blog, we would suggest that if you are tackling a problem related to finding the first and last occurrences of x you might want to sort the list first and run the syntax.
You can change the codes a bit to fit your assumptions from the array. But the basic structure should remain unchanged. Other than that we have discussed the types of linked lists in this blog.
Finally, you will also find the method to flatten a linked list, which is by using the merge sort algorithm.
Click here to read about – How to Use UX Design website to improve Data Security?
