Una suave introducción a las estructuras de datos: cómo funcionan las listas enlazadas

¿Ha construido alguna vez una máquina Rube Goldberg? Si no es así, ¿tal vez ha construido una elaborada línea de dominó?

De acuerdo, tal vez no eras tan nerd como yo. Que así sea. Para aquellos de ustedes que han tenido el placer de hacer algo de lo anterior, ya han captado la esencia de la estructura de datos actual: ¡listas enlazadas!

Cómo funcionan las listas vinculadas

La forma más simple de listas vinculadas, una lista vinculada individualmente, es una serie de nodos donde cada nodo individual contiene un valor y un puntero al siguiente nodo de la lista.

Las adiciones ( Agregar ) aumentan la lista al agregar elementos al final de la lista.

Eliminaciones ( Eliminar) siempre eliminará de una posición determinada en la lista.

Buscar ( contiene ) buscará en la lista un valor.

Casos de uso de ejemplo:

  • Almacenar valores en una tabla hash para evitar colisiones (más sobre esto en algunas publicaciones)
  • ¡Rehaciendo la increíble carrera!

Mantengamos este artículo agradable y ligero trabajando en una herramienta que la cadena CBS puede usar para planificar su próximo programa de televisión de carreras increíble.

A medida que avanza en esto, quiero que se siga preguntando: “¿En qué se diferencian las listas enlazadas de las matrices? ¿En qué se parecen? "

Empecemos.

Primero, necesita crear la representación de nuestra lista vinculada:

class LinkedList{ constructor(){ this._head = null; this._tail = null; this._length = 0; }
 size(){ return this._length; }}

Para realizar un seguimiento del punto de partida y el punto final de la carrera, crea las propiedades de cabeza y cola.

Luego, para asegurarse de que la carrera no sea demasiado larga o demasiado corta para la temporada, cree una propiedad de longitud y un método de tamaño. De esta manera, siempre puede realizar un seguimiento de la duración exacta de la carrera.

Ahora que tiene una forma de almacenar la lista de carreras, debe crear una forma de agregarla a esta lista. La pregunta es, ¿qué está agregando específicamente?

Recuerde, una lista vinculada es una serie de nodos donde cada nodo tiene un valor y un puntero al siguiente nodo de la lista. Sabiendo esto, te das cuenta de que un nodo es solo un objeto con un valor y la siguiente propiedad.

Dado que va a crear un nuevo nodo cada vez que agregue a la lista, decide crear un constructor que facilite la creación de un nuevo nodo para cada valor que se agregue a su lista.

class Node{ constructor(value){ this.value = value; this.next = null; }}

Tener este constructor disponible le permite crear su método add.

class Node { constructor(value) { this.value = value; this.next = null; }}
class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); //we create our node if(!this._head && !this._tail){ //If it's the first node this._head = node; //1st node is head & tail this._tail = node; }else{ this._tail.next = node; //add node to the back this._tail = this._tail.next; //reset tail to last node } this._length++; } size() { return this._length; }}
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");

Ahora que ha agregado este método, podrá agregar un montón de ubicaciones a su lista Amazing Race. Así es como se verá. Tenga en cuenta que agregué un espacio en blanco adicional para que sea más fácil de entender.

{ _head: { value: 'Colombo, Sri Lanka', next: { value: 'Lagos, Nigeria', next: { value: 'Surat, India', next: { value: 'Suzhou, China', next: null } } } }, _tail: { value: 'Suzhou, China', next: null }, _length: 4 }

Bien, ahora que ha creado esta lista y una forma de agregar, se da cuenta de que desea ayuda para agregar ubicaciones a esta lista porque tiene decidofobia (sí, es una cosa).

Decide compartirlo con su compañero de trabajo, Kent, y le pide que agregue algunos lugares más. El único problema es que, cuando se lo das, no le dices qué lugares ya has agregado. Desafortunadamente, usted también lo ha olvidado después de sufrir amnesia provocada por la ansiedad por tomar decisiones.

Por supuesto, podría ejecutar console.log (AmazingRace) y leer los resultados de la consola. Pero Kent es un programador vago y necesita una forma de comprobar si existe algo para evitar duplicados. Con eso en mente, crea un método contiene para verificar los valores existentes.

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");
//Kent's check
AmazingRace.contains('Suzhou, China'); //trueAmazingRace.contains('Hanoi, Vietnam'); //falseAmazingRace.add('Hanoi, Vietnam');AmazingRace.contains('Seattle, Washington'); //falseAmazingRace.add('Seattle, Washington');AmazingRace.contains('North Pole'); // falseAmazingRace.add('North Pole');

Genial, ahora Kent tiene una forma de verificar los valores antes de agregarlos, para evitar duplicados.

Como acotación al margen, es posible que se pregunte por qué no utilizó el método contiene en el método de adición para evitar adiciones duplicadas. Cuando está implementando una lista vinculada, o cualquier estructura de datos, en teoría, podría agregar cualquier funcionalidad adicional que desee.

Incluso puede ingresar y cambiar métodos nativos en estructuras existentes. Pruebe lo siguiente en un REPL:

Array.prototype.push = () => { return 'cat';}
let arr = [];arr.push('eggs'); // returns 'cat';

La razón por la que no hacemos ninguna de estas cosas es por los estándares acordados. Esencialmente, los desarrolladores tienen la expectativa de cómo deberían funcionar ciertos métodos.

Dado que nuestra clase de lista vinculada no es nativa de JavaScript, tenemos más libertad para implementarla, pero aún existen expectativas básicas sobre cómo deberían funcionar estructuras de datos como estas. Las listas vinculadas no almacenan inherentemente valores únicos. Pero tienen métodos como contiene que nos permiten verificar previamente y mantener la unicidad en nuestra lista.

Kent se comunica con usted con su lista de destinos, pero algunos de ellos son cuestionables. Por ejemplo, el Polo Norte podría no ser el mejor destino de Amazing Race.

Así que decides crear un método para poder eliminar un nodo. Es importante recordar que una vez que elimine el nodo, desvinculará la lista y tendrá que volver a vincular lo que vino antes y después del nodo eliminado.

class Node { constructor(value) { this.value = value; this.next = null; }}class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ // see if our value exists let current = this._head; // begin at start of list let previous = this._head; while(current){ // check each node if(current.value === value){ if(this._head === current){ // if it's the head this._head = this._head.next; // reset the head this._length--; // update the length return; // break out of the loop } if(this._tail === current){ // if it's the tail node this._tail = previous; // make sure to reset it } previous.next = current.next; // unlink (see img below) this._length--; // update the length return; // break out of } previous = current; // look at the next node current = current.next; // ^^ } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; } }
const AmazingRace = new LinkedList();AmazingRace.add("Colombo, Sri Lanka");AmazingRace.add("Lagos, Nigeria");AmazingRace.add("Surat, India");AmazingRace.add("Suzhou, China");AmazingRace.add('Hanoi, Vietnam');AmazingRace.add('Seattle, Washington');AmazingRace.add('North Pole');
//Kent's check
AmazingRace.remove('North Pole');

There’s a lot of code in that remove function up there. Essentially it boils down to the following:

  1. if the value exists in the list…
  2. iterate over the linked list, keeping track of the previous and current node
  3. then, if there’s a match →

4A . if it’s the head

  • reset the head to the next node in the list
  • update the length
  • break out of the loop

4B. if it’s the tail

  • reset the tail to the previous node in the list
  • unlink the node by resetting the pointers as seen below

4C. If it’s not a match → continue iterating

  • make the next node current
  • make the current node previous

One last thing to note: you may have realized that you didn’t actually delete the node. You just removed the references to it. Well, that’s OK because once all references to an object are removed, the garbage collector helps us remove it from memory. You can read up on the garbage collection here.

With the remove method now implemented, you can run this little piece of code below to make sure contestants don’t freeze to death, or accidentally bother Santa as he’s prepping for this year’s festivities.

AmazingRace.remove('North Pole');

You’ve done it! You’ve created a simple implementation of a linked list. And you can grow the list by adding items, and shrink it by removing items — all based on the item’s value.

See if you can add you can expand the linked list to allow you to insert values at the beginning, end, or any point in between.

You have all you need to implement those methods. The names and arguments for these methods should look a little like this:

addHead(value) {
}
insertAfter(target, value){
}

Feel free to share your implementations in the comments below ?

A time complexity analysis on the queue methods

Here’s the code again:

class LinkedList { constructor() { this._head = null; this._tail = null; this._length = 0; } add(value) { let node = new Node(value); if(!this._head && !this._tail){ this._head = node; this._tail = this._head; }else{ this._tail.next = node; this._tail = this._tail.next; } this._length++; } remove(value) { if(this.contains(value)){ let current = this._head; let previous = this._head; while(current){ if(current.value === value){ if(this._head === current){ this._head = this._head.next; this._length--; return; } if(this._tail === current){ this._tail = previous; } previous.next = current.next; this._length--; return; } previous = current; current = current.next; } } } contains(value){ let node = this._head; while(node){ if(node.value === value){ return true; } node = node.next; } return false; } size() { return this._length; }
// To Be Implemented
addHead(value) {
}
insertAfter(target, value){
}

Add is O(1): Since you always know the last item in the list thanks to tail property, you don’t have to iterate over the list.

Remove is O(n): In the worst case scenario you’re going to have to iterate over the entire list to find the value to be removed. Great part though is the actual removal of the node is O(1) because you’re just resetting pointers.

Contains is O(n): You have to iterate over the entire list to check if the value exists in your list.

addHead is O(1): Similar to our add method above, we always know the position of the head, so no iteration necessary.

insertAfter is O(n): Similar to our Remove method above, you’ll have to iterate over the entire list to find the target node that your value should be inserted after. Likewise, the actual insertion is O(1) because you’re just resetting pointers.

Linked List vs Array?

Why would you use a linked list instead of an arrays? Arrays technically allow you to do all of the things linked lists do, such as additions, insertions, and removals. Also, all these methods are already readily available to us in JavaScript.

Well, the biggest difference comes in the insertions and removals. Since arrays are indexed, when you perform an insertion or removal in the middle of the array, you have to reset the position of all following values to their new indices.

Imagine inserting into the start or middle of an array 100,000 values long! Insertions and removals like this are extremely expensive. Because of this, linked lists are often preferred for large data sets that are often shifted around.

On the other hand, arrays are great when it comes to finding items (random access) since they are indexed. If you know the position of an item, you can access it in O(1) time via array[position].

Linked lists always require you to iterate over the linked lists sequentially. Given this, arrays are usually preferred for either smaller data sets, or data sets that aren’t shifted around as often.

Time for a quick recap

Linked Lists:

  1. have a tail and head property to track the ends of the list
  2. have an add, addHead, insertAfter, and remove method to manage the contents of your list
  3. have a length property to track how long your linked list is

Further Reading

There are also the doubly-linked list and circular-linked list data structures. You can read about them on Wikipedia.

Also, here’s a solid, quick overview by Vivek Kumar.

Finally, Ian Elliot wrote a walk-through that helps you implementing all of the methods. But see if you can implement addHead() and insertAfter() for your linked list before peeking at this ?