How to conduct searching in linked list? If you are looking for a clear answer to this question, you should get acquainted with our sample below. As with all samples that are published on our blog, it was completed by an expert who is knowledgeable in the discipline. The special feature of our service is that we help students with technical tasks. You can find information on how to complete certain assignments in such disciplines as math, physics, astronomy, and others.
If you are interested in a topic or issue that is not presented on our website, you are welcome to make an order. Doing so, you will be able to ask our experts to help you with a specific task. All experts have graduated from higher educational affiliations and possess vast experience. You can apply to them anytime. Our service is available 24/7! Be quick to ask for help with assignment writing!
The Algorithm for the Search in a Linked List
This algorithm can be implemented using the recursive and non-recursive way. Recursive solutions are generally more understandable and less optimal. For example, the recursive implementation of this task is almost two times shorter than the non-recursive, but it takes O(n) space, where n is the number of elements of a linked list.
When solving this problem, remember that you can choose the value of k so that when transferring k = 1 we obtain the last element, 2 – the penultimate, etc. Or choose k so that k = 0 corresponds to the last element.
Solution 1: linked list of known size
If the size of the linked list is known, the k-th element can be easily found from the end (L – k). All you need to do is go through the list and find the item.
Solution 2: recursive solution
This algorithm recursively iterates through a linked list. When the last element is reached, the algorithm starts the countdown, and the counter is reset to 0. Each step increments the counter by 1. When the counter reaches k, the desired item is found.
The implementation of this algorithm is quite short and simple: simply pass back an integer value through the stack. Unfortunately, the return operator can not return the value of the node. So how do we get around this difficulty?
Approach A: do not return the element
We can forget about the return of the item, as it is enough to withdraw it as soon as it is found. And in the “return” operator we can return the value of the counter.
public static int counter(node head, int k) {
if (head == null) {
return 0;
}
int i = counter(head.next, k) + 1;
if (i == k) {
System.out.println(head.data);
}
return i;
}
Solution is correct, but we can go the other way.
Approach B: use C++
The second method is the use of C++ and transferring the value by reference. This approach allows us not only to return the value of the node but also to update the counter by passing a pointer to it.
node* counter(node* head, int k, int& a) {
if (head == NULL) {
return NULL;
}
node* nod = counter(head->next, k, a);
a = a + 1;
if (a == k) {
return head;
}
return nod;
}
Solution 3: iterative solution
The iterative solution is more complex, but also more optimal. We can use two pointers: pointer1 and pointer2. Initially, both pointers point to the top of the list. Then we move forward pointer2 by k nodes. Now we are beginning to move both pointers at the same time. When pointer2 reaches the end of the list, pointer1 will point to the item we want it to.
node counter(node head, int k) {
if (k <= 0) return 0;
node pointer1 = head;
node pointer2 = head;
for (int i = 0; i < k – 1; i++) {
if (pointer2 == null) return null;
pointer2 = pointer2.next;
}
if (pointer2 == null) return null;
while (pointer2.next != null) {
pointer1 = pointer1.next;
pointer2 = pointer2.next;
}
return pointer1;
}
Thanks for your attention!