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: y . es el valor del nodo actual y es un puntero/referencia al siguiente nodo. val next val next Si desea utilizar la lista doblemente enlazada, necesitará un atributo para indicar el nodo anterior en la lista enlazada. Suponga que todos los nodos en la lista enlazada están . prev indexados en 0 Implemente la clase : MyLinkedList https://gist.github.com/RakhmedovRS/70950a8b5d8c6669cdd270d3ef7737e1 Inicializa el objeto . MyLinkedList() MyLinkedList Obtiene el valor del nodo en la lista enlazada. Si el índice no es válido, devuelve . int get(int index) indexth -1 Agrega un nodo de valor 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 addAtHead(int val) val Agrega un nodo de valor como el último elemento de la lista enlazada. void addAtTail(int val) val Agrega un nodo de valor antes del nodo en la lista enlazada. Si el es igual a la longitud de la lista vinculada, el nodo se agregará al final de la lista vinculada. Si es mayor que la longitud, el nodo . void addAtIndex(int index, int val) val indexth index index no se insertará Elimina el nodo en la lista enlazada, si el índice es válido. void deleteAtIndex(int index) indexth 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 llamadas para , , , y . 2000 get addAtHead addAtTail addAtIndex 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, 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 ya que almacena el enlace al encabezado de la lista. Téngalo en cuenta, nos pondremos en contacto con él. int get(int index) head 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 debe insertar valor al principio de nuestra lista. Este es un poco complicado. Tenemos 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 que almacenará el valor proporcionado ( ). 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. void addAtHead(int val) head enlace esquema a continuación También tenemos un variable que está aquí para almacenar la cantidad de elementos en nuestra lista. tamaño https://gist.github.com/RakhmedovRS/f18182ba692a76502f4444bf58410af6 https://gist.github.com/RakhmedovRS/b84d3c5758832540450b394dd69d85d2 El siguiente método es hace casi lo mismo que el anterior, la única diferencia es que insertamos nuestro valor antes de la de nuestra lista. void addAtTail(int val) cola https://gist.github.com/RakhmedovRS/47272129eea9dbc18b78f1591e79d3cd El siguiente método es debe insertar un valor en LinkedList en un índice particular que se proporciona como parámetro. El primer nodo después de tiene el índice 0, el siguiente tiene el índice 1 y así sucesivamente. void addAtIndex(int index, int val) head 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 . 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. void deleteAtIndex(int index) https://gist.github.com/RakhmedovRS/4b67829babc66f0a3d1845d6017d48dd https://gist.github.com/RakhmedovRS/db7a74650045b6fe108b159525b7a579 El código anterior nos da los siguientes resultados También publicado aquí

Target

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Let Your Engineers & PMs focus on Product. Apply for $50K Credits!

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

Demasiado Largo; Para Leer

Company Mentioned

@rakhmedovrs

HISTORIAS RELACIONADAS