Agregue un nodo en una lista vinculada en C ++

Una lista vinculada es una estructura de datos que almacena una colección de nodos, donde cada nodo almacena un valor de datos y un puntero al siguiente nodo en la lista. A diferencia de las matrices, las listas vinculadas pueden crecer y reducirse dinámicamente, lo que facilita trabajar con datos que cambian constantemente. La inserción de la lista vinculada es el proceso de agregar un nuevo nodo a una lista vinculada.

En C ++, podemos insertar un nuevo nodo en una lista vinculada de tres maneras:

1. Al comienzo de la lista vinculada
2. Al final de la lista vinculada
3. Después de un nodo dado en la lista vinculada

Hablemos sobre cómo hacer cada uno de los métodos de inserción de la lista vinculada uno por uno.

Al comienzo de la lista vinculada

Para agregar cualquier nodo al inicio de la lista vinculada, tenemos que seguir estos pasos:

1. Crear un nuevo nodo.
2. La dirección de encabezado de la lista vinculada se da al nuevo puntero de nodo para que pueda comenzar a señalar el nodo del encabezado que ya existe.
3. Asigne la nueva dirección de nodo al encabezado.

El siguiente sería nulo si este nuevo nodo es el primer nodo en la lista vinculada.

Al final de la lista vinculada

Para agregar cualquier nodo al final de la lista vinculada, tenemos que seguir estos pasos:

1. Crear un nuevo nodo.
2. Visite la lista vinculada hasta que llegamos al final de la lista vinculada.
3. Asigne el nodo recién creado de la dirección del puntero de la lista vinculada al último nodo de la dirección de puntero de la lista vinculada para que pueda comenzar a señalar el nodo recién creado.
4. Al final, agregue un puntero nulo al nodo recién creado de la lista vinculada ya que ahora es el último nodo.

Después de un nodo dado en la lista vinculada

Para agregar cualquier nodo en la enésima posición de la lista vinculada, tenemos que seguir estos pasos:

1. Crear un nuevo nodo.
2. Verifique si la posición deseada del usuario para el nuevo nodo es válida; es decir, si la posición del nuevo nodo es mayor o menor que el tamaño de la lista vinculada.
3. Visite la lista vinculada a la décima posición de la lista vinculada.
4. Asigne el enésimo puntero Next al recién creado puntero Next.
5. Asigne la nueva dirección de nodo al enésimo puntero siguiente para que pueda comenzar a señalar el nuevo nodo.

Implementación del programa C ++ para la inserción del nodo en la lista vinculada:

// Complete el programa para la inserción en una lista vinculada en C++
#incluir
usando el espacio de nombres STD;
nodo de clase

público:
datos int;
Nodo *siguiente;
;
void insertAtBeginningLinkedList (nodo ** headNode, int data)
// crear dinámicamente memoria para este nuevonode
Nodo* newnode = new Node ();
newnode-> data = data;
newnode-> next = *headNode;
*headNode = newnode;
cout << newNode->datos << " inserted data successfully"
"En la lista vinculada" << endl;

void insertAtLastLinkedList (nodo ** headNode, int data)
Nodo* newnode = new Node ();
newnode-> data = data;
// El último nodo siempre apunta a NULL
newnode-> next = null;
// Si la lista vinculada estaba vacía
if (*headNode == null)
*headNode = newnode;
cout << newNode->datos << " inserted data successfully"
"En la lista vinculada" << endl;
devolver;

Nodo * tempnode = * headNode;
// llegar al último nodo de la lista vinculada
while (tempnode-> Siguiente!= Nulo)
tempnode = tempnode-> next;
// Asignar Newnode al siguiente nodo
tempnode-> next = newnode;
cout << newNode->datos tamaño ++;

tamaño de retorno;

void insertAfternthnodelinkedlist
(int n, int data, nodo ** HeadNode)

int loc = n;
int size = longitudOfLinkedList (*headNode);
// No se permiten insertos de posición negativa
// La inserción no es posible si la ubicación es más grande
// que el tamaño de la lista vinculada.
if (n < 0 || n > tamaño)
cout << "Insert position not valid";
if (n == 0)
insertAtBeginningLinkedList (HeadNode, Data);

demás
Nodo* newnode = new Node ();
newnode-> data = data;
newnode-> next = null;
// usó tempnode para iterar a través de la lista vinculada
Nodo * tempnode = * headNode;
// atraviesa hasta llegar al enésimo nodo
mientras (-n)
tempnode = tempnode-> next;
// al siguiente nodo en el enésimo nodo, asigne el siguiente.
newnode-> next = tempnode-> next;
// Asignar enésimo nodo al lado de este nuevo nodo
tempnode-> next = newnode;
// Newnode insertado
cout << newNode->datos << " inserted data after index " <

void printLinkedList (nodo* nodo)
cout << "\n";
// mientras que la condición se detendrá cuando nodo == nulo
mientras (nodo!= Nulo)
cout << node->datos << " "; node = node->próximo;

cout << "\n" << endl;

int main ()

Nodo* headNode = null;
insertAtBeginningLinkedList (y HeadNode, 10);
insertAtBeginningLinkedList (y HeadNode, 9);
insertAtBeginningLinkedList (& HeadNode, 8);
printLinkedList (nodo de cabeza);
InsertAtLastLinkedList (& HeadNode, 11);
InsertAtLastLinkedList (& HeadNode, 12);
InsertAtLastLinkedList (& HeadNode, 14);
printLinkedList (nodo de cabeza);
// inserta datos en la posición particular
insertAfternthNodElinkedList (5, 17 y HeadNode);
insertAfternThnodElinkedList (1, 11 y HeadNode);
printLinkedList (nodo de cabeza);
regresar 0;

Producción:

10 datos insertados con éxito en la lista vinculada
9 datos insertados con éxito en la lista vinculada
8 datos insertados con éxito en la lista vinculada
8 9 10
11 datos insertados al final
12 datos insertados al final
14 datos insertados al final
8 9 10 11 12 14
17 Datos insertados después del índice 5
11 datos insertados después del índice 1
8 11 9 10 11 12 17 14

Explicación:

El código define un nodo con nombre de clase que tiene dos propiedades: (1) datos (de tipo int) para almacenar el valor del nodo, y (2) siguiente (de nodo de tipo*) para almacenar el puntero al siguiente nodo en la lista.

El programa implementa tres funciones para insertar los nodos en la lista vinculada:

• insertatbeginninglinkedlist: Inserta un nodo al comienzo de la lista vinculada.
• InsertAtlastLinkedList: Inserta un nodo al final de la lista vinculada.
• InsertAfternThnodelinkedList: Inserta un nodo después del enésimo nodo de la lista vinculada.

Un datos enteros y un doble puntero al nodo principal de la lista vinculada se pasan a la función InsertATBeginningLinkedList (). Usando el nuevo nodo (), la memoria de un nuevo nodo se crea dinámicamente y los datos se asignan al nuevo nodo. Más tarde, actualiza el nodo principal para que sea el nuevo nodo configurando el siguiente puntero del nuevo nodo en el nodo anterior anterior.

Un datos enteros y un doble puntero al nodo principal de la lista vinculada se pasan al método InsertAtLastLinkedList (). Usando el nuevo nodo (), la memoria de un nuevo nodo se crea dinámicamente y los datos se asignan al nuevo nodo. El siguiente puntero del nuevo nodo se establece en NULL. Si la lista vinculada está vacía, el nodo principal se actualiza para servir como el nuevo nodo. En cualquier otro caso, atraviesa la lista vinculada hasta que alcanza el último nodo, momento en el que establece el nuevo nodo al siguiente puntero del último nodo.

La función InsertAfternThnodeLinkedList () agrega un nuevo nodo con los datos dados después del nodo nth en una lista vinculada. La lista vinculada y su tamaño, así como la posición n y los datos que se insertarán, se pasan como argumentos. Primero, la función verifica si la ubicación n es correcta (i.mi., no negativo y no más grande que el tamaño de la lista vinculada). Se imprimen los mensajes de error si la posición no es válida. Si la posición es válida, la función construye un nuevo nodo, establece sus datos y los siguientes campos, y luego busca iterativamente a través de la lista vinculada para encontrar el enésimo nodo. Luego, vincula el enésimo nodo y el nuevo nodo cambiando los siguientes punteros del enésimo nodo y el nuevo nodo.

La longitud de la lista vinculada se devuelve mediante la función LongOfLinkedList () que acepta un puntero al nodo Head de la lista vinculada. Esto se logra en bucle alrededor de la lista vinculada, contando los nodos y devolviendo el recuento.

En el método principal, el programa crea una lista vinculada vacía, luego llama a los tres métodos de inserción con diversos datos y entradas de posición. Finalmente, imprime la lista vinculada para ver los resultados.

Conclusión

Dependiendo de dónde se realice una inserción en una lista vinculada, hay varios problemas de complejidad temporal y espacial. Como una operación extremadamente efectiva, la inserción al comienzo de la lista tiene una complejidad de tiempo constante de O (1) y una complejidad espacial constante de O (1). En el peor escenario, insertar al final de la lista lleva el tiempo lineal o (n), donde n es el número total de entradas de la lista. Esto es para que podamos descubrir el nodo de cola atravesando la lista. En el peor de los casos, insertar en una posición específica en la lista también lleva tiempo lineal, que es o (n), porque tenemos que pasar por la lista para encontrar el nodo en la posición específica. No importa cómo se agregan, las listas vinculadas son una forma flexible y dinámica de almacenar los datos que se pueden usar de muchas maneras diferentes.