Una lista doblemente enlazada es una lista enlazada que consta de un conjunto de registros enlazados secuencialmente llamados Nodes. Cada Node contiene dos campos que son referencias al Node anterior y al siguiente en la secuencia de Nodes.
La tarea es crear una lista doblemente enlazada insertando Nodes de modo que la lista permanezca en orden ascendente al imprimirse de izquierda a derecha. Además, necesitamos mantener dos punteros, head (apunta al primer Node) y tail (apunta al último Node).
Ejemplos:
Input : 40 50 10 45 90 100 95 Output :10 40 45 50 90 95 100 Input : 30 10 50 43 56 12 Output :10 12 30 43 50 56
Algoritmo:
la tarea se puede lograr como:
- Si la lista Vinculada está vacía, haga que los punteros izquierdo y derecho apunten al Node que se insertará y haga que su campo anterior y siguiente apunten a NULL.
- Si el Node que se va a insertar tiene un valor menor que el valor del primer Node de la lista vinculada, conecte ese Node desde el campo anterior del primer Node.
- Si el Node que se va a insertar tiene un valor mayor que el valor del último Node de la lista vinculada, conecte ese Node desde el siguiente campo del último Node.
- Si el Node que se va a insertar tiene un valor entre el valor del primer y el último Node, compruebe la posición adecuada y realice las conexiones.
C++
/* C++ program to insetail nodes in doubly
linked list such that list remains in
ascending order on printing from left
to right */
#include <bits/stdc++.h>
using namespace std;
// A linked list node
class Node
{
public:
Node *prev;
int info;
Node *next;
};
// Function to insetail new node
void nodeInsetail(Node **head,
Node **tail,
int key)
{
Node *p = new Node();
p->info = key;
p->next = NULL;
// If first node to be insetailed in doubly
// linked list
if ((*head) == NULL)
{
(*head) = p;
(*tail) = p;
(*head)->prev = NULL;
return;
}
// If node to be insetailed has value less
// than first node
if ((p->info) < ((*head)->info))
{
p->prev = NULL;
(*head)->prev = p;
p->next = (*head);
(*head) = p;
return;
}
// If node to be insetailed has value more
// than last node
if ((p->info) > ((*tail)->info))
{
p->prev = (*tail);
(*tail)->next = p;
(*tail) = p;
return;
}
// Find the node before which we need to
// insert p.
Node *temp = (*head)->next;
while ((temp->info) < (p->info))
temp = temp->next;
// Insert new node before temp
(temp->prev)->next = p;
p->prev = temp->prev;
temp->prev = p;
p->next = temp;
}
// Function to print nodes in from left to right
void printList(Node *temp)
{
while (temp != NULL)
{
cout << temp->info << " ";
temp = temp->next;
}
}
// Driver program to test above functions
int main()
{
Node *left = NULL, *right = NULL;
nodeInsetail(&left, &right, 30);
nodeInsetail(&left, &right, 50);
nodeInsetail(&left, &right, 90);
nodeInsetail(&left, &right, 10);
nodeInsetail(&left, &right, 40);
nodeInsetail(&left, &right, 110);
nodeInsetail(&left, &right, 60);
nodeInsetail(&left, &right, 95);
nodeInsetail(&left, &right, 23);
cout<<"Doubly linked list on printing"
" from left to right\n";
printList(left);
return 0;
}
// This is code is contributed by rathbhupendra
C
/* C program to insetail nodes in doubly
linked list such that list remains in
ascending order on printing from left
to right */
#include<stdio.h>
#include<stdlib.h>
// A linked list node
struct Node
{
struct Node *prev;
int info;
struct Node *next;
};
// Function to insetail new node
void nodeInsetail(struct Node **head,
struct Node **tail,
int key)
{
struct Node *p = new Node;
p->info = key;
p->next = NULL;
// If first node to be insetailed in doubly
// linked list
if ((*head) == NULL)
{
(*head) = p;
(*tail) = p;
(*head)->prev = NULL;
return;
}
// If node to be insetailed has value less
// than first node
if ((p->info) < ((*head)->info))
{
p->prev = NULL;
(*head)->prev = p;
p->next = (*head);
(*head) = p;
return;
}
// If node to be insetailed has value more
// than last node
if ((p->info) > ((*tail)->info))
{
p->prev = (*tail);
(*tail)->next = p;
(*tail) = p;
return;
}
// Find the node before which we need to
// insert p.
temp = (*head)->next;
while ((temp->info) < (p->info))
temp = temp->next;
// Insert new node before temp
(temp->prev)->next = p;
p->prev = temp->prev;
temp->prev = p;
p->next = temp;
}
// Function to print nodes in from left to right
void printList(struct Node *temp)
{
while (temp != NULL)
{
printf("%d ", temp->info);
temp = temp->next;
}
}
// Driver program to test above functions
int main()
{
struct Node *left = NULL, *right = NULL;
nodeInsetail(&left, &right, 30);
nodeInsetail(&left, &right, 50);
nodeInsetail(&left, &right, 90);
nodeInsetail(&left, &right, 10);
nodeInsetail(&left, &right, 40);
nodeInsetail(&left, &right, 110);
nodeInsetail(&left, &right, 60);
nodeInsetail(&left, &right, 95);
nodeInsetail(&left, &right, 23);
printf("\nDoubly linked list on printing"
" from left to right\n");
printList(left);
return 0;
}
Java
/* Java program to insetail nodes in doubly
linked list such that list remains in
ascending order on printing from left
to right */
import java.io.*;
import java.util.*;
// A linked list node
class Node
{
int info;
Node prev, next;
}
class GFG
{
static Node head, tail;
// Function to insetail new node
static void nodeInsetail(int key)
{
Node p = new Node();
p.info = key;
p.next = null;
// If first node to be insetailed in doubly
// linked list
if (head == null)
{
head = p;
tail = p;
head.prev = null;
return;
}
// If node to be insetailed has value less
// than first node
if (p.info < head.info)
{
p.prev = null;
head.prev = p;
p.next = head;
head = p;
return;
}
// If node to be insetailed has value more
// than last node
if (p.info > tail.info)
{
p.prev = tail;
tail.next = p;
tail = p;
return;
}
// Find the node before which we need to
// insert p.
Node temp = head.next;
while (temp.info < p.info)
temp = temp.next;
// Insert new node before temp
(temp.prev).next = p;
p.prev = temp.prev;
temp.prev = p;
p.next = temp;
}
// Function to print nodes in from left to right
static void printList(Node temp)
{
while (temp != null)
{
System.out.print(temp.info + " ");
temp = temp.next;
}
}
// Driver code
public static void main(String args[])
{
head = tail = null;
nodeInsetail(30);
nodeInsetail(50);
nodeInsetail(90);
nodeInsetail(10);
nodeInsetail(40);
nodeInsetail(110);
nodeInsetail(60);
nodeInsetail(95);
nodeInsetail(23);
System.out.println("Doubly linked list on printing from left to right");
printList(head);
}
}
// This code is contributed by rachana soma
Python
# Python program to insetail nodes in doubly
# linked list such that list remains in
# ascending order on printing from left
# to right
# Linked List node
class Node:
def __init__(self, data):
self.info = data
self.next = None
self.prev = None
head = None
tail = None
# Function to insetail new node
def nodeInsetail( key) :
global head
global tail
p = Node(0)
p.info = key
p.next = None
# If first node to be insetailed in doubly
# linked list
if ((head) == None) :
(head) = p
(tail) = p
(head).prev = None
return
# If node to be insetailed has value less
# than first node
if ((p.info) < ((head).info)) :
p.prev = None
(head).prev = p
p.next = (head)
(head) = p
return
# If node to be insetailed has value more
# than last node
if ((p.info) > ((tail).info)) :
p.prev = (tail)
(tail).next = p
(tail) = p
return
# Find the node before which we need to
# insert p.
temp = (head).next
while ((temp.info) < (p.info)) :
temp = temp.next
# Insert new node before temp
(temp.prev).next = p
p.prev = temp.prev
temp.prev = p
p.next = temp
# Function to print nodes in from left to right
def printList(temp) :
while (temp != None) :
print( temp.info, end = " ")
temp = temp.next
# Driver program to test above functions
nodeInsetail( 30)
nodeInsetail( 50)
nodeInsetail( 90)
nodeInsetail( 10)
nodeInsetail( 40)
nodeInsetail( 110)
nodeInsetail( 60)
nodeInsetail( 95)
nodeInsetail( 23)
print("Doubly linked list on printing from left to right\n" )
printList(head)
# This code is contributed by Arnab Kundu
C#
/* C# program to insetail nodes in doubly
linked list such that list remains in
ascending order on printing from left
to right */
using System;
// A linked list node
public class Node
{
public int info;
public Node prev, next;
}
class GFG
{
static Node head, tail;
// Function to insetail new node
static void nodeInsetail(int key)
{
Node p = new Node();
p.info = key;
p.next = null;
// If first node to be insetailed in doubly
// linked list
if (head == null)
{
head = p;
tail = p;
head.prev = null;
return;
}
// If node to be insetailed has value less
// than first node
if (p.info < head.info)
{
p.prev = null;
head.prev = p;
p.next = head;
head = p;
return;
}
// If node to be insetailed has value more
// than last node
if (p.info > tail.info)
{
p.prev = tail;
tail.next = p;
tail = p;
return;
}
// Find the node before which we need to
// insert p.
Node temp = head.next;
while (temp.info < p.info)
temp = temp.next;
// Insert new node before temp
(temp.prev).next = p;
p.prev = temp.prev;
temp.prev = p;
p.next = temp;
}
// Function to print nodes in from left to right
static void printList(Node temp)
{
while (temp != null)
{
Console.Write(temp.info + " ");
temp = temp.next;
}
}
// Driver code
public static void Main(String []args)
{
head = tail = null;
nodeInsetail(30);
nodeInsetail(50);
nodeInsetail(90);
nodeInsetail(10);
nodeInsetail(40);
nodeInsetail(110);
nodeInsetail(60);
nodeInsetail(95);
nodeInsetail(23);
Console.WriteLine("Doubly linked list on printing from left to right");
printList(head);
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
/* javascript program to insetail nodes in doubly
linked list such that list remains in
ascending order on printing from left
to right */
// A linked list node
class Node {
constructor() {
this.info = 0;
this.prev = null;
this.next = null;
}
}
var head, tail;
// Function to insetail new node
function nodeInsetail(key) {
p = new Node();
p.info = key;
p.next = null;
// If first node to be insetailed in doubly
// linked list
if (head == null) {
head = p;
tail = p;
head.prev = null;
return;
}
// If node to be insetailed has value less
// than first node
if (p.info < head.info) {
p.prev = null;
head.prev = p;
p.next = head;
head = p;
return;
}
// If node to be insetailed has value more
// than last node
if (p.info > tail.info) {
p.prev = tail;
tail.next = p;
tail = p;
return;
}
// Find the node before which we need to
// insert p.
temp = head.next;
while (temp.info < p.info)
temp = temp.next;
// Insert new node before temp
(temp.prev).next = p;
p.prev = temp.prev;
temp.prev = p;
p.next = temp;
}
// Function to print nodes in from left to right
function printList( temp) {
while (temp != null) {
document.write(temp.info + " ");
temp = temp.next;
}
}
// Driver code
head = tail = null;
nodeInsetail(30);
nodeInsetail(50);
nodeInsetail(90);
nodeInsetail(10);
nodeInsetail(40);
nodeInsetail(110);
nodeInsetail(60);
nodeInsetail(95);
nodeInsetail(23);
document.write("Doubly linked list on printing from left to right<br/>");
printList(head);
// This code is contributed by aashish1995
</script>
Producción:
Doubly linked list on printing from left to right 10 23 30 40 50 60 90 95 110
Complejidad de tiempo: O (n) desde que se usa un solo bucle para atravesar una lista doblemente enlazada
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AmishTandon y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA