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.
Java
// Linked List Class
class LinkedList
{
// Head of list
Node head;
// Node Class
class Node
{
int data;
Node next;
// Constructor to create
// a new node
Node(int d)
{
data = d;
next = null;
}
}
}
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.
Java
/* This function is in LinkedList class. Inserts a
new Node at front of the list. This method is
defined inside LinkedList class shown above */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
// 3. Make next of new Node as head
new_node.next = head;
// 4. Move the head to point to
// new Node
head = 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.
Java
/* This function is in LinkedList class.
Inserts a new node after the given
prev_node. This method is defined
inside LinkedList class shown above */
public void insertAfter(Node prev_node,
int new_data)
{
// 1. Check if the given Node is null
if (prev_node == null)
{
System.out.println(
"The given previous node cannot be null");
return;
}
/* 2. Allocate the Node &
3. Put in the data*/
Node new_node = new Node(new_data);
// 4. Make next of new Node as next
// of prev_node
new_node.next = prev_node.next;
// 5. make 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.
Java
/* Appends a new node at the end. This method is
defined inside LinkedList class shown above */
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);
/* 4. If the Linked List is empty, then
make the new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}
/* 4. This new node is going to be the
last node, so make next of it
as null */
new_node.next = null;
// 5. Else traverse till the last node
Node last = head;
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.
Java
// A complete working Java program to
// demonstrate all insertion methods
// on linked list
class LinkedList
{
// head of list
Node head;
// Linked list Node
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// Inserts a new Node at front
// of the list.
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
// 3. Make next of new Node as head
new_node.next = head;
// 4. Move the head to point to
// new Node
head = new_node;
}
// Inserts a new node after the
// given prev_node.
public void insertAfter(Node prev_node,
int new_data)
{
// 1. Check if the given Node is null
if (prev_node == null)
{
System.out.println(
"The given previous node cannot be null");
return;
}
/* 2 & 3: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
// 4. Make next of new Node as next
// of prev_node
new_node.next = prev_node.next;
// 5. make next of prev_node as
// new_node
prev_node.next = new_node;
}
/* Appends a new node at the end.
This method is defined inside
LinkedList class shown above */
public void append(int new_data)
{
/* 1. Allocate the Node &
2. Put in the data
3. Set next as null */
Node new_node = new Node(new_data);
/* 4. If the Linked List is empty,
then make the new node as head */
if (head == null)
{
head = new Node(new_data);
return;
}
/* 4. This new node is going to be
the last node, so make next
of it as null */
new_node.next = null;
// 5. Else traverse till the last node
Node last = head;
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 the
given node */
public void printList()
{
Node tnode = head;
while (tnode != null)
{
System.out.print(tnode.data + " ");
tnode = tnode.next;
}
}
// Driver code
public static void main(String[] args)
{
// Start with the empty list
LinkedList llist = new LinkedList();
// Insert 6. So linked list
// becomes 6->NUllist
llist.append(6);
// Insert 7 at the beginning.
// So linked list becomes
// 7->6->NUllist
llist.push(7);
// Insert 1 at the beginning.
// So linked list becomes
// 1->7->6->NUllist
llist.push(1);
// Insert 4 at the end.
// So linked list becomes
// 1->7->6->4->NUllist
llist.append(4);
// Insert 8, after 7. So linked
// list becomes
// 1->7->8->6->4->NUllist
llist.insertAfter(llist.head.next, 8);
System.out.println(
"Created Linked list is: ");
llist.printList();
}
}
// This code is contributed by Rajat Mishra
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