Siempre entendí el concepto central de las Listas Vinculadas, pero nunca lo puse en práctica.
No fue hasta mi primera entrevista en Amazon hace años cuando me di cuenta de que no tenía idea de cómo el concepto de Listas Vinculadas se traducía en código.
¡Y es por eso que estoy escribiendo esta guía!
Mi objetivo es ayudarte a conseguir un trabajo como ingeniero de software.
Quiero cubrir muchas preguntas de entrevistas de Listas vinculadas, y este artículo es el primer paso en ese proceso. Así que vamos a sumergirnos.
¿Qué es una lista vinculada?
Una lista vinculada es una estructura de datos que consta de muchas mini estructuras de datos denominadas 'Nodos'. Los nodos se enlazan para formar una lista.
Cada nodo contiene 2 atributos
- Es valioso. Puede ser cualquier cosa: números enteros, caracteres, cadenas, objetos, etc.
- Un puntero al siguiente nodo de la secuencia.
Algunas definiciones
El 'nodo principal': el nodo principal es simplemente el primer nodo de la lista vinculada. Como podemos ver en el ejemplo anterior, el nodo que contiene '5' es el primer nodo y, por lo tanto, la cabeza.
El 'nodo de cola': el nodo de cola es el último nodo de la secuencia. Como es el último nodo, apunta a nulo, porque no hay ningún nodo siguiente en la secuencia. En el ejemplo anterior, el nodo que contiene '3' sería el nodo de cola.
Vinculado individualmente o vinculado doblemente
Cuando se trata de listas vinculadas, hay dos tipos principales.
Aquellos que están vinculados 'individualmente' y aquellos que están vinculados 'doblemente'.
Vinculado individualmente significa que cada nodo solo apunta como máximo a otro nodo, el nodo frente a él. Esto se muestra en el ejemplo anterior.
Doblemente vinculado significa que cada nodo puede apuntar a otros 2 nodos, el nodo que está enfrente y el nodo detrás. Como podemos ver en el ejemplo siguiente, dado que no hay ningún nodo que preceda al nodo principal (que es 5), uno de sus punteros apunta a nulo.
Está bien, entiendo todo eso. Pero, ¿cómo funciona el código?
La codificación de listas enlazadas puede ser un problema de 4 líneas o un problema de 400 líneas. Depende de cómo quieras abordarlo.
En el nivel más simple, como discutimos, una lista vinculada es solo un grupo de nodos conectados.
Por lo tanto, todo lo que realmente necesitamos para crear esta estructura es un objeto de nodo.
class linkedListNode: def __init__(self, value, nextNode=None): self.value = value self.nextNode = nextNodeAquí podemos ver que simplemente hemos creado una clase que tiene un valor y un atributo nextNode.
Para crear un nodo, simplemente pasamos un valor.
node1 = linkedListNode("3") # "3"node2 = linkedListNode("7") # "7"node3 = linkedListNode("10") # "10"Aquí, hemos creado 3 nodos individuales.
El siguiente paso es simplemente conectarlos.
node1.nextNode = node2 node2.nextNode = node3 La primera línea de arriba hace que el nodo1 apunte al nodo2:
“3” → “7”
La segunda línea de arriba hace que el nodo2 apunte al nodo3:
“7” → ”10"
Todos juntos, nos queda una lista vinculada que se ve así:
“3” → ”7" → ”10" → Nulo
Nota: “10” apunta a nulo, porque no había ningún nextNode asignado al nodo3, y el nextNode predeterminado es Null.
Como mencioné anteriormente, hay muchas formas diferentes de hacer esto. Este es el más simple.
Si está intentando crear una clase LinkedList completa, este video explica en profundidad cómo hacerlo.
Atravesando una lista vinculada
Si está realizando una entrevista de programación y le hacen una pregunta de la Lista vinculada, no se le darán todos los nodos.
Todo lo que obtendrás es el nodo principal.
Desde ese nodo principal, debe obtener el resto de la lista.
First let’s understand how to get the value and nextNode from a node in Python.
Let’s say we have a node simply named ‘node’.
Getting the value of the node:
node.valueGetting the nextNode of the node:
node.nextNodeTraversal
This first thing we want to do is create a variable called “currentNode” that keeps track of the node we’re at. We want to assign this to our head node at first.
currentNode = headNow all we have to do is simply check whether or not our current node is Null. If it’s not, we make our ‘currentNode’ equal to the ‘nextNode’ of the ‘currentNode’.
currentNode = node1while currentNode is not None: currentNode = currentNode.nextNodeLet’s say we have the following Linked List: “3”→”7"→”10".
Our head and first ‘currentNode’ is “3”.
When we do
currentNode = currentNode.nextNodeWe are reassigning ‘currentNode’ to our current node’s neighbor, which in this case is “7”.
This continues until the currentNode is pointed to None, in which case the loop stops.
And that is the basic way to traverse through a Linked List in Python.
Link to the code on Github.
Inserting elements
When you insert an element into a linked list, you insert it into the back unless specified otherwise.
Let’s use the following example:
“3”→”7"→”10"→Null
Let’s say we want to insert a “4”.
We would simply find the tail node, in this case “10”, and set its nextNode to our “4” node.
“3”→”7"→”10"→“4”→Null
node4 = linkedListNode("4")node3.nextNode = node4Now let’s say we were in an interview, and all we had was the head node.
We simply traverse through the LinkedList to find the tail. Once we have the tail, we simply set its nextNode to our new node that we create.
def insertNode(head, valuetoInsert): currentNode = head while currentNode is not None: if currentNode.nextNode is None: currentNode.nextNode = linkedListNode(valuetoInsert) return head currentNode = currentNode.nextNodeDeleting elements
Deleting can get a bit tricky.
Let’s take the same example.
“3”→”7"→”10"→Null
If we wanted to delete the “7”, all we need to do is point the “3” to the “10” so that the “7” is never referenced.
“3”→”10"→Null
To do this, we would have to traverse the list while not only keeping track of the currentNode, but also keeping track of the previousNode.
We would also have to account for the head node being the node we want to delete.
In the code below, we simply delete the first instance of the value we want to delete.
Note that there are many ways to accomplish this, and the solution below might not be the cleanest code you’ll see in your life. However, in the heat of an interview, the interviewer probably won’t expect textbook perfect code.
def deleteNode(head, valueToDelete): currentNode = head previousNode = None while currentNode is not None: if currentNode.value == valueToDelete: if previousNode is None: newHead = currentNode.nextNode currentNode.nextNode = None return newHead # Deleted the head previousNode.nextNode = currentNode.nextNode return head previousNode = currentNode currentNode = currentNode.nextNode return head # Value to delete was not found.In the code above, once we find the node we want to delete, we set the previous node’s “nextNode” to the deleted node’s “nextNode” to completely cut it out of the list.
Big O Time Complexity Analysis
**NOTE** These are the time complexities for the node structure above, which is most likely to appear on an interview. In practical cases, you can store attributes in a LinkedList class to lower these complexities.
‘n’ = the amount of elements inside the Linked List.
Inserting to the back of the Linked List— We go through all n elements to find the tail and insert our new node. O(n)
Inserting to the front of the Linked List — We simply create the new node and set its nextNode to the head. No need to traverse the list. O(1)
Traversing — We go through all n elements once. O(n)
Deleting — Worst case scenario, the node we’re deleting is the last node, causing us to traverse through the entire list. O(n)
You can now tackle Linked List interview questions!
You now have the fundamental knowledge you need to start tackling Linked List interview questions!
They can start off easy, and get tough really quick.
In the next article, I’m going to go over a couple of common questions and techniques you can use to solve them.
If you’re a student looking to land your dream internship or full-time job within the next 2 years, start practicing now!
I’ve started a community (www.theforge.ca) where we connect students with mentors and industry experts that help them navigate their way to their dream job.
Thanks for reading, and good luck!