Programa Javascript para insertar un Node en una lista vinculada

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. 

<script>
// Linked List Class
 
// Head of list
var head;
 
// Node Class
class Node
{
    // Constructor to create
    // a new node
    constructor(d)
    {
            this.data = d;
            this.next = null;
        }
    }
// This code is contributed by todaysgaurav
</script>

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.

<script>
/* This function is in LinkedList class.
   Inserts a new Node at front of the list.
   This method is defined inside LinkedList
   class shown above */  
 function push(new_data)
{
    /* 1 & 2: Allocate the Node &
              Put in the data*/
    var new_node = new Node(new_data);
 
    // Make next of new Node as head
    new_node.next = head;
 
    // 4. Move the head to point to new Node
    head = new_node;
}
// This code is contributed by Rajput-Ji
</script>

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.

<script>
/* This function is in LinkedList class.
   Inserts a new node after the given prev_node.
   This method is defined inside LinkedList
   class shown above */
function insertAfter(prev_node , new_data)
{
    // 1. Check if the given Node is null
    if (prev_node == null)
    {
        document.write(
                 "The given previous node cannot be null");
        return;
    }
 
    /* 2. Allocate the Node &
       3. Put in the data*/
    var 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;
}
// This code is contributed by aashish1995
</script>

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.

<script>
/* Appends a new node at the end. This method is
   defined inside LinkedList class shown above */
 function append(new_data)
{
    /* 1. Allocate the Node &
       2. Put in the data
       3. Set next as null */
    var 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
    var last = head;
    while (last.next != null)
        last = last.next;
 
    // 6. Change the next of last node
    last.next = new_node;
    return;
}
// This code is contributed by aashish1995
</script>

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.

<script>
// A complete working javascript program
// to demonstrate all insertion methods
// on linked list
 
// Head of list
var head;
 
// Linked list Node
class Node
{
    constructor(val)
    {
        this.data = val;
        this.next = null;
    }
}
 
// Inserts a new Node at front
// of the list.
function push(new_data)
{
    /* 1 & 2: Allocate the Node &
              Put in the data */
        var 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.
function insertAfter(prev_node,
                     new_data)
{
    // 1. Check if the given Node is null
    if (prev_node == null)
    {
        document.write(
                 "The given previous node cannot be null");
        return;
    }
 
    /* 2 & 3: Allocate the Node &
              Put in the data */
    var 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 */
function append(new_data)
{
    /* 1. Allocate the Node &
       2. Put in the data
       3. Set next as null */
    var 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
    var 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 */
function printList()
{
    var tnode = head;
    while (tnode != null)
    {
        document.write(tnode.data + " ");
        tnode = tnode.next;
    }
}
 
// Driver code
 
// Start with the empty list
 
// Insert 6. So linked list becomes
// 6->NUllist
append(6);
 
// Insert 7 at the beginning. So
// linked list becomes 7->6->NUllist
push(7);
 
// Insert 1 at the beginning. So
// linked list becomes 1->7->6->NUllist
push(1);
 
// Insert 4 at the end. So linked list
// becomes 1->7->6->4->NUllist
append(4);
 
// Insert 8, after 7. So linked list
// becomes 1->7->8->6->4->NUllist
insertAfter(head.next, 8);
 
document.write(
         "Created Linked list is: ");
printList();
// This code is contributed by gauravrajput1
</script>

Producción:

 Created Linked list is:  1  7  8  6  4

Complejidad de tiempo: O(N) donde N es ninguno de los Nodes en la lista enlazada

Consulte el artículo completo en Lista vinculada | ¡ Establezca 2 (Inserción de un Node) para obtener más detalles!