Buscar un elemento en una lista doblemente enlazada

Dada una lista doblemente enlazada (DLL) que contiene N Nodes y un entero X , la tarea es encontrar la posición del entero X en la lista doblemente enlazada. Si no se encuentra dicha posición, imprima -1 .

Ejemplos:

Entrada: 15 <=> 16 <=> 8 <=> 7 <=> 13, X = 8 
Salida: 3 
Explicación: X (= 8) está presente en el tercer Node de la lista doblemente enlazada. 
Por lo tanto, la salida requerida es 3

Entrada: 5 <=> 3 <=> 4 <=> 2 <=> 9, X = 0 
Salida: -1 
Explicación: X (= 0) no está presente en la lista doblemente enlazada. 
Por lo tanto, la salida requerida es -1

Enfoque: siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos pos , para almacenar la posición del Node que contiene el valor de datos X en la lista doblemente enlazada .
• Inicialice un puntero, digamos temp , para almacenar el Node principal de la lista doblemente enlazada .
• Itere sobre la lista vinculada y para cada Node, verifique si el valor de los datos de ese Node es igual a X o no. Si se encuentra que es cierto, imprima pos .
• De lo contrario, imprima -1 .

A continuación se muestra la implementación del enfoque anterior.

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node of
// the doubly linked list
struct Node {
 
    // Stores data value
    // of a node
    int data;
 
    // Stores pointer
    // to next node
    Node* next;
 
    // Stores pointer
    // to previous node
    Node* prev;
};
 
// Function to insert a node at the
// beginning of the Doubly Linked List
void push(Node** head_ref, int new_data)
{
 
    // Allocate memory for new node
    Node* new_node
        = (Node*)malloc(sizeof(struct Node));
 
    // Insert the data
    new_node->data = new_data;
 
    // Since node is added at the
    // beginning, prev is always NULL
    new_node->prev = NULL;
 
    // Link the old list to the new node
    new_node->next = (*head_ref);
 
    // If pointer to head is not NULL
    if ((*head_ref) != NULL) {
 
        // Change the prev of head
        // node to new node
        (*head_ref)->prev = new_node;
    }
 
    // Move the head to point to the new node
    (*head_ref) = new_node;
}
 
// Function to find the position of
// an integer in doubly linked list
int search(Node** head_ref, int x)
{
 
    // Stores head Node
    Node* temp = *head_ref;
 
    // Stores position of the integer
    // in the doubly linked list
    int pos = 0;
 
    // Traverse the doubly linked list
    while (temp->data != x
           && temp->next != NULL) {
 
        // Update pos
        pos++;
 
        // Update temp
        temp = temp->next;
    }
 
    // If the integer not present
    // in the doubly linked list
    if (temp->data != x)
        return -1;
 
    // If the integer present in
    // the doubly linked list
    return (pos + 1);
}
 
// Driver Code
int main()
{
    Node* head = NULL;
    int X = 8;
 
    // Create the doubly linked list
    // 18 <-> 15 <-> 8 <-> 9 <-> 14
    push(&head, 14);
    push(&head, 9);
    push(&head, 8);
    push(&head, 15);
    push(&head, 18);
 
    cout << search(&head, X);
 
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
   
  // Structure of a node of
  // the doubly linked list
  static class Node
  {
    // Stores data value
    // of a node
    int data;
     
    // Stores pointer
    // to next node
    Node next;
     
    // Stores pointer
    // to previous node
    Node prev;
  };
   
  // Function to insert a node at the
  // beginning of the Doubly Linked List
  static Node push(Node head_ref, int new_data)
  {
     
    // Allocate memory for new node
    Node new_node = new Node();
     
    // Insert the data
    new_node.data = new_data;
     
    // Since node is added at the
    // beginning, prev is always null
    new_node.prev = null;
     
    // Link the old list to the new node
    new_node.next = head_ref;
     
    // If pointer to head is not null
    if (head_ref != null)
    {
       
      // Change the prev of head
      // node to new node
      head_ref.prev = new_node;
    }
     
    // Move the head to point to the new node
    head_ref = new_node;
    return head_ref;
  }
   
  // Function to find the position of
  // an integer in doubly linked list
  static int search(Node head_ref, int x)
  {
     
    // Stores head Node
    Node temp = head_ref;
     
    // Stores position of the integer
    // in the doubly linked list
    int pos = 0;
     
    // Traverse the doubly linked list
    while (temp.data != x
               && temp.next != null)
    {
      // Update pos
      pos++;
       
      // Update temp
      temp = temp.next;
    }
     
    // If the integer not present
    // in the doubly linked list
    if (temp.data != x)
      return -1;
    // If the integer present in
    // the doubly linked list
    return (pos + 1);
  }
   
  // Driver Code
  public static void main(String[] args)
  {
    Node head = null;
    int X = 8;
    // Create the doubly linked list
    // 18 <-> 15 <-> 8 <-> 9 <-> 14
    head = push(head, 14);
    head = push(head, 9);
    head = push(head, 8);
    head = push(head, 15);
    head = push(head, 18);
    System.out.print(search(head, X));
  }
}
 
// This code is contributed by Rajput-Ji

// C# program to implement
// the above approach
using System;
 
class GFG{
   
// Structure of a node of
// the doubly linked list
public class Node
{
     
    // Stores data value
    // of a node
    public int data;
     
    // Stores pointer
    // to next node
    public Node next;
     
    // Stores pointer
    // to previous node
    public Node prev;
};
 
// Function to insert a node at the
// beginning of the Doubly Linked List
static Node push(Node head_ref, int new_data)
{
     
    // Allocate memory for new node
    Node new_node = new Node();
     
    // Insert the data
    new_node.data = new_data;
     
    // Since node is added at the
    // beginning, prev is always null
    new_node.prev = null;
     
    // Link the old list to the new node
    new_node.next = head_ref;
     
    // If pointer to head is not null
    if (head_ref != null)
    {
         
        // Change the prev of head
        // node to new node
        head_ref.prev = new_node;
    }
     
    // Move the head to point to the new node
    head_ref = new_node;
    return head_ref;
}
 
// Function to find the position of
// an integer in doubly linked list
static int search(Node head_ref, int x)
{
     
    // Stores head Node
    Node temp = head_ref;
     
    // Stores position of the integer
    // in the doubly linked list
    int pos = 0;
     
    // Traverse the doubly linked list
    while (temp.data != x &&
           temp.next != null)
    {
         
        // Update pos
        pos++;
         
        // Update temp
        temp = temp.next;
    }
     
    // If the integer not present
    // in the doubly linked list
    if (temp.data != x)
        return -1;
         
    // If the integer present in
    // the doubly linked list
    return (pos + 1);
}
 
// Driver Code
public static void Main(String[] args)
{
    Node head = null;
    int X = 8;
     
    // Create the doubly linked list
    // 18 <-> 15 <-> 8 <-> 9 <-> 14
    head = push(head, 14);
    head = push(head, 9);
    head = push(head, 8);
    head = push(head, 15);
    head = push(head, 18);
     
    Console.Write(search(head, X));
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program to implement
// the above approach
 
// Structure of a node of
// the doubly linked list
class Node {
 
    constructor()
    {
         // Stores data value
         // of a node
         this.data = 0;
 
         // Stores pointer
         // to next node
         this.next = null;
 
         // Stores pointer
         // to previous node
         this.prev = null;
    }
};
 
// Function to insert a node at the
// beginning of the Doubly Linked List
function push(head_ref, new_data)
{
 
    // Allocate memory for new node
    var new_node
        = new Node();
 
    // Insert the data
    new_node.data = new_data;
 
    // Since node is added at the
    // beginning, prev is always null
    new_node.prev = null;
 
    // Link the old list to the new node
    new_node.next = (head_ref);
 
    // If pointer to head is not null
    if ((head_ref) != null) {
 
        // Change the prev of head
        // node to new node
        (head_ref).prev = new_node;
    }
 
    // Move the head to point to the new node
    (head_ref) = new_node;
 
    return head_ref;
}
 
// Function to find the position of
// an integer in doubly linked list
function search( head_ref, x)
{
 
    // Stores head Node
    var temp = head_ref;
 
    // Stores position of the integer
    // in the doubly linked list
    var pos = 0;
 
    // Traverse the doubly linked list
    while (temp.data != x
           && temp.next != null) {
 
        // Update pos
        pos++;
 
        // Update temp
        temp = temp.next;
    }
 
    // If the integer not present
    // in the doubly linked list
    if (temp.data != x)
        return -1;
 
    // If the integer present in
    // the doubly linked list
    return (pos + 1);
}
 
// Driver Code
var head = null;
var X = 8;
 
// Create the doubly linked list
// 18 <. 15 <. 8 <. 9 <. 14
head = push(head, 14);
head = push(head, 9);
head = push(head, 8);
head = push(head, 15);
head = push(head, 18);
document.write( search(head, X));
 
// This code is contributed by rrrtnx.
</script>

# Python program to implement
# the above approach
 
# Structure of a Node of
# the doubly linked list
class Node:
    def __init__(self):
        self.data = 0;
        self.next = None;
        self.prev = None;
 
# Function to insert a Node at the
# beginning of the Doubly Linked List
def push(head_ref, new_data):
 
    # Allocate memory for new Node
    new_Node = Node();
 
    # Insert the data
    new_Node.data = new_data;
 
    # Since Node is added at the
    # beginning, prev is always None
    new_Node.prev = None;
 
    # Link the old list to the new Node
    new_Node.next = head_ref;
 
    # If pointer to head is not None
    if (head_ref != None):
 
        # Change the prev of head
        # Node to new Node
        head_ref.prev = new_Node;
     
    # Move the head to point to the new Node
    head_ref = new_Node;
    return head_ref;
 
# Function to find the position of
# an integer in doubly linked list
def search(head_ref, x):
 
    # Stores head Node
    temp = head_ref;
 
    # Stores position of the integer
    # in the doubly linked list
    pos = 0;
 
    # Traverse the doubly linked list
    while (temp.data != x and temp.next != None):
        # Update pos
        pos+=1;
 
        # Update temp
        temp = temp.next;
     
    # If the integer not present
    # in the doubly linked list
    if (temp.data != x):
        return -1;
       
    # If the integer present in
    # the doubly linked list
    return (pos + 1);
 
# Driver Code
if __name__ == '__main__':
    head = None;
    X = 8;
     
    # Create the doubly linked list
    # 18 <-> 15 <-> 8 <-> 9 <-> 14
    head = push(head, 14);
    head = push(head, 9);
    head = push(head, 8);
    head = push(head, 15);
    head = push(head, 18);
    print(search(head, X));
 
# This code is contributed by Rajput-Ji

3

Complejidad temporal: O(N)
Espacio auxiliar: O(1)