linked list java linked list implementation java examples
Este tutorial explica qué es una estructura de datos de lista enlazada en Java y cómo crear, inicializar, implementar, recorrer, invertir y ordenar una lista enlazada de Java:
En Java, una LinkedList es una estructura de datos que almacena elementos en una ubicación no contigua. Es una estructura de datos lineal.
Cada elemento de datos se denomina 'Nodo' y cada nodo tiene una parte de datos y una parte de dirección. La parte de la dirección almacena el enlace al siguiente nodo en LinkedList.
=> Visite aquí para ver la serie de formación Java para todos.
Lo que vas a aprender:
- LinkedList en Java
- Clase Java LinkedList
- Cómo crear una lista vinculada en Java
- Implementación de listas vinculadas en Java
- Lista enlazada de impresión / desplazamiento en Java
- Métodos LinkedList
- Lista vinculada inversa en Java
- Ordenar una lista vinculada en Java
- Eliminar duplicados
- Lista enlazada circular en Java
- LinkedList de Java 8
- Preguntas frecuentes
- Conclusión
LinkedList en Java
A continuación se muestra el diseño general de LinkedList:
Como se muestra en la representación anterior de LinkedList, cada elemento de LinkedList es el 'Nodo'. Cada nodo tiene dos partes, la primera parte almacena los datos y la segunda parte tiene una referencia o puntero o dirección del siguiente nodo en la LinkedList.
cómo abrir jar con java
Esta disposición es necesaria ya que los datos en LinkedList se almacenan en ubicaciones no contiguas, a diferencia de Arrays.
El 'Head' de LinkedList es un puntero que contiene la dirección del primer elemento en LinkedList. El último nodo de LinkedList es la cola. Como se muestra en la figura anterior, la parte de la dirección del último nodo en LinkedList se establece en 'Null', lo que indica el final de LinkedList.
El diagrama anterior representa un ' Lista de enlaces individuales ”Que almacena la dirección sólo del siguiente nodo en LinkedList.
Existe otra versión conocida como ' Lista doblemente vinculada ”Cuyo cada nodo tiene tres partes:
- Dirección o referencia o puntero al elemento anterior en LinkedList.
- Parte de datos
- Dirección o referencia o puntero al siguiente elemento en LinkedList.
La dirección anterior del primer elemento en LinkedList se establecerá en Null mientras que el siguiente puntero del último elemento en LinkedList se establecerá en Null.
Representación de lista doblemente enlazada:
Como se muestra en la representación anterior, cada nodo en la lista doblemente enlazada tiene punteros a su nodo anterior y siguiente (representados así sin flechas). El puntero anterior del primer nodo apunta a nulo mientras que el siguiente puntero del último nodo apunta a nulo.
En este tutorial de LinkedList, nos ocuparemos principalmente de la lista de enlaces individuales. Discutiremos la lista doblemente enlazada en nuestro próximo tutorial.
Clase Java LinkedList
En Java, la lista vinculada se implementa mediante el ' Lista enlazada ' clase. Esta clase pertenece a la ' java.util ' paquete. La clase LinkedList implementa las interfaces List y Deque y hereda la clase AbstractList.
A continuación se muestra la jerarquía de clases de la clase LinkedList.
El diagrama anterior muestra la jerarquía de la clase LinkedList. Como se muestra, la clase LinkedList implementa las interfaces List y Deque.
Como ya se mencionó, la clase LinkedList es parte de la ' java.util ' paquete. Por lo tanto, debería poder usar la clase LinkedList en su programa al incluir una de las siguientes declaraciones en su programa.
|_+_|O
|_+_|Entonces, según la jerarquía anterior, una definición típica de la clase LinkedList es la siguiente:
|_+_|A continuación se enumeran algunas de las características de la clase LinkedList que debe recordar:
- Esta clase no está sincronizada.
- Permite valores duplicados.
- Conserva la orden de inserción.
- Como no se requiere que los elementos se muevan mientras se mueven, la manipulación de elementos es más rápida.
- Esta clase se puede utilizar para implementar una pila, una cola y una lista.
Cómo crear una lista vinculada en Java
Antes de pasar a la creación de una lista vinculada en Java, analicemos primero un nodo de lista vinculada en Java.
Como ya se mencionó, una lista vinculada consta de nodos. Por lo tanto, en Java, podemos representar una LinkedList como una clase con su Nodo como una clase separada. Por lo tanto, esta clase tendrá una referencia al tipo de nodo.
Esto se muestra a continuación:
|_+_|Para crear un objeto de tipo LinkedList, hay dos constructores principales como sigue:
# 1) LinkedList ()
La sintaxis general de este constructor es:
|_+_|La declaración anterior crea una LinkedList vacía.
Por ejemplo,
|_+_|Esto creará una lista enlazada vacía llamada l_list.
# 2) LinkedList (Colección c)
La sintaxis general es:
|_+_|La declaración anterior crea una LinkedList con elementos de la colección c como sus elementos iniciales.
Como otras estructuras de datos de lista que ya hemos visto, la lista enlazada también se puede inicializar usando el método add, método Arrays.asList () o usando el constructor con la colección como argumento.
Implementación de listas vinculadas en Java
A continuación se muestra un ejemplo simple de una estructura de datos LinkedList en Java. En este ejemplo de implementación, usaremos el método add y el método asList para inicializar los objetos LinkedList.
|_+_|Producción:
Contenido de la primera LinkedList: (10, 20, 30, 40, 50)
Contenido de la segunda LinkedList: (rojo, verde, azul, cian, magenta)
El programa anterior muestra la creación e inicialización de LinkedList. Primero, creamos una LinkedList de tipo Integer y proporcionamos una matriz de Integers convertidos a lista usando el método asList como valores iniciales para LinkedList.
A continuación, creamos una LinkedList vacía de tipo String y luego, usando el método add, agregamos valores a LinkedList.
Finalmente, mostramos ambos objetos LinkedList como una cadena.
Lista enlazada de impresión / desplazamiento en Java
Para imprimir el contenido o realizar cualquier operación sobre los elementos de la LinkedList, es necesario recorrer sus elementos. Ya hemos visto estos métodos en nuestros tutoriales anteriores. En esta sección, discutiremos los ejemplos de cada uno con respecto a LinkedList.
Usando for loop
|_+_|Producción:
Elementos LinkedList que usan for loop:
rojo verde azul
Uso de forEach Loop
|_+_|Producción:
Elementos LinkedList usando forEach loop:
rojo verde azul
Utilizando Iterator
|_+_|Producción:
El contenido de la lista vinculada:
Rojo verde azul amarillo
como hacer un programa ddos
Métodos LinkedList
La clase LinkedList proporciona una API que admite varios métodos para manipular la lista vinculada. Hemos tabularizado los métodos en LinkedList API a continuación.
Discutiremos las operaciones / métodos principales en la siguiente sección.
| Método | Prototipo | Descripción |
|---|---|---|
| Claro | vacío claro () | Elimina todos los elementos de la lista. |
| Agregar | suma booleana (E e) | Agregar un elemento especificado a LinkedList |
| añadir vacío (índice int, elemento E) | Agregar elemento en el índice dado en LinkedList | |
| Añadir todo | boolean addAll (Colección c) | Agrega los elementos de la colección c dada al final de LinkedList. |
| boolean addAll (índice int, colección c) | Agrega los elementos de la colección c dada en el índice especificado en LinkedList | |
| addFirst | anular addFirst (E e) | Agregue el elemento dado como el primer elemento a LinkedList. |
| addLast | vacío addLast (E e) | Agregue el elemento dado al final de la lista. |
| Clon | Clonar objeto () | Hace una copia superficial de LinkedList |
| Contiene | Booleano contiene (Objeto o) | Comprueba si la lista contiene elementos especificados; si es así, devuelve verdadero. |
| descendingIterator | Iterador descendingIterator () | Devuelve un iterador de orden inverso para LinkedList. |
| Elemento | Elemento E () | Devuelve el elemento al principio de la lista. |
| Obtener | E get (índice int) | Obtiene el elemento en el índice especificado. |
| getFirst | E getFirst () | Recupera el primer elemento de LinkedList. |
| obtener ultimo | E getLast () | Recupera el último elemento de LinkedList. |
| índice de | Int indexOf (Objeto o) | Busque el índice de la primera aparición de los elementos dados en la lista y devuelva el índice. -1 si no se encuentra el elemento. |
| lastIndexOf | Int lastIndexOf (Objeto o) | Devuelve la posición de la última aparición del elemento dado en LinkedList; -1 si el elemento dado no está presente |
| listIterator | ListIterator listIterator (índice int) | Devuelve el listIterator del índice especificado en la lista vinculada. |
| Oferta | oferta booleana (E e) | Agrega el elemento dado como último elemento (cola) en LinkedList. |
| oferta primero | Oferta booleana Primero (E e) | Agrega el elemento dado como el primer elemento en la LinkedList. |
| ofertaÚltima | Oferta booleana Última (E e) | Agregue el elemento e dado al final de LinkedList. |
| Ojeada | E mirar () | Devuelve el encabezado de la lista sin eliminarlo. |
| peekFirst | E peekFirst () | Devuelve el primer elemento de la lista. devuelve nulo si la lista está vacía. |
| peekLast | E peekLast () | Devuelve el último elemento o nulo si la lista está vacía. No elimina el elemento. |
| Encuesta | Encuesta E () | Devuelve el encabezado de LinkedList y también lo elimina. |
| pollFirst | E pollFirst () | Devuelve y elimina el primer elemento de la lista; devuelve nulo si la lista está vacía. |
| pollLast | E pollLast () | Devuelve y elimina el último elemento de la lista; devuelve nulo si la lista está vacía. |
| Pop | E pop () | Saca el elemento de la representación de pila de LinkedList. |
| Empujar | Empuje vacío (E e) | Inserta o inserta un elemento en la representación de pila de LinkedList. |
| Eliminar | E eliminar () | Elimina y devuelve el encabezado de LinkedList. |
| E eliminar (índice int) | Elimina el elemento en el índice dado de LinkedList. | |
| boolean eliminar (Objeto o) | Elimina la primera aparición del elemento dado de LinkedList. | |
| removeFirst | E removeFirst () | Devuelve y elimina el primer elemento de la lista. |
| removeFirstOccurence | booleano removeFirstOccurrence (Objeto o) | Elimina la primera aparición del elemento dado de la lista cuando la lista se recorre de principio a fin. |
| removeLast | E removeLast () | Devuelve el último elemento de LinkedList y también lo elimina. |
| removeLastOccurence | booleano removeLastOccurrence (Objeto o) | Elimina la última aparición del elemento dado de LinkedList cuando se atraviesa de principio a fin |
| Colocar | E conjunto (índice int, elemento E) | Establece el elemento dado en el índice dado. Reemplaza el elemento actual por nuevo. |
| Tamaño | Tamaño int () | Devuelve el tamaño o la cantidad de elementos en LinkedList |
| toArray | Objeto () toArray () | Convierte LinkedList en una matriz que contiene todos los elementos de la lista en la secuencia adecuada |
| T () toArray (T () a) | Convierte LinkedList en una matriz con el mismo tipo de tiempo de ejecución que el argumento a. |
El siguiente programa Java demuestra los diversos métodos que enumeramos anteriormente.
|_+_|Producción:
Lista vinculada: (A, B, C, D, G, E, F)
Lista vinculada después de agregar el contenido de ArrayList: (A, B, C, D, G, E, F, H, I)
Lista vinculada después de la eliminación: (C, D, E, F, H)
La lista no contiene el elemento 'G'
Tamaño de la lista vinculada = 5
Elemento devuelto por get (): F
Lista vinculada después del cambio: (C, D, E, J, H)
Matriz obtenida de la lista vinculada: (C, D, E, J, H)
El programa anterior demuestra varios métodos de la clase LinkedList. Primero, declaramos una LinkedList de tipo String. Luego usamos varias versiones del método add como add, andFirst, addLast, addAll, etc. para poblar la LinkedList con valores.
Aquí podemos agregar el elemento directamente al final de la lista o agregar el elemento en una posición específica en la lista.
También usamos el método addFirst para agregar un elemento al principio de la lista y addLast para agregar un elemento al final de la lista. Luego realizamos operaciones de eliminación en LinkedList como eliminar, eliminarFirst, eliminarLast, etc.
Para el método de eliminación, podemos especificar el elemento a eliminar o podemos especificar el índice o la posición en la LinkedList en la que se eliminará el elemento. Los métodos removeFirst y removeLast eliminan el primer y último elemento de la lista respectivamente.
Luego buscamos en la lista un elemento en particular usando el método contiene. A continuación, usamos el método size () para recuperar el tamaño o la longitud de LinkedList. Luego usamos métodos get / set para recuperar el valor en un índice particular en la lista y luego reemplazamos un valor en una posición específica en la lista.
Finalmente, convertimos LinkedList en un Array usando el método toArray.
Lista vinculada inversa en Java
Para invertir una lista enlazada en Java, usamos el método 'descendingIterator ()' que devuelve un iterador inverso para la lista. Luego, podemos usar este iterador para recorrer la lista y mostrar elementos.
El siguiente programa invierte la lista enlazada usando el método descendingIterator ().
|_+_|Producción:
Lista vinculada: (Pune, Mumbai, Nagpur)
Lista vinculada en orden inverso:
Nagpur Mumbai Pune
En el programa anterior, declaramos una lista vinculada y luego la imprimimos. Luego obtenemos un iterador inverso y luego recorremos la lista usándolo y mostramos cada elemento. La salida muestra el contenido de la Lista vinculada, primero en el orden en que se agregan los elementos y luego la salida muestra el contenido en orden inverso.
Ordenar una lista vinculada en Java
Los objetos de la clase LinkedList se pueden ordenar mediante el método Collections.sort (). Este método proporciona dos versiones con o sin comparador. Cuando se llama al método Collections.sort () sin un comparador, la colección se ordena en el orden natural.
Cuando el comparador se utiliza con este método, podemos definir nuestros propios criterios de clasificación anulando el método compareTo.
El siguiente programa de Java ordena una LinkedList usando Collections.sort (). Aquí clasificamos las matrices usando el orden natural y también usando un comparador.
|_+_|Producción:
LinkedList original (sin clasificar): (enero, febrero, marzo, abril, mayo, junio)
LinkedList (ordenada en orden natural): (abril, febrero, enero, junio, marzo, mayo)
LinkedList (ordenada mediante Comparador): (abril, febrero, enero, junio, marzo, mayo)
Eliminar duplicados
Para eliminar duplicados, debe atravesar cada nodo y compararlo con el siguiente. Si ambos nodos son iguales, saltamos un nodo y pasamos al siguiente.
De esta manera, después de atravesar todos y cada uno de los nodos y deshacernos de los nodos duplicados, obtendremos la lista resultante que no tiene elementos duplicados.
A continuación se muestra un programa Java para eliminar duplicados.
|_+_|Producción:
Linkedlist original:
1 1 2 3 5 2 1 1
LinkedList después de eliminar duplicados:
1 2 3 5
En el programa anterior, tenemos una clase de lista vinculada creada para eliminar duplicados. También tenemos una clase para definir cada nodo. En otras palabras, los nodos de la lista son los objetos de este nodo de clase. Tenemos un método para agregar el nodo a una lista vinculada.
Luego, en el método removeDuplicate, atravesamos cada nodo en la lista vinculada comenzando desde la cabeza y comparamos cada nodo subsiguiente para el duplicado. Si se encuentra un duplicado, saltamos ese nodo y pasamos al siguiente.
De esta manera, el ist se construye omitiendo los nodos duplicados y la lista modificada se imprime utilizando el método print ().
Lista enlazada circular en Java
Una lista enlazada circular es una lista que tiene su cola o último nodo conectado de nuevo a la cabeza o al primer nodo.
El siguiente diagrama muestra la lista enlazada circular en Java.
Como se muestra en el diagrama anterior, la parte de la dirección del último nodo o cola de la lista vinculada no se establece en nulo. En cambio, apunta hacia el primer nodo o encabezado de la lista, formando así una lista enlazada circular.
El siguiente programa implementa una lista enlazada circular en la que tenemos que manipular nodos individuales de la lista enlazada.
|_+_|Producción:
Nodos de lista enlazados circulares:
10 20 30 40
LinkedList de Java 8
Aunque no se agregaron más características específicamente a la clase LinkedList en Java 8, aún introdujo flujos para manipular datos.
El siguiente programa muestra el uso de la secuencia Java 8 para mostrar LinkedList.
|_+_|Producción:
El contenido de LinkedList:
Red
Verde
Azul
Cian
Magenta
Preguntas frecuentes
P # 1) ¿Cuándo se usa la lista vinculada en Java?
Responder: Como es más rápido que colecciones como ArrayList en operaciones de modificación, debe usarse en aplicaciones que requieren operaciones frecuentes de adición / eliminación. Para aplicaciones que tienen principalmente datos de solo lectura, se pueden usar ArrayList o colecciones similares.
Q #2) ¿Qué es ListNode?
Responder: Un ListNode es una clase básica asociada con una lista enlazada en Java y representa información asociada con un solo elemento o nodo. Cada ListNode consta de datos y un puntero o referencia al siguiente elemento.
Q #3) ¿La lista vinculada permite valores nulos?
Responder: Sí, la lista vinculada permite cualquier número de valores nulos.
Q #4) ¿Cuáles son las ventajas de una lista vinculada?
Respuesta: Algunas de las ventajas son:
¿Cómo abro archivos dat?
- Las operaciones de manipulación como la adición, la eliminación son más rápidas.
- No es necesario preasignar memoria para una lista vinculada y, por lo tanto, se obtiene una utilización eficiente de la memoria.
- Proporciona un tiempo de acceso más rápido y sin sobrecarga adicional de memoria, y se puede ampliar en tiempo constante.
- Es una estructura de datos dinámica
- Crece y se reduce en tiempo de ejecución según los valores agregados o eliminados.
Q #5) ¿Cuál es la aplicación de la lista vinculada?
Respuesta: Se utiliza principalmente en las siguientes aplicaciones:
- Para implementar la funcionalidad 'deshacer' en software como MS-Word, Photoshop, etc.
- Implementar estructuras de datos como pila y cola.
- También podemos implementar gráficos usando una lista vinculada.
- Para el hash de cubos, cada cubeta se puede implementar como una lista vinculada.
Q #6) ¿Cuáles son las limitaciones de una lista vinculada?
Respuesta: Algunas de las limitaciones son:
- Con un puntero adicional para contener la referencia del siguiente elemento en cada nodo, la memoria utilizada es mucho más que matrices.
- Esta es una estructura de datos de acceso estrictamente secuencial, por lo que los nodos de la lista vinculada siempre deben leerse desde el principio.
- Es difícil recorrerlo hacia atrás, especialmente en las listas de enlaces individuales.
- Dado que los nodos se almacenan en ubicaciones no contiguas, el tiempo necesario para el acceso puede ser elevado.
Conclusión
En este tutorial, hemos aprendido la estructura básica de datos de listas vinculadas. Luego pasamos a la clase java.util.LinkedList proporcionada en Java. Discutimos esta clase en detalle, incluidos sus constructores, métodos, etc.
También hemos discutido algunas operaciones especiales relacionadas con las listas vinculadas, como ordenar, invertir una lista, eliminar duplicados, listas vinculadas circulares, etc.
En nuestro próximo tutorial, discutiremos características específicas de la lista doblemente enlazada.
=> Consulte la guía completa de formación de Java aquí.
Lectura recomendada
- Lista doblemente enlazada en Java: implementación y ejemplos de código
- Lista de Java: cómo crear, inicializar y usar la lista en Java
- Métodos de lista de Java: ordenar lista, contener, agregar lista, eliminar lista
- Algoritmo de búsqueda binaria en Java: implementación y ejemplos
- Orden de inserción en Java: algoritmo de ordenación de inserción y ejemplos
- Tutorial de interfaz Java y clase abstracta con ejemplos
- Estructura de datos de lista vinculada en C ++ con ilustración
- Lista encubierta para matriz y otras colecciones en Java