A diferencia de las arrays, los elementos de la lista enlazada no se almacenan en una ubicación contigua; los elementos se vinculan mediante punteros. En esta publicación, se analizan los métodos para insertar un nuevo Node en una lista vinculada. Un Node se puede insertar de tres formas , ya sea al principio de la lista enlazada o después de un Node determinado o al final de la lista enlazada. Como ya hemos discutido , la lista doblemente enlazada (DLL) contiene un puntero adicional, generalmente llamado puntero anterior , junto con el siguiente puntero y los datos que están allí en una lista enlazada individualmente.
De manera similar, una L ista triplemente enlazada ( TLL ) contiene un puntero extra, normalmente llamado puntero superior , junto con el siguiente puntero, el anterior y los datos que están en la lista doblemente enlazada. El puntero adicional aquí llamado como la parte superior se puede utilizar para varios propósitos. Por ejemplo, almacenar valores iguales en el mismo nivel. Consulte la imagen de abajo para una mejor comprensión. En este artículo, insertaremos Nodes en la lista vinculada en orden. Y almacenaremos elementos iguales en el mismo nivel, lo que significa que se accederá a ellos mediante el puntero superior .
Ilustración: Representación de un Node DLL
// Class for Triply Linked List
public class TLL {
// Triply Linked list Node
class Node {
int data;
Node prev;
Node next;
Node top;
}
// Head and Tail pointer
Node head = null, tail = null;
// To keep track of the number
// of nodes
int node_count = 0;
}
Procedimiento:
1. Insertar un nuevo Node
Dado que estamos almacenando Nodes en un orden ordenado, es por eso que tenemos que encontrar la posición correcta del Node dado en la lista enlazada.
- Si no hay Nodes en la lista (La lista está vacía), simplemente haga que la cabeza y la cola apunten a este Node.
- Si el Node dado es menor que el Node principal, simplemente inserte el Node al principio.
- Si el Node dado no es menor que el Node principal, recorra la lista y encuentre el primer Node que sea mayor que el Node dado.
- Si tal Node no existe, esto significa que el Node dado es mayor que todos los Nodes. Así que insértelo al final de la Lista.
- Si tal Node existe, inserte el Node dado antes del Node encontrado.
- Si el Node dado es igual a algún Node ya presente, inserte el Node dado en la parte superior de la Lista.
2(A): Atraviese la Lista desde la Cabeza donde comenzamos desde la cabeza y continuamos hasta el siguiente Node. Si la parte superior del Node actual no está vacía, imprima primero el Node superior y luego continúe recorriendo el resto de la lista.
2(B): recorrer la lista desde la cola o recorrido inverso en el que comenzamos desde la cola y continuamos hasta el Node anterior. Si la parte superior del Node actual no está vacía, imprima primero el Node superior y luego continúe recorriendo el resto de la lista.
Ejemplo:
Java
// Java Program to Implement Triply Linked List
// Importing all utility classes
import java.util.*;
// Main Class
public class GFG {
// First let us create a Node class
class Node {
// Data refers to the value in node
int data;
// Being triply linked list,
// three pointers needs to be defined
Node prev;
Node next;
Node top;
// Parameterized constructor of Node class
// to initialize the node whenever created
Node(int data)
{
// this keyword refers to current object itself
this.data = data;
// Initializing all 3 pointers to null
prev = null;
next = null;
top = null;
}
}
// Defining two new pointers for iterate over to perform
// operations over the triply linked list Head and Tail
// pointer
Node head = null, tail = null;
// Declaring and initializing variable to
// keep track of the number of nodes
int node_count = 0;
// Method 1
// To insert a new node
public void insert(int new_data)
{
// Create new node with the given data
Node new_node = new Node(new_data);
// curr_node to traverse the List
Node curr_node = null;
// If List is empty then
// make head and tail
// equal to this node
if (node_count == 0) {
// Case 1: Of LinkedList is empty
// If there is no such node existing
tail = new_node;
head = new_node;
curr_node = head;
// So next will be assigned a null
curr_node.next = null;
curr_node.prev = null;
curr_node.top = null;
// Increment the node count
node_count++;
}
// Case 2: If LinkedList is not empty
// Case 2(A): If given node is less then the head
else {
// Make curr_node point to head
curr_node = head;
// If given node is less then the head
// insert at the beginning
if (new_node.data < curr_node.data) {
// Linking two nodes through addresses
new_node.next = curr_node;
curr_node.prev = new_node;
new_node.prev = null;
head = new_node;
curr_node = head;
// Adjusting the tail
do {
curr_node = curr_node.next;
} while (curr_node.next != null);
tail = curr_node;
}
// CAse 2(B): If given node is not less then the
// head
else {
// last_node to keep track of
// the last visited node
Node last_node = curr_node;
// Goal is to traverse the List and
// find first node greater than new_node
while (curr_node != null
&& new_node.data > curr_node.data) {
last_node = curr_node;
curr_node = curr_node.next;
// If curr_node is null that
// means we have reached the
// end of the list so insert the
// node at the end and update the tail
if (curr_node == null) {
last_node.next = new_node;
new_node.prev = last_node;
new_node.next = null;
tail = new_node;
// Haulting the execution of the
// program using break keyword
break;
}
else if (new_node.data
<= curr_node.data) {
// If curr_node is greater than
// the new_node then insert the
// new_node before curr_nod and
// update the tail
if (new_node.data
< curr_node.data) {
last_node.next = new_node;
new_node.prev = last_node;
new_node.next = curr_node;
curr_node.prev = new_node;
if (curr_node.next != null) {
do {
curr_node
= curr_node.next;
}
while (curr_node.next
!= null);
}
tail = curr_node;
break;
}
// If curr_node is equal to the
// new_node then insert the
// new_node to the top of the
// curr_nod and update the tail
else if (curr_node.data
== new_node.data) {
last_node = curr_node;
while (last_node.top != null) {
last_node = last_node.top;
}
last_node.top = new_node;
new_node.top = null;
break;
}
}
}
}
}
}
// Method 2
// Traversing list from head
public void traverse_head()
{
Node node = head;
Node curr = null;
while (node != null) {
System.out.print(node.data + "\t");
curr = node;
// If curr has top node
// then traverse them first
while (curr.top != null) {
curr = curr.top;
// Print top node first followed by rest of
// list
System.out.print("top->" + curr.data
+ "\t");
}
// Update the node to next node
node = node.next;
}
// New line
System.out.println();
}
// Method 3
// Traversing list from tail
public void traverse_tail()
{
Node node = tail;
Node curr = null;
while (node != null) {
System.out.print(node.data + "\t");
curr = node;
// If curr has top node
// then traverse them first
while (curr.top != null) {
curr = curr.top;
// Print top node first followed by rest of
// list
System.out.print("top->" + curr.data
+ "\t");
}
// Update the node to prev node
node = node.prev;
}
// New line
System.out.println();
}
// Method 4
// Main driver method
public static void main(String args[])
{
// Creating an object of main class in the main()
// method
// by starting with the empty list
GFG tll = new GFG();
// Inserting custom input integer numbers
// using insert() method
// Number Set = {7,9,1,5,7}
// Insert the first number i.e 7,
// so linked list become
// 7 -> NULL
tll.insert(7);
// Insert the second number i.e 9,
// so linked list becomes
// 7 -> 9 -> NULL
tll.insert(9);
// Insert the third number i.e 1,
// so linked list becomes
// 1 -> 7 -> 9 -> NULL
tll.insert(1);
// Insert the fourth number i.e 5,
// so linked list becomes
// 1 -> 5 -> 7 -> 9 -> NULL
tll.insert(5);
// Insert the fifth number i.e 7,
// so linked list becomes
// 1 -> 5 -> 7 (top->7) -> 9 -> NULL
tll.insert(7);
// Display message only
System.out.println(
"\nTraversing Linked List head: ");
// Calling the traverse_head() method () / Method 2
tll.traverse_head();
// Display message only
System.out.println(
"\nTraversing Linked List tail: ");
// Calling the traverse_tail() method / Method 3
tll.traverse_tail();
}
}
Traversing Linked List head: 1 5 7 top->7 9 Traversing Linked List tail: 9 7 top->7 5 1
La representación del flujo de trabajo de la lista vinculada después de ejecutar el programa anterior se representa gráficamente y es la siguiente:
Publicación traducida automáticamente
Artículo escrito por adityapande88 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA