Hemos introducido listas enlazadas en la publicación anterior . También creamos una lista enlazada simple con 3 Nodes y discutimos el recorrido de la lista enlazada.
Todos los programas discutidos en esta publicación consideran las siguientes representaciones de la lista enlazada.
C++
// A linked list node
class Node
{
public:
int data;
Node *next;
};
// This code is contributed by rathbhupendra
En esta publicación, se analizan los métodos para insertar un nuevo Node en la lista vinculada. Un Node se puede agregar de tres maneras
1) Al principio de la lista enlazada
2) Después de un Node dado.
3) Al final de la lista enlazada.
Agregar un Node al frente: (proceso de 4 pasos)
El nuevo Node siempre se agrega antes del encabezado de la lista enlazada dada. Y el Node recién agregado se convierte en el nuevo encabezado de la lista enlazada. Por ejemplo, si la lista enlazada dada es 10->15->20->25 y agregamos un elemento 5 al frente, entonces la lista enlazada se convierte en 5->10->15->20->25. Llamemos a la función que agrega al frente de la lista push(). Push() debe recibir un puntero al puntero principal, porque push debe cambiar el puntero principal para apuntar al nuevo Node (Ver esto )
Los siguientes son los 4 pasos para agregar un Node en la parte delantera.
C++
/* Given a reference (pointer to pointer)
to the head of a list and an int,
inserts a new node on the front of
the list. */
void push(Node** head_ref,
int new_data)
{
// 1. Allocate node
Node* new_node = new Node();
// 2. Put in the data
new_node->data = new_data;
// 3. Make next of new node
// as head
new_node->next = (*head_ref);
// 4. Move the head to point to
// the new node
(*head_ref) = new_node;
}
// This code is contributed by rathbhupendra
La complejidad temporal de push() es O(1) ya que realiza una cantidad constante de trabajo.
Agregar un Node después de un Node dado: (proceso de 5 pasos)
Se nos da un puntero a un Node y el nuevo Node se inserta después del Node dado.
C++
// Given a node prev_node, insert a
// new node after the given prev_node
void insertAfter(Node* prev_node, int new_data)
{
// 1. Check if the given prev_node
// is NULL
if (prev_node == NULL)
{
cout << "the given previous node cannot be NULL";
return;
}
// 2. Allocate new node
Node* new_node = new Node();
// 3. Put in the data
new_node->data = new_data;
// 4. Make next of new node as
// next of prev_node
new_node->next = prev_node->next;
// 5. move the next of prev_node
// as new_node
prev_node->next = new_node;
}
// This code is contributed by anmolgautam818
La complejidad temporal de insertAfter() es O(1) ya que realiza una cantidad constante de trabajo.
Agregar un Node al final: (proceso de 6 pasos)
El nuevo Node siempre se agrega después del último Node de la lista enlazada dada. Por ejemplo, si la lista enlazada dada es 5->10->15->20->25 y agregamos un elemento 30 al final, entonces la lista enlazada se convierte en 5->10->15->20->25- >30.
Dado que una lista enlazada suele estar representada por el encabezado de la misma, tenemos que recorrer la lista hasta el final y luego cambiar el penúltimo Node a un nuevo Node.
Los siguientes son los 6 pasos para agregar un Node al final.
C++
// Given a reference (pointer to pointer) to
// the head of a list and an int, appends a
// new node at the end
void append(Node** head_ref, int new_data)
{
// 1. Allocate node
Node* new_node = new Node();
// Used in step 5
Node *last = *head_ref;
// 2. Put in the data
new_node->data = new_data;
// 3. This new node is going to be
// the last node, so make next of
// it as NULL
new_node->next = NULL;
// 4. If the Linked List is empty,
// then make the new node as head
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
// 5. Else traverse till the last node
while (last->next != NULL)
last = last->next;
// 6. Change the next of last node
last->next = new_node;
return;
}
// This code is contributed by anmolgautam818
La complejidad temporal de agregar es O(n) donde n es el número de Nodes en la lista enlazada. Dado que hay un ciclo de principio a fin, la función funciona como O(n).
Este método también se puede optimizar para que funcione en O(1) manteniendo un puntero adicional al final de la lista enlazada/
El siguiente es un programa completo que utiliza todos los métodos anteriores para crear una lista enlazada.
C++
// A complete working C++ program to demonstrate
// all insertion methods on Linked List
#include <bits/stdc++.h>
using namespace std;
// A linked list node
class Node
{
public:
int data;
Node *next;
};
/* Given a reference (pointer to pointer)
to the head of a list and an int, inserts
a new node on the front of the list. */
void push(Node** head_ref, int new_data)
{
// 1. Allocate node
Node* new_node = new Node();
// 2. Put in the data
new_node->data = new_data;
// 3. Make next of new node as head
new_node->next = (*head_ref);
// 4. Move the head to point to the
// new node
(*head_ref) = new_node;
}
/* Given a node prev_node, insert a new
node after the given prev_node */
void insertAfter(Node* prev_node,
int new_data)
{
/* 1. Check if the given prev_node
is NULL */
if (prev_node == NULL)
{
cout << "the given previous node cannot be NULL";
return;
}
// 2. Allocate new node
Node* new_node = new Node();
// 3. Put in the data
new_node->data = new_data;
// 4. Make next of new node as next
// of prev_node
new_node->next = prev_node->next;
// 5. Move the next of prev_node
// as new_node
prev_node->next = new_node;
}
/* Given a reference (pointer to pointer)
to the head of a list and an int,
appends a new node at the end */
void append(Node** head_ref,
int new_data)
{
// 1. Allocate node
Node* new_node = new Node();
// Used in step 5
Node *last = *head_ref;
// 2. Put in the data
new_node->data = new_data;
/* 3. This new node is going to be
the last node, so make next of
it as NULL */
new_node->next = NULL;
/* 4. If the Linked List is empty,
then make the new node as head */
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
// 5. Else traverse till the
// last node
while (last->next != NULL)
last = last->next;
// 6. Change the next of last node
last->next = new_node;
return;
}
// This function prints contents of
// linked list starting from head
void printList(Node *node)
{
while (node != NULL)
{
cout<<" "<<node->data;
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
// Insert 6. So linked list
// becomes 6->NULL
append(&head, 6);
// Insert 7 at the beginning.
// So linked list becomes
// 7->6->NULL
push(&head, 7);
// Insert 1 at the beginning.
// So linked list becomes
// 1->7->6->NULL
push(&head, 1);
// Insert 4 at the end. So
// linked list becomes
// 1->7->6->4->NULL
append(&head, 4);
// Insert 8, after 7. So linked
// list becomes 1->7->8->6->4->NULL
insertAfter(head->next, 8);
cout << "Created Linked list is: ";
printList(head);
return 0;
}
// This code is contributed by rathbhupendra
Producción:
Created Linked list is: 1 7 8 6 4
Consulte el artículo completo en Lista vinculada | ¡ Establezca 2 (Inserción de un Node) para obtener más detalles!
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