Hemos discutido la lista enlazada simple y circular en la siguiente publicación:
Lista enlazada simple Lista
enlazada circular
¿Por qué Circular? En una lista enlazada individualmente, para acceder a cualquier Node de la lista enlazada, comenzamos a atravesar desde el primer Node. Si estamos en cualquier Node en el medio de la lista, entonces no es posible acceder a los Nodes que preceden al Node dado. Este problema se puede resolver alterando ligeramente la estructura de una lista de enlaces simples. En una lista enlazada individualmente, la siguiente parte (puntero al siguiente Node) es NULL. Si utilizamos este enlace para apuntar al primer Node, entonces podemos llegar a los Nodes anteriores. Consulte esto para conocer más ventajas de las listas enlazadas circulares.
La estructura así formada es una lista circular de enlaces sencillos y se ve así:
En esta publicación, se explica la implementación e inserción de un Node en una Lista enlazada circular utilizando una lista enlazada simple.
Implementación
Para implementar una lista circular de enlaces simples, tomamos un puntero externo que apunta al último Node de la lista. Si tenemos un puntero last apuntando al último Node, last -> next apuntará al primer Node.
El puntero last apunta al Node Z y last -> next apunta al Node P.
¿Por qué hemos tomado un puntero que apunta al último Node en lugar del primer Node?
Para la inserción de un Node al principio, necesitamos recorrer toda la lista. Además, para la inserción al final, se debe recorrer toda la lista. Si en lugar de un puntero de inicio , llevamos un puntero al último Node, en ambos casos no habrá necesidad de recorrer toda la lista. Por lo tanto, la inserción al principio o al final lleva un tiempo constante, independientemente de la longitud de la lista.
Inserción
Un Node se puede agregar de tres maneras:
- Inserción en una lista vacía
- Inserción al principio de la lista
- Inserción al final de la lista
- Inserción entre los Nodes
Inserción en una Lista vacía
Inicialmente, cuando la lista está vacía, el último puntero será NULL.
Después de insertar el Node T,
Después de la inserción, T es el último Node, por lo que el último puntero apunta al Node T. Y el Node T es el primero y el último Node, por lo que T apunta a sí mismo.
Función para insertar un Node en una lista vacía,
C++
struct Node *addToEmpty(struct Node *last, int data)
{
// This function is only for empty list
if (last != NULL)
return last;
// Creating a node dynamically.
struct Node *temp =
(struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp -> next = last;
return last;
}
Java
static Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp.next = last;
return last;
}
// This code is contributed by gauravrajput1
Python3
# This function is only for empty list def addToEmpty(self, data): if (self.last != None): return self.last # Creating the newnode temp temp = Node(data) self.last = temp # Creating the link self.last.next = self.last return self.last # this code is contributed by shivanisinghss2110
C#
static Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
Node temp =
new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp.next = last;
return last;
}
// This code contributed by umadevi9616
Javascript
<script>
function addToEmpty(last , data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
var temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Note : list was empty. We link single node
// to itself.
temp.next = last;
return last;
}
// This code contributed by umadevi9616
</script>
Complejidad de tiempo: O(1)
Como tenemos que realizar un número constante de operaciones.
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
-
Inserción al principio de la lista
Para insertar un Node al principio de la lista, siga estos pasos:
1. Cree un Node, digamos T.
2. Haga T -> siguiente = último -> siguiente.
3. último -> siguiente = T.
Después de la inserción,
Función para insertar Nodes al principio de la lista,
C++
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
// Creating a node dynamically.
struct Node *temp
= (struct Node *)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = last -> next;
last -> next = temp;
return last;
}
Java
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically
Node temp = new Node();
// Assigning the data
temp.data = data;
// Adjusting the links
temp.next = last.next;
last.next = temp;
return last;
}
// This code is contributed by rutvik_56
Python3
def addBegin(self, data): if (self.last == None): return self.addToEmpty(data) temp = Node(data) temp.next = self.last.next self.last.next = temp return self.last # this code is contributed by shivanisinghss2110
C#
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically
Node temp = new Node();
// Assigning the data
temp.data = data;
// Adjusting the links
temp.next = last.next;
last.next = temp;
return last;
}
// This code is contributed by Pratham76
Javascript
<script>
function addBegin(last , data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically.
var temp = new Node();
// Assigning the data.
temp.data = data;
// Adjusting the links.
temp.next = last.next;
last.next = temp;
return last;
}
// This code contributed by Shivani
</script>
Complejidad de tiempo: O (1) para insertar el Node al principio, no es necesario recorrer la lista, lleva un tiempo constante
Complejidad espacial : O(1)
-
Inserción al final de la lista
Para insertar un Node al final de la lista, siga estos pasos:
1. Cree un Node, digamos T.
2. Haga T -> siguiente = último -> siguiente;
3. último -> siguiente = T.
4. último = T.
Después de la inserción,
Función para insertar un Node al final de la Lista
C++
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
// Creating a node dynamically.
struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
Java
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
// Adjusting the links.
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
// This code is contributed by shivanisinghss2110
Python3
def addEnd(self, data): if (self.last == None): return self.addToEmpty(data) # Assigning the data. temp = Node(data) # Adjusting the links. temp.next = self.last.next self.last.next = temp self.last = temp return self.last # This code is contributed by shivanisinghss2110
C#
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
// Adjusting the links.
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
function addEnd(last, data) {
if (last == null) return addToEmpty(last, data);
var temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
// this code is contributed by shivanisinghss2110
</script>
Análisis de complejidad:
Complejidad de tiempo: O(1) para insertar un Node al final de la lista. No es necesario recorrer la lista ya que estamos utilizando el último puntero, por lo tanto, lleva un tiempo constante.
Complejidad espacial : O(1)
- Inserción entre los Nodes
Para insertar un Node entre los dos Nodes, siga estos pasos:
1. Cree un Node, digamos T.
2. Busque el Node después del cual se debe insertar T, digamos que el Node es P.
3. Hacer T -> siguiente = P -> siguiente;
4. P -> siguiente = T.
Supongamos que se debe insertar 12 después de que el Node tenga el valor 10,
Después de buscar e insertar,
Function to insert a node at the specified position of the List,
C++
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
// Searching the item.
do
{
if (p ->data == item)
{
// Creating a node dynamically.
temp = (struct Node *)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
// Adjusting the links.
temp -> next = p -> next;
// Adding newly allocated node after p.
p -> next = temp;
// Checking for the last node.
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while (p != last -> next);
cout << item << " not present in the list." << endl;
return last;
}
Java
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do
{
if (p.data == item)
{
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while(p != last.next);
System.out.println(item + " not present in the list.");
return last;
}
// This code is contributed by shivanisinghss2110
Python3
def addAfter(self, data, item): if (self.last == None): return None temp = Node(data) p = self.last.next while p: if (p.data == item): temp.next = p.next p.next = temp if (p == self.last): self.last = temp return self.last else: return self.last p = p.next if (p == self.last.next): print(item, "not present in the list") break # This code is contributed by shivanisinghss2110
C#
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do
{
if (p.data == item)
{
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while(p != last.next);
Console.WriteLine(item + " not present in the list.");
return last;
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
function addAfter(last, data, item) {
if (last == null) return null;
var temp, p;
p = last.next;
do {
if (p.data == item) {
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last) last = temp;
return last;
}
p = p.next;
} while (p != last.next);
document.write(item + " not present in the list. <br>");
return last;
}
// This code is contributed by shivanisinghss2110
</script>
Análisis de complejidad:
Complejidad de tiempo : O(N)
Espacio Auxiliar : O(1)
El siguiente es un programa completo que utiliza todos los métodos anteriores para crear una lista circular con enlaces simples.
C++
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node *next;
};
struct Node *addToEmpty(struct Node *last, int data)
{
// This function is only for empty list
if (last != NULL)
return last;
// Creating a node dynamically.
struct Node *temp =
(struct Node*)malloc(sizeof(struct Node));
// Assigning the data.
temp -> data = data;
last = temp;
// Creating the link.
last -> next = last;
return last;
}
struct Node *addBegin(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
return last;
}
struct Node *addEnd(struct Node *last, int data)
{
if (last == NULL)
return addToEmpty(last, data);
struct Node *temp =
(struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = last -> next;
last -> next = temp;
last = temp;
return last;
}
struct Node *addAfter(struct Node *last, int data, int item)
{
if (last == NULL)
return NULL;
struct Node *temp, *p;
p = last -> next;
do
{
if (p ->data == item)
{
temp = (struct Node *)malloc(sizeof(struct Node));
temp -> data = data;
temp -> next = p -> next;
p -> next = temp;
if (p == last)
last = temp;
return last;
}
p = p -> next;
} while(p != last -> next);
cout << item << " not present in the list." << endl;
return last;
}
void traverse(struct Node *last)
{
struct Node *p;
// If list is empty, return.
if (last == NULL)
{
cout << "List is empty." << endl;
return;
}
// Pointing to first Node of the list.
p = last -> next;
// Traversing the list.
do
{
cout << p -> data << " ";
p = p -> next;
}
while(p != last->next);
}
// Driven Program
int main()
{
struct Node *last = NULL;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
return 0;
}
Java
class GFG
{
static class Node
{
int data;
Node next;
};
static Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Creating the link.
last.next = last;
return last;
}
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do
{
if (p.data == item)
{
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while(p != last.next);
System.out.println(item + " not present in the list.");
return last;
}
static void traverse(Node last)
{
Node p;
// If list is empty, return.
if (last == null)
{
System.out.println("List is empty.");
return;
}
// Pointing to first Node of the list.
p = last.next;
// Traversing the list.
do
{
System.out.print(p.data + " ");
p = p.next;
}
while(p != last.next);
}
// Driven code
public static void main(String[] args)
{
Node last = null;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
}
}
/* This code contributed by PrinciRaj1992 */
Python3
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.last = None
# This function is only for empty list
def addToEmpty(self, data):
if (self.last != None):
return self.last
# Creating the newnode temp
temp = Node(data)
self.last = temp
# Creating the link
self.last.next = self.last
return self.last
def addBegin(self, data):
if (self.last == None):
return self.addToEmpty(data)
temp = Node(data)
temp.next = self.last.next
self.last.next = temp
return self.last
def addEnd(self, data):
if (self.last == None):
return self.addToEmpty(data)
temp = Node(data)
temp.next = self.last.next
self.last.next = temp
self.last = temp
return self.last
def addAfter(self, data, item):
if (self.last == None):
return None
temp = Node(data)
p = self.last.next
while p:
if (p.data == item):
temp.next = p.next
p.next = temp
if (p == self.last):
self.last = temp
return self.last
else:
return self.last
p = p.next
if (p == self.last.next):
print(item, "not present in the list")
break
def traverse(self):
if (self.last == None):
print("List is empty")
return
temp = self.last.next
while temp:
print(temp.data, end = " ")
temp = temp.next
if temp == self.last.next:
break
# Driver Code
if __name__ == '__main__':
llist = CircularLinkedList()
last = llist.addToEmpty(6)
last = llist.addBegin(4)
last = llist.addBegin(2)
last = llist.addEnd(8)
last = llist.addEnd(12)
last = llist.addAfter(10,8)
llist.traverse()
# This code is contributed by
# Aditya Singh
C#
using System;
public class GFG
{
public class Node
{
public int data;
public Node next;
};
static Node addToEmpty(Node last, int data)
{
// This function is only for empty list
if (last != null)
return last;
// Creating a node dynamically.
Node temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Creating the link.
last.next = last;
return last;
}
static Node addBegin(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
static Node addEnd(Node last, int data)
{
if (last == null)
return addToEmpty(last, data);
Node temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
static Node addAfter(Node last, int data, int item)
{
if (last == null)
return null;
Node temp, p;
p = last.next;
do
{
if (p.data == item)
{
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last)
last = temp;
return last;
}
p = p.next;
} while(p != last.next);
Console.WriteLine(item + " not present in the list.");
return last;
}
static void traverse(Node last)
{
Node p;
// If list is empty, return.
if (last == null)
{
Console.WriteLine("List is empty.");
return;
}
// Pointing to first Node of the list.
p = last.next;
// Traversing the list.
do
{
Console.Write(p.data + " ");
p = p.next;
}
while(p != last.next);
}
// Driven code
public static void Main(String[] args)
{
Node last = null;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
function addToEmpty(last, data) {
// This function is only for empty list
if (last != null) return last;
// Creating a node dynamically.
var temp = new Node();
// Assigning the data.
temp.data = data;
last = temp;
// Creating the link.
last.next = last;
return last;
}
function addBegin(last, data) {
if (last == null) return addToEmpty(last, data);
var temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
return last;
}
function addEnd(last, data) {
if (last == null) return addToEmpty(last, data);
var temp = new Node();
temp.data = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
function addAfter(last, data, item) {
if (last == null) return null;
var temp, p;
p = last.next;
do {
if (p.data == item) {
temp = new Node();
temp.data = data;
temp.next = p.next;
p.next = temp;
if (p == last) last = temp;
return last;
}
p = p.next;
} while (p != last.next);
document.write(item + " not present in the list. <br>");
return last;
}
function traverse(last) {
var p;
// If list is empty, return.
if (last == null) {
document.write("List is empty.<br>");
return;
}
// Pointing to first Node of the list.
p = last.next;
// Traversing the list.
do {
document.write(p.data + " ");
p = p.next;
} while (p != last.next);
}
// Driven code
var last = null;
last = addToEmpty(last, 6);
last = addBegin(last, 4);
last = addBegin(last, 2);
last = addEnd(last, 8);
last = addEnd(last, 12);
last = addAfter(last, 10, 8);
traverse(last);
</script>
Producción:
2 4 6 8 10 12
Análisis de complejidad:
Complejidad de tiempo: O (N), para el código anterior necesitamos O (1) tiempo constante para insertar el Node en la primera posición y para insertar el Node en la cola o al final y entre la lista tomará O (N). por lo tanto, ignoramos las constantes, por lo que la complejidad de tiempo general es O (N) para la operación de inserción en la lista enlazada circular.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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