Una lista enlazada es un tipo de estructura de datos lineal donde cada Node tiene una parte de datos y una parte de dirección que apunta al siguiente Node. Una lista enlazada circular es un tipo de lista enlazada donde el último Node apunta al primero, formando un círculo de Nodes. Ejemplo:
Input : CList = 6->5->4->3->2, find = 3 Output: Element is present Input : CList = 6->5->4->3->2, find = 1 Output: Element is not present
Buscar un elemento en una lista enlazada circular
Por ejemplo, si la clave a buscar es 30 y la lista enlazada es 5->4->3->2, entonces la función debería devolver falso. Si la clave a buscar es 4, entonces la función debería devolver verdadero.
Acercarse:
- Inicializa un puntero de Node, temp = head
- Inicializar un contador f=0 (para verificar si el elemento está presente en una lista enlazada o no)
- Si el encabezado es nulo, la lista de impresión está vacía
- De lo contrario, comience a recorrer la Lista vinculada y, si el elemento se encuentra en la Lista vinculada, incremente en f.
- Si el contador es cero, entonces no se encuentra el elemento de impresión
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program to Search an Element
// in a Circular Linked List
public class search {
class Node {
int data;
Node next;
public Node(int data) { this.data = data; }
}
// declaring head pointer as null
public Node head = null;
public Node tempo = null;
// function adds new nodes at the end of list
public void addNode(int data)
{
Node new1 = new Node(data);
// If linked list is empty
if (head == null) {
head = new1;
}
else {
tempo.next = new1;
}
tempo = new1;
// last node points to first node
tempo.next = head;
}
public void find(int key)
{
// temp will traverse the circular
// linked list for searching element
Node temp = head;
// counter used to check if
// element is found or not
int f = 0;
if (head == null) {
System.out.println("List is empty");
}
else {
do {
if (temp.data == key) {
System.out.println(
"element is present");
f = 1;
break;
}
temp = temp.next;
} while (temp != head);
if (f == 0) {
System.out.println(
"element is not present");
}
}
}
public static void main(String[] args)
{
search s = new search();
// Adds data to the list
s.addNode(5);
s.addNode(4);
s.addNode(3);
s.addNode(2);
// Search for node 2 in the list
s.find(2);
// Search for node 6 in the list
s.find(6);
}
}
element is present element is not present
Complejidad temporal: O(N), donde N es la longitud de la lista enlazada circular.
Publicación traducida automáticamente
Artículo escrito por pradiptamukherjee y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA