Buscar un elemento en una lista enlazada doblemente circular

Requisito previo: convertir una array en una lista circular doblemente vinculada , lista
doblemente circular dada una lista doblemente circular. La tarea es encontrar la posición de un elemento en la lista.

Representación de la imagen

Search Image

Algoritmo:  

  • Declare un puntero temporal e inicialícelo en el encabezado de la lista.
  • Repita el bucle hasta que temp llegue a la dirección de inicio (el último Node de la lista, ya que es de forma circular) y compruebe el elemento n , ya sea que esté presente o no.
  • Si está presente, levante una bandera, incremente el conteo y rompa el ciclo.
  • Por último, como el último Node aún no se ha visitado, verifique el elemento n , si está presente, en el paso 3.

El siguiente programa ilustra el enfoque anterior:  

C++

// C++ program to illustrate inserting a Node in
// a Circular Doubly Linked list in begging, end
// and middle
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a Node
struct Node
{
    int data;
    struct Node *next;
    struct Node *prev;
};
 
// Function to insert a node at the end
void insertNode(struct Node** start, int value)
{
    // If the list is empty, create a single node
    // circular and doubly list
    if (*start == NULL)
    {
        struct Node* new_node = new Node;
        new_node->data = value;
        new_node->next = new_node->prev = new_node;
        *start = new_node;
        return;
    }
 
    // If list is not empty
 
    /* Find last node */
    Node *last = (*start)->prev;
 
    // Create Node dynamically
    struct Node* new_node = new Node;
    new_node->data = value;
 
    // Start is going to be next of new_node
    new_node->next = *start;
 
    // Make new node previous of start
    (*start)->prev = new_node;
 
    // Make last previous of new node
    new_node->prev = last;
 
    // Make new node next of old last
    last->next = new_node;
}
 
// Function to display the
// circular doubly linked list
void displayList(struct Node* start)
{
    struct Node *temp = start;
 
    while (temp->next != start)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("%d ", temp->data);
}
 
// Function to search the particular element
// from the list
int searchList(struct Node* start, int search)
{
    // Declare the temp variable
    struct Node *temp = start;
      
    // Declare other control
    // variable for the searching
    int count=0,flag=0,value;
      
    // If start is NULL return -1
    if(temp == NULL)
        return -1;
    else
    {
        // Move the temp pointer until,
        // temp->next doesn't move
        // start address (Circular Fashion)
        while(temp->next != start)
        {
            // Increment count for location
            count++;
            // If it is found raise the
            // flag and break the loop
            if(temp->data == search)
            {
                flag = 1;
                count--;
                break;
            }
            // Increment temp pointer
            temp = temp->next;  
        }
        // Check whether last element in the
        // list content the value if contain,
        // raise a flag and increment count
        if(temp->data == search)
        {
            count++;
            flag = 1;
        }
          
        // If flag is true, then element
        // found, else not
        if(flag == 1)
            cout<<"\n"<<search <<" found at location "<<
                                            count<<endl;
        else
            cout<<"\n"<<search <<" not found"<<endl;
    }
}
 
// Driver code
int main()
{
    /* Start with the empty list */
    struct Node* start = NULL;
 
    // Insert 4. So linked list becomes 4->NULL
    insertNode(&start, 4);
 
    // Insert 5. So linked list becomes 4->5
    insertNode(&start, 5); 
 
    // Insert 7. So linked list
    // becomes 4->5->7
    insertNode(&start, 7);
 
    // Insert 8. So linked list
    // becomes 4->5->7->8
    insertNode(&start, 8);
 
    // Insert 6. So linked list
    // becomes 4->5->7->8->6
    insertNode(&start, 6);
 
    printf("Created circular doubly linked list is: ");
    displayList(start);
     
    searchList(start, 5);
 
    return 0;
}

Java

// Java program to illustrate inserting 
// a Node in a Circular Doubly Linked list
// in begging, end and middle
class GFG
{
     
// Structure of a Node
static class Node
{
    int data;
    Node next;
    Node prev;
};
 
// Function to insert a node at the end
static Node insertNode(Node start, int value)
{
    // If the list is empty, create a single node
    // circular and doubly list
    if (start == null)
    {
        Node new_node = new Node();
        new_node.data = value;
        new_node.next = new_node.prev = new_node;
        start = new_node;
        return new_node;
    }
 
    // If list is not empty
 
    // Find last node /
    Node last = (start).prev;
 
    // Create Node dynamically
    Node new_node = new Node();
    new_node.data = value;
 
    // Start is going to be next of new_node
    new_node.next = start;
 
    // Make new node previous of start
    (start).prev = new_node;
 
    // Make last previous of new node
    new_node.prev = last;
 
    // Make new node next of old last
    last.next = new_node;
     
    return start;
}
 
// Function to display the
// circular doubly linked list
static void displayList(Node start)
{
    Node temp = start;
 
    while (temp.next != start)
    {
        System.out.printf("%d ", temp.data);
        temp = temp.next;
    }
    System.out.printf("%d ", temp.data);
}
 
// Function to search the particular element
// from the list
static int searchList(Node start, int search)
{
    // Declare the temp variable
    Node temp = start;
     
    // Declare other control
    // variable for the searching
    int count = 0, flag = 0, value;
     
    // If start is null return -1
    if(temp == null)
        return -1;
    else
    {
        // Move the temp pointer until,
        // temp.next doesn't move
        // start address (Circular Fashion)
        while(temp.next != start)
        {
            // Increment count for location
            count++;
             
            // If it is found raise the
            // flag and break the loop
            if(temp.data == search)
            {
                flag = 1;
                count--;
                break;
            }
             
            // Increment temp pointer
            temp = temp.next;
        }
         
        // Check whether last element in the
        // list content the value if contain,
        // raise a flag and increment count
        if(temp.data == search)
        {
            count++;
            flag = 1;
        }
         
        // If flag is true, then element
        // found, else not
        if(flag == 1)
            System.out.println("\n"+search +" found at location "+
                                            count);
        else
            System.out.println("\n"+search +" not found");
    }
    return -1;
}
 
// Driver code
public static void main(String args[])
{
    // Start with the empty list /
    Node start = null;
 
    // Insert 4. So linked list becomes 4.null
    start= insertNode(start, 4);
 
    // Insert 5. So linked list becomes 4.5
    start= insertNode(start, 5);
 
    // Insert 7. So linked list
    // becomes 4.5.7
    start= insertNode(start, 7);
 
    // Insert 8. So linked list
    // becomes 4.5.7.8
    start= insertNode(start, 8);
 
    // Insert 6. So linked list
    // becomes 4.5.7.8.6
    start= insertNode(start, 6);
 
    System.out.printf("Created circular doubly linked list is: ");
    displayList(start);
     
    searchList(start, 5);
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to illustrate inserting a Node in
# a Circular Doubly Linked list in begging, end
# and middle
import math
 
# Structure of a Node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Function to insert a node at the end
def insertNode(start, value):
     
    # If the list is empty, create a single node
    # circular and doubly list
    if (start == None) :
        new_node = Node(value)
        new_node.data = value
        new_node.next = new_node
        new_node.prev = new_node
        start = new_node
        return new_node
     
    # If list is not empty
 
    # Find last node */
    last = start.prev
 
    # Create Node dynamically
    new_node = Node(value)
    new_node.data = value
 
    # Start is going to be next of new_node
    new_node.next = start
 
    # Make new node previous of start
    (start).prev = new_node
 
    # Make last previous of new node
    new_node.prev = last
 
    # Make new node next of old last
    last.next = new_node
    return start
 
# Function to display the
# circular doubly linked list
def displayList(start):
    temp = start
 
    while (temp.next != start):
        print(temp.data, end = " ")
        temp = temp.next
     
    print(temp.data)
 
# Function to search the particular element
# from the list
def searchList(start, search):
     
    # Declare the temp variable
    temp = start
     
    # Declare other control
    # variable for the searching
    count = 0
    flag = 0
    value = 0
     
    # If start is None return -1
    if(temp == None):
        return -1
    else:
         
        # Move the temp pointer until,
        # temp.next doesn't move
        # start address (Circular Fashion)
        while(temp.next != start):
             
            # Increment count for location
            count = count + 1
             
            # If it is found raise the
            # flag and break the loop
            if(temp.data == search):
                flag = 1
                count = count - 1
                break
             
            # Increment temp pointer
            temp = temp.next
         
        # Check whether last element in the
        # list content the value if contain,
        # raise a flag and increment count
        if(temp.data == search):
            count = count + 1
            flag = 1
     
        # If flag is true, then element
        # found, else not
        if(flag == 1):
            print(search,"found at location ", count)
        else:
            print(search, " not found")
     
    return -1
 
# Driver code
if __name__=='__main__':
 
    # Start with the empty list */
    start = None
 
    # Insert 4. So linked list becomes 4.None
    start = insertNode(start, 4)
 
    # Insert 5. So linked list becomes 4.5
    start = insertNode(start, 5)
 
    # Insert 7. So linked list
    # becomes 4.5.7
    start = insertNode(start, 7)
 
    # Insert 8. So linked list
    # becomes 4.5.7.8
    start = insertNode(start, 8)
 
    # Insert 6. So linked list
    # becomes 4.5.7.8.6
    start = insertNode(start, 6)
 
    print("Created circular doubly linked list is: ",
                                            end = "")
    displayList(start)
     
    searchList(start, 5)
 
# This article contributed by Srathore

C#

// C# Program to Reverse a List using Data Swapping
using System;
 
class GFG
{
     
    // Structure of a Node
    public class Node
    {
        public int data;
        public Node next;
        public Node prev;
    };
     
    // Function to insert a node at the end
    static Node insertNode(Node start, int value)
    {
        // If the list is empty, create a single node
        // circular and doubly list
        Node new_node = new Node();
        if (start == null)
        {
             
            new_node.data = value;
            new_node.next = new_node.prev = new_node;
            start = new_node;
            return new_node;
        }
     
        // If list is not empty
     
        // Find last node /
        Node last = (start).prev;
     
        // Create Node dynamically
        new_node = new Node();
        new_node.data = value;
     
        // Start is going to be next of new_node
        new_node.next = start;
     
        // Make new node previous of start
        (start).prev = new_node;
     
        // Make last previous of new node
        new_node.prev = last;
     
        // Make new node next of old last
        last.next = new_node;
         
        return start;
    }
     
    // Function to display the
    // circular doubly linked list
    static void displayList(Node start)
    {
        Node temp = start;
     
        while (temp.next != start)
        {
            Console.Write("{0} ", temp.data);
            temp = temp.next;
        }
        Console.Write("{0} ", temp.data);
    }
     
    // Function to search the particular element
    // from the list
    static int searchList(Node start, int search)
    {
        // Declare the temp variable
        Node temp = start;
         
        // Declare other control
        // variable for the searching
        int count = 0, flag = 0, value;
         
        // If start is null return -1
        if(temp == null)
            return -1;
        else
        {
            // Move the temp pointer until,
            // temp.next doesn't move
            // start address (Circular Fashion)
            while(temp.next != start)
            {
                // Increment count for location
                count++;
                 
                // If it is found raise the
                // flag and break the loop
                if(temp.data == search)
                {
                    flag = 1;
                    count--;
                    break;
                }
                 
                // Increment temp pointer
                temp = temp.next;
            }
             
            // Check whether last element in the
            // list content the value if contain,
            // raise a flag and increment count
            if(temp.data == search)
            {
                count++;
                flag = 1;
            }
             
            // If flag is true, then element
            // found, else not
            if(flag == 1)
                Console.WriteLine("\n"+search +" found at location "+
                                                count);
            else
                Console.WriteLine("\n"+search +" not found");
        }
        return -1;
    }
     
    // Driver code
    public static void Main(String []args)
    {
        // Start with the empty list /
        Node start = null;
     
        // Insert 4. So linked list becomes 4.null
        start= insertNode(start, 4);
     
        // Insert 5. So linked list becomes 4.5
        start= insertNode(start, 5);
     
        // Insert 7. So linked list
        // becomes 4.5.7
        start= insertNode(start, 7);
     
        // Insert 8. So linked list
        // becomes 4.5.7.8
        start= insertNode(start, 8);
     
        // Insert 6. So linked list
        // becomes 4.5.7.8.6
        start= insertNode(start, 6);
     
        Console.Write("Created circular doubly linked list is: ");
        displayList(start);
         
        searchList(start, 5);
    }
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript program to illustrate inserting 
// a Node in a Circular Doubly Linked list
// in begging, end and middle
 
class Node
{
    constructor()
    {
        this.data=0;
        this.next=this.prev=null;
    }
}
 
// Function to insert a node at the end
function insertNode(start,value)
{
    // If the list is empty, create a single node
    // circular and doubly list
    if (start == null)
    {
        let new_node = new Node();
        new_node.data = value;
        new_node.next = new_node.prev = new_node;
        start = new_node;
        return new_node;
    }
   
    // If list is not empty
   
    // Find last node /
    let last = (start).prev;
   
    // Create Node dynamically
    let new_node = new Node();
    new_node.data = value;
   
    // Start is going to be next of new_node
    new_node.next = start;
   
    // Make new node previous of start
    (start).prev = new_node;
   
    // Make last previous of new node
    new_node.prev = last;
   
    // Make new node next of old last
    last.next = new_node;
       
    return start;
}
 
// Function to display the
// circular doubly linked list
function displayList(start)
{
    let temp = start;
   
    while (temp.next != start)
    {
        document.write(temp.data+" ");
        temp = temp.next;
    }
    document.write(temp.data+" ");
}
 
// Function to search the particular element
// from the list
function searchList(start,search)
{
    // Declare the temp variable
    let temp = start;
       
    // Declare other control
    // variable for the searching
    let count = 0, flag = 0, value;
       
    // If start is null return -1
    if(temp == null)
        return -1;
    else
    {
        // Move the temp pointer until,
        // temp.next doesn't move
        // start address (Circular Fashion)
        while(temp.next != start)
        {
            // Increment count for location
            count++;
               
            // If it is found raise the
            // flag and break the loop
            if(temp.data == search)
            {
                flag = 1;
                count--;
                break;
            }
               
            // Increment temp pointer
            temp = temp.next;
        }
           
        // Check whether last element in the
        // list content the value if contain,
        // raise a flag and increment count
        if(temp.data == search)
        {
            count++;
            flag = 1;
        }
           
        // If flag is true, then element
        // found, else not
        if(flag == 1)
            document.write("<br>"+search +" found at location "+
                                            count);
        else
            document.write("<br>"+search +" not found");
    }
    return -1;
}
 
// Driver code
// Start with the empty list /
let start = null;
 
// Insert 4. So linked list becomes 4.null
start= insertNode(start, 4);
 
// Insert 5. So linked list becomes 4.5
start= insertNode(start, 5);
 
// Insert 7. So linked list
// becomes 4.5.7
start= insertNode(start, 7);
 
// Insert 8. So linked list
// becomes 4.5.7.8
start= insertNode(start, 8);
 
// Insert 6. So linked list
// becomes 4.5.7.8.6
start= insertNode(start, 6);
 
document.write("Created circular doubly linked list is: ");
displayList(start);
 
searchList(start, 5);
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>
Producción: 

Created circular doubly linked list is: 4 5 7 8 6 
5 found at location 2

 

Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Publicación traducida automáticamente

Artículo escrito por bilal-hungund y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *