Implementación de una lista enlazada simple o doblemente en Java (una pregunta de LeetCode)

Descripción de la tarea:

Diseñe su implementación de la lista enlazada. Puede optar por utilizar una lista con enlaces simples o dobles.

Un nodo en una lista enlazada individualmente debe tener dos atributos: val y next . val es el valor del nodo actual y next es un puntero/referencia al siguiente nodo.

Si desea utilizar la lista doblemente enlazada, necesitará un atributo prev para indicar el nodo anterior en la lista enlazada. Suponga que todos los nodos en la lista enlazada están indexados en 0 .

Implemente la clase MyLinkedList :

https://gist.github.com/RakhmedovRS/70950a8b5d8c6669cdd270d3ef7737e1

• MyLinkedList() Inicializa el objeto MyLinkedList .
• int get(int index) Obtiene el valor del nodo indexth en la lista enlazada. Si el índice no es válido, devuelve -1 .
• void addAtHead(int val) Agrega un nodo de valor val antes del primer elemento de la lista enlazada. Después de la inserción, el nuevo nodo será el primer nodo de la lista enlazada.
• void addAtTail(int val) Agrega un nodo de valor val como el último elemento de la lista enlazada.
• void addAtIndex(int index, int val) Agrega un nodo de valor val antes del nodo indexth en la lista enlazada. Si el index es igual a la longitud de la lista vinculada, el nodo se agregará al final de la lista vinculada. Si index es mayor que la longitud, el nodo no se insertará .
• void deleteAtIndex(int index) Elimina el nodo indexth en la lista enlazada, si el índice es válido.

Ejemplo 1:

 Input ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] Output [null, null, null, null, 2, null, 3] Explanation MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 myLinkedList.get(1); // return 2 myLinkedList.deleteAtIndex(1); // now the linked list is 1->3 myLinkedList.get(1); // return 3

Restricciones:

• 0 <= index, val <= 1000
• No utilice la biblioteca LinkedList incorporada.
• Se realizarán como máximo 2000 llamadas para get , addAtHead , addAtTail , addAtIndex y deleteAtIndex .

Mis pensamientos:

Personalmente, me encantan las tareas como esta. Se puede solucionar de muchas maneras distintas que si vamos a describirlas te aburrirás y te cansarás de leer tanta información. Esta tarea puede ayudarlo a desarrollar o mejorar su habilidad de dividir tareas en partes más pequeñas. Nuevamente, es una habilidad extremadamente importante si quieres convertirte en un gran ingeniero de software. Si ya tiene experiencia en algoritmos y estructuras de datos, podría hacer algo como esto.

https://gist.github.com/RakhmedovRS/beb76bad4c696c6ca962a46e5631d545

Está perfectamente bien resolver el problema de esta manera, pero solo funciona cuando ya sabe cómo funciona LinkedList y puede implementarlo desde cero. Si bien el enfoque anterior puede ahorrarle tiempo. Sugiero profundizar más e implementar nuestra propia versión de LinkedList. Estoy bastante seguro de que muchos de ustedes saben cómo funciona, pero cuando les pido que lo implementen, es posible que algunos de ustedes tengan dificultades.

Creo que después de leer o aprender algo, debes implementar lo que acabas de aprender. Le ayudará a comprender cómo funciona esta estructura de datos y dónde se puede utilizar. Los conocimientos adquiridos se memorizarán mejor.

Razonamiento:

Como dije, esta tarea es un ejemplo perfecto de dónde podemos dividir una tarea grande en tareas más pequeñas. Así que tratemos de entender cómo hacerlo.

Parece que necesitamos implementar al menos 5 métodos diferentes. Es un gran punto de partida. Mientras tenemos una imagen más grande en tu cabeza, podemos centrarnos en un subproblema específico que cada método debe resolver. Resolvamos problemas más pequeños uno por uno.

De acuerdo con el método de descripción, int get(int index) puede recibir el índice del elemento y devolver el elemento en este índice si lo tenemos en nuestra lista. Suena bastante sencillo. Tenemos una lista con elementos, iteremos a través de ella y hagamos un seguimiento del índice actual y el índice que se nos proporciona. Si son iguales, encontramos el elemento y podemos regresar. En todos los demás casos devolvemos -1. Preste atención a la línea 11. Usamos head ya que almacena el enlace al encabezado de la lista. Téngalo en cuenta, nos pondremos en contacto con él.

Ejemplo: tenemos la lista 1 -> 2 -> 3 -> 4 ->5

1 tiene índice 0, 2 tiene índice 1 y así sucesivamente. Si nos dan el índice 3, debemos devolver 4

https://gist.github.com/RakhmedovRS/ca3d76ae29d1210d6eb312f9350385d5

El siguiente método en nuestra lista es void addAtHead(int val) debe insertar valor al principio de nuestra lista. Este es un poco complicado. Tenemos head que almacena el enlace a la cabeza, por lo que queremos empujar el siguiente elemento e insertar el valor proporcionado justo después de la cabeza. Lo primero que hacemos es crear el nuevo enlace que almacenará el valor proporcionado ( esquema a continuación ). Al mismo tiempo, necesitamos actualizar las relaciones entre los enlaces existentes y el nuevo. En lugar de usar palabras, veamos algunas imágenes. Espero que te ayuden a entender el concepto.

También tenemos un tamaño variable que está aquí para almacenar la cantidad de elementos en nuestra lista.

https://gist.github.com/RakhmedovRS/f18182ba692a76502f4444bf58410af6

https://gist.github.com/RakhmedovRS/b84d3c5758832540450b394dd69d85d2

El siguiente método es void addAtTail(int val) hace casi lo mismo que el anterior, la única diferencia es que insertamos nuestro valor antes de la cola de nuestra lista.

https://gist.github.com/RakhmedovRS/47272129eea9dbc18b78f1591e79d3cd

El siguiente método es void addAtIndex(int index, int val) debe insertar un valor en LinkedList en un índice particular que se proporciona como parámetro. El primer nodo después de head tiene el índice 0, el siguiente tiene el índice 1 y así sucesivamente.

Nuestro objetivo es iterar al índice de destino e insertar valor en ese índice. Insertemos el valor 5 en el índice 1.

https://gist.github.com/RakhmedovRS/c032fe01f6ac4679295c1ef1ec5c1f31

Nuestro último método para implementar es void deleteAtIndex(int index) . Hace casi lo mismo que una inserción en el índice, excepto una cosa, esta vez eliminamos el enlace. Este artículo se está volviendo demasiado grande, así que proporciono algunas imágenes y código para que sea más fácil de entender. Eliminemos el nodo en el índice 3.

https://gist.github.com/RakhmedovRS/4b67829babc66f0a3d1845d6017d48dd

https://gist.github.com/RakhmedovRS/db7a74650045b6fe108b159525b7a579

El código anterior nos da los siguientes resultados

También publicadoaquí