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:
- Inicialice un puntero de Node, temp = head.
- Inicialice 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.
- De lo contrario, el elemento de impresión está presente.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python program to Search an Element
# in a Circular Linked List
# Class to define node of the linked list
class Node:
def __init__(self,data):
self.data = data;
self.next = None;
class CircularLinkedList:
# Declaring Circular Linked List
def __init__(self):
self.head = Node(None);
self.tail = Node(None);
self.head.next = self.tail;
self.tail.next = self.head;
# Adds new nodes to the Circular Linked List
def add(self,data):
# Declares a new node to be added
newNode = Node(data);
# Checks if the Circular
# Linked List is empty
if self.head.data is None:
# If list is empty then new node
# will be the first node
# to be added in the Circular Linked List
self.head = newNode;
self.tail = newNode;
newNode.next = self.head;
else:
# If a node is already present then
# tail of the last node will point to
# new node
self.tail.next = newNode;
# New node will become new tail
self.tail = newNode;
# New Tail will point to the head
self.tail.next = self.head;
# Function to search the element in the
# Circular Linked List
def findNode(self,element):
# Pointing the head to start the search
current = self.head;
i = 1;
# Declaring f = 0
f = 0;
# Check if the list is empty or not
if(self.head == None):
print("Empty list");
else:
while(True):
# Comparing the elements
# of each node to the
# element to be searched
if(current.data == element):
# If the element is present
# then incrementing f
f += 1;
break;
# Jumping to next node
current = current.next;
i = i + 1;
# If we reach the head
# again then element is not
# present in the list so
# we will break the loop
if(current == self.head):
break;
# Checking the value of f
if(f > 0):
print("element is present");
else:
print("element is not present");
# Driver Code
if __name__ == '__main__':
# Creating a Circular Linked List
'''
Circular Linked List we will be working on:
1 -> 2 -> 3 -> 4 -> 5 -> 6
'''
circularLinkedList = CircularLinkedList();
#Adding nodes to the list
circularLinkedList.add(1);
circularLinkedList.add(2);
circularLinkedList.add(3);
circularLinkedList.add(4);
circularLinkedList.add(5);
circularLinkedList.add(6);
# Searching for node 2 in the list
circularLinkedList.findNode(2);
#Searching for node in the list
circularLinkedList.findNode(7);
Producción:
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 aditya_taparia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA