En este artículo, implementaremos la estructura de datos LinkedList en Javascript. LinkedList es la estructura de datos dinámica, ya que podemos agregar o eliminar elementos fácilmente, e incluso puede crecer según sea necesario. Al igual que los arreglos, las listas enlazadas almacenan elementos secuencialmente, pero no almacenan los elementos de forma contigua como un arreglo.
Ahora, veamos un ejemplo de un Node de lista enlazada:
Javascript
// User defined class node
class Node {
// constructor
constructor(element)
{
this.element = element;
this.next = null
}
}
Como en el código anterior, definimos un Node de clase que tiene dos propiedades: elemento y siguiente . Element contiene los datos de un Node mientras que next mantiene el puntero al siguiente Node, que se inicializa con el valor nulo.
Ahora, veamos una implementación de la clase Linked List:
Javascript
// linkedlist class
class LinkedList {
constructor()
{
this.head = null;
this.size = 0;
}
// functions to be implemented
// add(element)
// insertAt(element, location)
// removeFrom(location)
// removeElement(element)
// Helper Methods
// isEmpty
// size_Of_List
// PrintList
}
El ejemplo anterior muestra una clase de lista enlazada con un constructor y una lista de métodos que se implementarán. La clase Lista enlazada tiene dos propiedades: es decir , cabeza y tamaño , donde la cabeza almacena el primer Node de una Lista y el tamaño indica el número de Nodes en una lista.
Implementemos cada una de estas funciones:
1. add(element) – Agrega un elemento al final de la lista.
Javascript
// adds an element at the end
// of list
add(element)
{
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the
// element and make it head
if (this.head == null)
this.head = node;
else {
current = this.head;
// iterate to the end of the
// list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this.size++;
}
Para agregar un elemento al final de la lista, consideramos lo siguiente:
- Si la lista está vacía, agregue un elemento y será la cabeza
- Si la lista no está vacía, itere hasta el final de la lista y agregue un elemento al final de la lista.
2. insertAt(elemento, índice) – Inserta un elemento en el índice dado en una lista.
Javascript
// insert element at the position index
// of the list
insertAt(element, index)
{
if (index < 0 || index > this.size)
return console.log("Please enter a valid index.");
else {
// creates a new node
var node = new Node(element);
var curr, prev;
curr = this.head;
// add the element to the
// first index
if (index == 0) {
node.next = this.head;
this.head = node;
} else {
curr = this.head;
var it = 0;
// iterate over the list to find
// the position to insert
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// adding an element
node.next = curr;
prev.next = node;
}
this.size++;
}
}
Para agregar un elemento en el índice dado de la lista, consideramos tres condiciones de la siguiente manera:
- si el índice es cero, agregamos un elemento al principio de la lista y lo hacemos encabezar
- Si el índice es la última posición de la lista, agregamos el elemento al final de la lista
- si el índice está entre 0 o tamaño – 1 iteramos sobre el índice y agregamos un elemento en ese índice
3. removeFrom(index) – Elimina y devuelve un elemento de la lista del índice especificado
Javascript
// removes an element from the
// specified location
removeFrom(index)
{
if (index < 0 || index >= this.size)
return console.log("Please Enter a valid index");
else {
var curr, prev, it = 0;
curr = this.head;
prev = curr;
// deleting first element
if (index === 0) {
this.head = curr.next;
} else {
// iterate over the list to the
// position to removce an element
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// remove the element
prev.next = curr.next;
}
this.size--;
// return the remove element
return curr.element;
}
}
Para eliminar un elemento de la lista consideramos tres condiciones:
- Si el índice es 0, eliminamos la cabeza y hacemos que el siguiente Node sea la cabeza de la lista
- si el índice es tamaño – 1, entonces eliminamos el último elemento de la lista y hacemos anterior el último elemento
- si está entre 0 y tamaño – 1, eliminamos el elemento usando prev y el Node actual
4. removeElement(elemento) – Este método elimina el elemento de la lista. Devuelve el elemento eliminado, o si no se encuentra devuelve -1.
Javascript
// removes a given element from the
// list
removeElement(element)
{
var current = this.head;
var prev = null;
// iterate over the list
while (current != null) {
// comparing element with current
// element if found then remove the
// and return true
if (current.element === element) {
if (prev == null) {
this.head = current.next;
} else {
prev.next = current.next;
}
this.size--;
return current.element;
}
prev = current;
current = current.next;
}
return -1;
}
El método anterior es solo una modificación de removeFrom(index) , ya que busca un elemento y lo elimina, en lugar de eliminarlo de una ubicación específica
Métodos auxiliares
Declaremos algunos métodos auxiliares que son útiles al trabajar con LinkedList.
1. indexOf(element) – devuelve el índice de un elemento dado si el elemento está en la lista.
Javascript
// finds the index of element
indexOf(element)
{
var count = 0;
var current = this.head;
// iterate over the list
while (current != null) {
// compare each element of the list
// with given element
if (current.element === element)
return count;
count++;
current = current.next;
}
// not found
return -1;
}
En este método, iteramos sobre la lista para encontrar el índice de un elemento. Si no está presente en la lista, devuelve -1 en su lugar.
2. isEmpty() : devuelve verdadero si la lista está vacía.
Javascript
// checks the list for empty
isEmpty()
{
return this.size == 0;
}
En este método, verificamos la propiedad de tamaño de la clase LinkedList y, si es cero, la lista está vacía.
3. size_of_list() – Devuelve el tamaño de la lista
Javascript
// gives the size of the list
size_of_list()
{
console.log(this.size);
}
3. printList() – Imprime el contenido de la lista.
Javascript
// prints the list items
printList()
{
var curr = this.head;
var str = "";
while (curr) {
str += curr.element + " ";
curr = curr.next;
}
console.log(str);
}
En este método, iteramos sobre la lista completa y concatenamos los elementos de cada Node y lo imprimimos.
Nota: Se pueden declarar diferentes métodos auxiliares en la clase LinkedList según sea necesario.
Implementación
Ahora, usemos la clase LinkedList y sus diferentes métodos descritos anteriormente.
Javascript
// creating an object for the
// Linkedlist class
var ll = new LinkedList();
// testing isEmpty on an empty list
// returns true
console.log(ll.isEmpty());
// adding element to the list
ll.add(10);
// prints 10
ll.printList();
// returns 1
console.log(ll.size_of_list());
// adding more elements to the list
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// returns 10 20 30 40 50
ll.printList();
// prints 50 from the list
console.log("is element removed ?" + ll.removeElement(50));
// prints 10 20 30 40
ll.printList();
// returns 3
console.log("Index of 40 " + ll.indexOf(40));
// insert 60 at second position
// ll contains 10 20 60 30 40
ll.insertAt(60, 2);
ll.printList();
// returns false
console.log("is List Empty ? " + ll.isEmpty());
// remove 3rd element from the list
console.log(ll.removeFrom(3));
// prints 10 20 60 40
ll.printList();
Código completo:
Javascript
class Node {
// constructor
constructor(element) {
this.element = element;
this.next = null
}
}
// linkedlist class
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// adds an element at the end
// of list
add(element) {
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the
// element and make it head
if (this.head == null)
this.head = node;
else {
current = this.head;
// iterate to the end of the
// list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this.size++;
}
// insert element at the position index
// of the list
insertAt(element, index) {
if (index < 0 || index > this.size)
return console.log("Please enter a valid index.");
else {
// creates a new node
var node = new Node(element);
var curr, prev;
curr = this.head;
// add the element to the
// first index
if (index == 0) {
node.next = this.head;
this.head = node;
} else {
curr = this.head;
var it = 0;
// iterate over the list to find
// the position to insert
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// adding an element
node.next = curr;
prev.next = node;
}
this.size++;
}
}
// removes an element from the
// specified location
removeFrom(index) {
if (index < 0 || index >= this.size)
return console.log("Please Enter a valid index");
else {
var curr, prev, it = 0;
curr = this.head;
prev = curr;
// deleting first element
if (index === 0) {
this.head = curr.next;
} else {
// iterate over the list to the
// position to removce an element
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// remove the element
prev.next = curr.next;
}
this.size--;
// return the remove element
return curr.element;
}
}
// removes a given element from the
// list
removeElement(element) {
var current = this.head;
var prev = null;
// iterate over the list
while (current != null) {
// comparing element with current
// element if found then remove the
// and return true
if (current.element === element) {
if (prev == null) {
this.head = current.next;
} else {
prev.next = current.next;
}
this.size--;
return current.element;
}
prev = current;
current = current.next;
}
return -1;
}
// finds the index of element
indexOf(element) {
var count = 0;
var current = this.head;
// iterate over the list
while (current != null) {
// compare each element of the list
// with given element
if (current.element === element)
return count;
count++;
current = current.next;
}
// not found
return -1;
}
// checks the list for empty
isEmpty() {
return this.size == 0;
}
// gives the size of the list
size_of_list() {
console.log(this.size);
}
// prints the list items
printList() {
var curr = this.head;
var str = "";
while (curr) {
str += curr.element + " ";
curr = curr.next;
}
console.log(str);
}
}
// creating an object for the
// Linkedlist class
var ll = new LinkedList();
// testing isEmpty on an empty list
// returns true
console.log(ll.isEmpty());
// adding element to the list
ll.add(10);
// prints 10
ll.printList();
// returns 1
console.log(ll.size_of_list());
// adding more elements to the list
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// returns 10 20 30 40 50
ll.printList();
// prints 50 from the list
console.log("is element removed ?" + ll.removeElement(50));
// prints 10 20 30 40
ll.printList();
// returns 3
console.log("Index of 40 " + ll.indexOf(40));
// insert 60 at second position
// ll contains 10 20 60 30 40
ll.insertAt(60, 2);
ll.printList();
// returns false
console.log("is List Empty ? " + ll.isEmpty());
// remove 3rd element from the list
console.log(ll.removeFrom(3));
// prints 10 20 60 40
ll.printList();
Producción:
true 10 1 undefined 10 20 30 40 50 is element removed ?50 10 20 30 40 Index of 40 3 10 20 60 30 40 is List Empty ? false 30 10 20 60 40
JavaScript es mejor conocido por el desarrollo de páginas web, pero también se usa en una variedad de entornos que no son de navegador. Puede aprender JavaScript desde cero siguiendo este tutorial de JavaScript y ejemplos de JavaScript .
Este artículo es una contribución de Sumit Ghosh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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