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
struct Node
{
int data;
struct Node *next;
};
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(struct Node** head_ref,
int new_data)
{
// 1. Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct 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;
}
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(struct Node* prev_node,
int new_data)
{
// 1. Check if the given prev_node
// is NULL
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
// 2. Allocate new node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct 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;
}
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(struct Node** head_ref,
int new_data)
{
// 1. Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// Used in step 5
struct 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;
}
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 <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node
{
int data;
struct 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(struct Node** head_ref,
int new_data)
{
// 1. Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct 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(struct Node* prev_node,
int new_data)
{
// 1. Check if the given prev_node
// is NULL
if (prev_node == NULL)
{
printf("the given previous node cannot be NULL");
return;
}
// 2. Allocate new node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct 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(struct Node** head_ref,
int new_data)
{
// 1. Allocate node
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
// Used in step 5
struct 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 the
// linked list starting from head
void printList(struct Node *node)
{
while (node != NULL)
{
printf(" %d ", node->data);
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
struct 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);
printf("Created Linked list is: ");
printList(head);
return 0;
}
Producción:
Created Linked list is: 1 7 8 6 4
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
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