La lista enlazada es una estructura de datos lineal. Los elementos de la lista vinculada no se almacenan en una ubicación contigua, los elementos se vinculan mediante punteros. La lista de enlaces individuales es la colección de Nodes, donde cada Node tiene dos partes, una son los datos y la otra es la parte vinculada.
Ejemplo:
Input : AddNodes = {2, 3, 4}
Output: LinkedList = [2, 3, 4]
Size = 3
Input : AddNodes = {1, 2, 3, 4, 5}
Output: LinkedList = [1, 2, 3, 4, 5]
Size = 5
Operaciones:
- Crear lista vinculada de Nodes
- Defina métodos como addNode(),displayNodes() y countNodes()
- Obtenga la respuesta final
Implementación:
Java
// Java Program to Create a Singly Linked List
// of n Nodes and Count the Number of Nodes
import java.io.*;
import java.util.*;
public class LinkedListCreation {
class Node {
int data;
Node next;
// constructor to create new node
Node(int data)
{
this.data = data;
this.next = null;
}
}
// Initially both head and tail are not
// pointing to any other node
Node head = null;
Node tail = null;
// method to add newNode in Linked List
void addNode(int data)
{
Node newNode = new Node(data);
// Checks if the list is empty
if (head == null) {
// If list is empty, both head and
// tail will point to new node
head = newNode;
tail = newNode;
}
else {
tail.next = newNode;
// storing newnode in tail
tail = newNode;
}
}
// display linked list
void displayNodes()
{
Node current = head;
if (head == null) {
System.out.println("Empty");
return;
}
System.out.println("Nodes : ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.println();
}
// method to count nodes
int countNodes()
{
// Initially zero
int count = 0;
Node currentNode = head;
// iterate until all the nodes are present
while (currentNode != null) {
count++;
currentNode = currentNode.next;
}
// return the count
return count;
}
public static void main(String[] args)
{
LinkedListCreation L1 = new LinkedListCreation();
L1.addNode(1);
L1.addNode(2);
L1.addNode(3);
L1.addNode(4);
// Displays the nodes present in the list
L1.displayNodes();
// Counts the nodes present in the given list
System.out.println("Total Nodes: "
+ L1.countNodes());
}
}
Producción
Nodes : 1 2 3 4 Total Nodes: 4
Complejidad de tiempo para la inserción de un nuevo Node:
- Al principio: O(1)
- Al final: O(N), donde N es el tamaño de la lista enlazada
Complejidad de tiempo Para contar el número de Nodes: O(N), donde N es un número de Nodes