Linked list problem statement

Learn the most efficient way to search an element in a doubly linked list.

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a Doubly Linked List, and we need to search for a node with value X in the list and return its position.

Problem Statement Understanding:

Let’s try to understand the problem statement with the help of an example.

If the given doubly linked list is head ↔ 4 ↔ 5 ↔ 7 ↔ 6 ↔ 2 ↔ 1 ↔ 9 and X = 7.

• According to the problem statement, we will have to search for the node with value X in the list, and finally, after finding the node, we have to return its position in the list.
• We can clearly see that node with value 7 is present in the list, and this node is at 3rd position [considering one based indexing] in the list.
• So finally, we will output 3, as 3 is the position of a node with value X = 7 in the given list.

Input: head ↔ 4 ↔ 5 ↔ 7 ↔ 6 ↔ 2 ↔ 1 ↔ 9, X[element to be searched] = 7
Output: 3

Also, there can be multiple nodes with value X in the list, so that's why we will return the position of the first node with value X in the list.

Note: If there is no node with the value of X in the list, the output will be -1.

Now I think the problem statement is clear, so let’s see how we can approach it.

Let’s move to the approach section.

Approach

In order to find an element X in the given doubly linked list:

• We need to traverse the list until either the node is null or we have found the node with value X which we were searching for.
• Also, we need a variable position that will keep the count of the elements we have visited so far.
• Then finally, we will return the location of the element X in our list which will be given by the variable position.

Algorithm

• First, we need to create a variable position that will keep track of number of nodes traversed.
• Then using a pointer, say, temp, we will traverse the given list till the next node of the temp is null, or we found the element we were searching for.
• Then we will check if the current node's data is equal to the element we were searching for or not.
  • If temp.data == X, our position variable will give the location of the element to be searched for and we will output it.
  • Else, it means that there is no node with value X in the given list, so we will output -1.

Dry Run

Code Implementation

#include using namespace std; struct DLLNode { int data; DLLNode* next; DLLNode* prev; }; void push[DLLNode** head, int new_data]{ DLLNode* new_node = [DLLNode*]malloc[sizeof[struct DLLNode]]; new_node->data = new_data; new_node->prev = NULL; new_node->next = [*head]; if [[*head] != NULL] { [*head]->prev = new_node; } [*head] = new_node; } int search_the_element[DLLNode** head, int X]{ DLLNode* temp = *head; int position = 0; while [temp->data != X && temp->next != NULL] { position++; temp = temp->next; } if [temp->data != X] return -1; return [position + 1]; } int main[] { DLLNode* head = NULL; int X = 7; push[&head, 9]; push[&head, 1]; push[&head, 2]; push[&head, 6]; push[&head, 7]; push[&head, 5]; push[&head, 4]; cout<

public class Prepbytes { static class Node { int data; Node next; Node prev; }; static Node push[Node head_ref, int new_data] { Node new_node = new Node[]; new_node.data = new_data; new_node.prev = null; new_node.next = head_ref; if [head_ref != null] { head_ref.prev = new_node; } head_ref = new_node; return head_ref; } static int search[Node head_ref, int x] { Node temp = head_ref; int position = 1; while [temp.data != x && temp.next != null] { position++; temp = temp.next; } if [temp.data != x] return -1; return position; } public static void main[String[] args] { Node head = null; int X = 7; head = push[head, 9]; head = push[head, 1]; head = push[head, 2]; head = push[head, 6]; head = push[head, 7]; head = push[head, 5]; head = push[head, 4]; System.out.print[search[head, X]]; } }

Output

3

Time Complexity: O[n], where n is the total number of nodes in the Doubly Linked List.

So, in this blog, we have tried to explain how you can search a value in a doubly linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Given a singly linked list, group all odd nodes together followed by all the even nodes. Please note here we are talking about the node number and not the value in the nodes.

The program should run in O[1] space complexity and O[nodes] time complexity.

Continue reading “Rearrange a linked list such that all even index nodes come after all odd index nodes”

Given a circular linked list, you have to count the number of nodes in it.

For example:

A Circular linked list with a total of 6 nodes.

Solution

Well, there is only one way to solve the problem, and that is to traverse the circular linked list keeping the track of the number of nodes as we traverse. Nothing really fancy, right? In this tutorial, we will show you how we can solve the problem using straight-forward way i.e traversing and counting, and then we will also see how we can design a recursive solution to solve the problem, overkill, I know, but still, there’s no harm to know different ways to solve a problem, right?

Continue reading “Count the number of nodes in a circular linked list”

Given a sorted linked list and a node, insert the node in the linked list such that the linked list still remain sorted.

For Example

Input: 2 -> 8 -> 12 -> 41 ->NULL, val = 30
Output: 2 -> 8 -> 12 -> 30 ->41 -> NULL.

Continue reading “Insert a node in a sorted linked list”

Given a linked list, write a program to delete it.

For Example

Input: 2->4->6->9->NULL *After the Deletion*

Output: The Linked List is Empty.

Assume the structure of a Linked List node is as follows. 

def __init__[self, data]:

Explain the functionality of the following C functions.

1. What does the following function do for a given Linked List?

void fun1[struct Node* head]   cout data data];

static void fun1[Node head]     System.out.print[head.data + " "];

print[head.data, end = " "]

static void fun1[Node head]     Console.Write[head.data + " "];

document.write[head.data];

fun1[] prints the given Linked List in the reverse way. For Linked List 1->2->3->4->5, fun1[] prints 5->4->3->2->1.

2. What does the following function do for a given Linked List? 

void fun2[struct Node* head]     cout data data];

static void fun2[Node head]     System.out.print[head.data + " "];     System.out.print[head.data + " "];

print[head.data, end = " "]     print[head.data, end = " "]

static void fun2[Node head]     Console.Write[head.data + " "];     Console.Write[head.data + " "];

document.write[head.data];   document.write[head.data];

fun2[] prints alternate nodes of the given Linked List, first from head to end, and then from end to head. If Linked List has even number of nodes, then fun2[] skips the last node. For Linked List 1->2->3->4->5, fun2[] prints 1 3 5 5 3 1. For Linked List 1->2->3->4->5->6, fun2[] prints 1 3 5 5 3 1.

Below is a complete running program to test the above functions.

cout data next = [*head_ref];     coutdata]; void fun2[struct Node* start]   printf["%d  ", start->data];   printf["%d  ", start->data]; void push[struct Node** head_ref, int new_data]           [struct Node*] malloc[sizeof[struct Node]];   new_node->data  = new_data;   new_node->next = [*head_ref];   struct Node* head = NULL;   printf["Output of fun1[] for list 1->2->3->4->5 \n"];   printf["\nOutput of fun2[] for list 1->2->3->4->5 \n"];

static void fun1[Node head]         System.out.print[head.data + " "];     static void fun2[Node start]         System.out.print[start.data + " "];         System.out.print[start.data + " "];     static Node push[Node head_ref, int new_data]         Node new_node = new Node[];         new_node.data = new_data;         new_node.next = [head_ref];     public static void main[String[] args]         System.out.print["Output of fun1[] for " +                          "list 1->2->3->4->5 \n"];         System.out.print["\nOutput of fun2[] for " +                            "list 1->2->3->4->5 \n"];

def __init__[self, data]:     print[head.data, end = " "]     print[start.data, end = " "]     print[start.data, end = " "] def push[ head, new_data]:     new_node = Node[new_data] print["Output of fun1[] for list 1->2->3->4->5"] print["\nOutput of fun2[] for list 1->2->3->4->5"]

static void fun1[Node head]         Console.Write[head.data + " "];     static void fun2[Node start]         Console.Write[start.data + " "];         Console.Write[start.data + " "];     static Node Push[Node head_ref, int new_data]         Node new_node = new Node[];         new_node.data = new_data;         new_node.next = [head_ref];     public static void Main[String[] args]         Console.Write["Output of fun1[] for " +                         "list 1->2->3->4->5 \n"];         Console.Write["\nOutput of fun2[] for " +                         "list 1->2->3->4->5 \n"];

document.write[head.data + " "];         document.write[start.data + " "];         document.write[start.data + " "];     function Push[head_ref, new_data]         let new_node = new Node[new_data];         new_node.next = [head_ref];     document.write["Output of fun1[] for " +                   "list 1->2->3->4->5 " + " "];     document.write["Output of fun2[] for " +                   "list 1->2->3->4->5 " + " "];

Output: 

Output of fun1[] for list 1->2->3->4->5 5 4 3 2 1 Output of fun2[] for list 1->2->3->4->5 1 3 5 5 3 1

Please write comments if you find any of the answers/explanations incorrect, or you want to share more information about the topics discussed above.
 

Article Tags :

Practice Tags :