Hemos discutido la introducción y las aplicaciones de la lista circular enlazada,en la publicación anterior sobre Lista enlazada circular. En esta publicación, se discute la operación transversal.
En una lista enlazada convencional, recorremos la lista desde el Node principal y detenemos el recorrido cuando llegamos a NULL. En una lista enlazada circular, detenemos el recorrido cuando llegamos nuevamente al primer Node. A continuación se muestra el código C para el recorrido de la lista enlazada.
C++
/* Function to print nodes in
a given Circular linked list */
void printList(Node* head)
{
Node* temp = head;
// If linked list is not empty
if (head != NULL) {
// Print nodes till we reach first node again
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
}
C
/* Function to traverse a given Circular linked list and print nodes */
void printList(struct Node *first)
{
struct Node *temp = first;
// If linked list is not empty
if (first != NULL)
{
// Keep printing nodes till we reach the first node again
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != first);
}
}
Java
/* Function to print nodes in a
given Circular linked list */
static void printList(Node head)
{
Node temp = head;
// If linked list is not empty
if (head != null)
{
// Keep printing nodes till we reach the first node
// again
do
{
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
// This code is contributed by pratham76.
Python3
# Function to print nodes in a given Circular linked list def printList(self): temp = self.head # If linked list is not empty if self.head is not None: while(True): # Print nodes till we reach first node again print(temp.data, end=" ") temp = temp.next if (temp == self.head): break
C#
/* Function to print nodes in a
given Circular linked list */
static void printList(Node head)
{
Node temp = head;
// If linked list is not empty
if (head != null) {
// Keep printing nodes till we reach the first node
// again
do {
Console.Write(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
//This code is contributed by rutvik_56
Javascript
<script>
/* Function to print nodes in a
given Circular linked list */
function printList(head)
{
var temp = head;
// If linked list is not empty
if (head != null)
{
// Keep printing nodes till we reach the first node
// again
do
{
document.write(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
// This code contributed by umadevi9616
</script>
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Programa completo para demostrar el recorrido. Los siguientes son programas completos para demostrar el recorrido de una lista enlazada circular.
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
/* structure for a node */
class Node
{
public:
int data;
Node *next;
};
/* Function to insert a node at the beginning
of a Circular linked list */
void push(Node **head_ref, int data)
{
Node *ptr1 = new Node();
Node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
/* If linked list is not NULL then
set the next of last node */
if (*head_ref != NULL)
{
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
/* Function to print nodes in
a given Circular linked list */
void printList(Node *head)
{
Node *temp = head;
if (head != NULL)
{
do
{
cout << temp->data << " ";
temp = temp->next;
}
while (temp != head);
}
}
/* Driver program to test above functions */
int main()
{
/* Initialize lists as empty */
Node *head = NULL;
/* Created linked list will be 11->2->56->12 */
push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);
cout << "Contents of Circular Linked List\n ";
printList(head);
return 0;
}
C
// C program to implement
// the above approach
#include<stdio.h>
#include<stdlib.h>
/* structure for a node */
struct Node
{
int data;
struct Node *next;
};
/* Function to insert a node at the beginning of a Circular
linked list */
void push(struct Node **head_ref, int data)
{
struct Node *ptr1 = (struct Node *)malloc(sizeof(struct Node));
struct Node *temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
/* If linked list is not NULL then set the next of last node */
if (*head_ref != NULL)
{
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1; /*For the first node */
*head_ref = ptr1;
}
/* Function to print nodes in a given Circular linked list */
void printList(struct Node *head)
{
struct Node *temp = head;
if (head != NULL)
{
do
{
printf("%d ", temp->data);
temp = temp->next;
}
while (temp != head);
}
}
/* Driver program to test above functions */
int main()
{
/* Initialize lists as empty */
struct Node *head = NULL;
/* Created linked list will be 11->2->56->12 */
push(&head, 12);
push(&head, 56);
push(&head, 2);
push(&head, 11);
printf("Contents of Circular Linked List\n ");
printList(head);
return 0;
}
Java
// Java program to implement
// the above approach
class GFG {
// node
static class Node {
int data;
Node next;
};
/* Function to insert a node
at the beginning of a Circular
linked list */
static Node push(Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
/* If linked list is not null
then set the next of last node */
if (head_ref != null) {
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
/* Function to print nodes in a
given Circular linked list */
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
}
// Driver Code
public static void main(String args[])
{
/* Initialize lists as empty */
Node head = null;
/* Created linked list will
be 11.2.56.12 */
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
System.out.println("Contents of Circular "
+ "Linked List:");
printList(head);
}
}
Python3
# Python program to demonstrate
# circular linked list traversal
# Structure for a Node
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
# Constructor to create a empty circular linked list
def __init__(self):
self.head = None
# Function to insert a node at the beginning of a
# circular linked list
def push(self, data):
ptr1 = Node(data)
temp = self.head
ptr1.next = self.head
# If linked list is not None then set the next of
# last node
if self.head is not None:
while(temp.next != self.head):
temp = temp.next
temp.next = ptr1
else:
ptr1.next = ptr1 # For the first node
self.head = ptr1
# Function to print nodes in a given circular linked list
def printList(self):
temp = self.head
if self.head is not None:
while(True):
print (temp.data, end=" ")
temp = temp.next
if (temp == self.head):
break
# Driver program to test above function
# Initialize list as empty
cllist = CircularLinkedList()
# Created linked list will be 11->2->56->12
cllist.push(12)
cllist.push(56)
cllist.push(2)
cllist.push(11)
print ("Contents of circular Linked List")
cllist.printList()
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// node
class Node
{
public int data;
public Node next;
};
/* Function to insert a node
at the beginning of a Circular
linked list */
static Node push(Node head_ref,
int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
/* If linked list is not null
then set the next of last node */
if (head_ref != null)
{
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
/* Function to print nodes in a
given Circular linked list */
static void printList(Node head)
{
Node temp = head;
if (head != null)
{
do
{
Console.Write(temp.data + " ");
temp = temp.next;
}
while (temp != head);
}
}
// Driver Code
static public void Main(String []args)
{
/* Initialize lists as empty */
Node head = null;
/* Created linked list will
be 11.2.56.12 */
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
Console.WriteLine("Contents of Circular " +
"Linked List:");
printList(head);
}
}
Javascript
<script>
// JavaScript program to implement
// the above approach
// node
class Node
{
constructor(data)
{
this.data=data;
this.next=null;
}
}
/* Function to insert a node
at the beginning of a Circular
linked list */
function push(head_ref, data)
{
let ptr1 = new Node();
let temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
/* If linked list is not null
then set the next of last node */
if (head_ref != null)
{
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
/* Function to print nodes in a
given Circular linked list */
function printList(head)
{
let temp = head;
if (head != null)
{
do
{
document.write(temp.data + " ");
temp = temp.next;
}
while (temp != head);
}
}
// Driver Code
/* Initialize lists as empty */
let head = null;
/* Created linked list will
be 11.2.56.12 */
head = push(head, 12);
head = push(head, 56);
head = push(head, 2);
head = push(head, 11);
document.write("Contents of Circular " +
"Linked List:<br>");
printList(head);
</script>
Producción:
Contents of Circular Linked List 11 2 56 12
Complejidad de tiempo: O(n) Como necesitamos movernos a través de toda la lista, Espacio auxiliar: O(1) Como no se usa espacio extra
Programa completo para recorrer una lista enlazada circular usando recursividad: El programa para recorrer una lista enlazada usando recursividad es el siguiente:
Python3
class Node(object):
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def push(self, data, temp=None):
if self.head == None:
node = Node(data)
self.head = node
node.next = self.head
return
if temp == None:
temp = self.head
if temp.next == self.head:
node = Node(data)
node.next = self.head
temp.next = node
return
self.push(data, temp.next)
def traverse(self, temp=None):
if temp == None:
temp = self.head
if temp.next == self.head:
print(temp.data, end="\n")
return
print(temp.data, end="-->")
self.traverse(temp.next)
if __name__ == "__main__":
clist = CircularLinkedList()
clist.push(2)
clist.push(3)
clist.push(7)
clist.push(5)
print("Traversed Circular Linked List: ", end="\n")
clist.traverse()
Producción
Traversed Circular Linked List: 2-->3-->7-->5
Complejidad de Tiempo: O(n), Espacio Auxiliar: O(1)
Es posible que desee ver las siguientes publicaciones en la Lista enlazada circular
Dividir una lista enlazada circular en dos mitades
Insertar ordenado para lista enlazada circular
Pronto discutiremos la implementación de operaciones de inserción y eliminación para listas enlazadas circulares.
Escriba comentarios si encuentra algún error en el código/algoritmo anterior, o encuentre otras formas de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA