Similar a las matrices en Java, LinkedList es una estructura de datos lineal. Sin embargo, los elementos LinkedList no se almacenan en ubicaciones contiguas como matrices, están vinculados entre sí mediante punteros. Cada elemento de LinkedList tiene la referencia (dirección / puntero) al siguiente elemento de LinkedList.
Resumen
1. Representación LinkedList
2. ¿Por qué necesitamos una lista vinculada?
3. Jerarquía de la clase LinkedList en Java
4. Ejemplo de una lista enlazada de Java para agregar elementos
5. Ejemplo de una lista enlazada de Java para eliminar elementos
6. Ejemplo de LinkedList en Java
7. Métodos de la clase LinkedList
8. Tutorial de LinkedList: todos los métodos de la clase LinkedList se tratan en detalle en tutoriales separados
Representación LinkedList
Cada elemento de LinkedList se llama Nodo. Cada nodo de LinkedList contiene dos elementos: 1) Contenido del elemento 2) Puntero / Dirección / Referencia al siguiente nodo de LinkedList.
Así es como se ve una LinkedList:
Nota:
1. Cabeza de LinkedList contiene solo la dirección del Primer elemento de la lista.
2. El último elemento de LinkedList contiene nulo en la parte del puntero del nodo porque es el final de la lista, por lo que no apunta a nada como se muestra en el diagrama anterior.
3. El diagrama que se muestra arriba representa un lista vinculada individualmente. Hay otra variante de tipo complejo de LinkedList que se llama lista doblemente enlazada, el nodo de una lista doblemente enlazada contiene tres partes: 1) Puntero al nodo anterior de la lista enlazada 2) contenido del elemento 3) puntero al siguiente nodo de la lista enlazada.
¿Por qué necesitamos una lista vinculada?
Debe tener en cuenta las matrices que también son una estructura de datos lineal pero las matrices tienen algunas limitaciones como:
1) El tamaño de la matriz es fijo. que se decide cuando creamos una matriz, por lo que es difícil predecir la cantidad de elementos de antemano, si el tamaño declarado es menor, no podemos aumentar el tamaño de una matriz y si declaramos una matriz grande y no es necesario almacenar tantos elementos, entonces es una pérdida de memoria.
2) Elementos de matriz necesitan ubicaciones de memoria contiguas para almacenar sus valores.
3) Insertar un elemento en una matriz es costoso en términos de rendimiento. ya que tenemos que mover varios elementos para hacer un espacio para el nuevo elemento. Por ejemplo:
Digamos que tenemos una matriz que tiene los siguientes elementos: 10, 12, 15, 20, 4, 5, 100, ahora si queremos insertar un nuevo elemento 99 después del elemento que tiene valor 12 entonces tenemos que mover todos los elementos posteriores a las 12 a su derecha para dejar espacio para el nuevo elemento.
igualmente eliminar un elemento de la matriz también es una operación costosa en términos de rendimiento porque todos los elementos después del elemento eliminado deben moverse hacia la izquierda.
Estas limitaciones se manejan en la lista vinculada proporcionando la siguiente funcionalidad:
1. La lista vinculada permite asignación de memoria dinámica, lo que significa que la asignación de memoria la realiza el compilador en tiempo de ejecución y no es necesario mencionar el tamaño de la lista al declarar la lista vinculada.
2. Elementos de la lista vinculada no necesitan ubicaciones de memoria contiguas porque los elementos están vinculados entre sí utilizando la parte de referencia del nodo que contiene la dirección del siguiente nodo de la lista.
3. Las operaciones de inserción y eliminación en la lista vinculada no son costosas en términos de rendimiento porque agregar y eliminar un elemento de la lista vinculada no requiere mover el elemento, solo el puntero del nodo anterior y siguiente requiere modificación.
Jerarquía de clases LinkedList en Java
Ejemplo de lista enlazada de Java para agregar elementos
En el siguiente ejemplo estamos usando add()
, addFirst()
es addLast()
métodos para agregar elementos a las ubicaciones deseadas en LinkedList, hay muchos métodos útiles en la clase LinkedList que mencioné al final de este artículo.
package com.beginnersbook; import java.util.*; public class JavaExample{ public static void main(String args[]){ LinkedList<String> list=new LinkedList<String>(); //Adding elements to the Linked list list.add("Steve"); list.add("Carl"); list.add("Raj"); //Adding an element to the first position list.addFirst("Negan"); //Adding an element to the last position list.addLast("Rick"); //Adding an element to the 3rd position list.add(2, "Glenn"); //Iterating LinkedList Iterator<String> iterator=list.iterator(); while(iterator.hasNext()){ System.out.println(iterator.next()); } } }
Producción:
Ejemplo de Java de eliminación de elementos de LinkedList
En el siguiente ejemplo, estamos viendo los pocos populares eliminar métodos en LinkedList que se utilizan para eliminar elementos de determinadas ubicaciones en LinkedList. La explicación detallada de estos métodos junto con los ejemplos se cubren en tutoriales separados, los enlaces se proporcionan al final de este artículo.
package com.beginnersbook; import java.util.*; public class JavaExample{ public static void main(String args[]){ LinkedList<String> list=new LinkedList<String>(); //Adding elements to the Linked list list.add("Steve"); list.add("Carl"); list.add("Raj"); list.add("Negan"); list.add("Rick"); //Removing First element //Same as list.remove(0); list.removeFirst(); //Removing Last element list.removeLast(); //Iterating LinkedList Iterator<String> iterator=list.iterator(); while(iterator.hasNext()){ System.out.print(iterator.next()+" "); } //removing 2nd element, index starts with 0 list.remove(1); System.out.print("nAfter removing second element: "); //Iterating LinkedList again Iterator<String> iterator2=list.iterator(); while(iterator2.hasNext()){ System.out.print(iterator2.next()+" "); } } }
Producción:
Ejemplo de LinkedList en Java
import java.util.*; public class LinkedListExample { public static void main(String args[]) { /* Linked List Declaration */ LinkedList<String> linkedlist = new LinkedList<String>(); /*add(String Element) is used for adding * the elements to the linked list*/ linkedlist.add("Item1"); linkedlist.add("Item5"); linkedlist.add("Item3"); linkedlist.add("Item6"); linkedlist.add("Item2"); /*Display Linked List Content*/ System.out.println("Linked List Content: " +linkedlist); /*Add First and Last Element*/ linkedlist.addFirst("First Item"); linkedlist.addLast("Last Item"); System.out.println("LinkedList Content after addition: " +linkedlist); /*This is how to get and set Values*/ Object firstvar = linkedlist.get(0); System.out.println("First element: " +firstvar); linkedlist.set(0, "Changed first item"); Object firstvar2 = linkedlist.get(0); System.out.println("First element after update by set method: " +firstvar2); /*Remove first and last element*/ linkedlist.removeFirst(); linkedlist.removeLast(); System.out.println("LinkedList after deletion of first and last element: " +linkedlist); /* Add to a Position and remove from a position*/ linkedlist.add(0, "Newly added item"); linkedlist.remove(2); System.out.println("Final Content: " +linkedlist); } }
Producción:
Linked List Content: [Item1, Item5, Item3, Item6, Item2] LinkedList Content after addition: [First Item, Item1, Item5, Item3, Item6, Item2, Last Item] First element: First Item First element after update by set method: Changed first item LinkedList after deletion of first and last element: [Item1, Item5, Item3, Item6, Item2] Final Content: [Newly added item, Item1, Item3, Item6, Item2]
Métodos de la clase LinkedList:
Aquí he mencionado la breve descripción de los métodos de LinkedList, he cubierto cada uno de estos métodos en tutoriales separados, los enlaces se proporcionan al final de este artículo.
Para todos los ejemplos de los siguientes métodos, considere llistobj
como referencia para LinkedList<String>
.
LinkedList<String> llistobj = new LinkedList<String>();
1) suma booleana (objeto objeto): Agrega el elemento al final de la lista.
llistobj.add("Hello");
Agregaría la cadena “Hola” al final de la lista vinculada.
2) añadir vacío (índice int, objeto objeto): Agrega un elemento al índice dado de la lista.
llistobj.add(2, "bye");
Esto agregará la cadena “bye” a la 3ª posición (el índice 2 es la 3ª posición ya que el índice comienza con 0).
3) boolean addAll (Colección c): Agrega todos los elementos de la colección c especificada a la lista. Lanza NullPointerException si la colección especificada es nula. Considere el siguiente ejemplo:
LinkedList<String> llistobj = new LinkedList<String>(); ArrayList<String> arraylist= new ArrayList<String>(); arraylist.add("String1"); arraylist.add("String2"); llistobj.addAll(arraylist);
Este fragmento de código agregaría todos los elementos de ArrayList a LinkedList.
4) boolean addAll (índice int, colección c): Agrega todos los elementos de la colección c a la lista comenzando desde un índice dado de la lista. Lanza NullPointerException si la colección c es nula e IndexOutOfBoundsException cuando el índice especificado está fuera de rango.
llistobj.add(5, arraylist);
Agregaría todos los elementos de ArrayList a LinkedList comenzando en la posición 6 (índice 5).
5) void addFirst (objeto objeto): Agrega el elemento (o elemento) a la primera posición de la lista.
llistobj.addFirst("text");
Agregaría la cadena “texto” al principio de la lista.
6) void addLast (objeto objeto): Inserta el elemento especificado al final de la lista.
llistobj.addLast("Chaitanya");
Esta declaración agregará una cadena “Chaitanya” a la posición final de la lista vinculada.
7) vacío claro (): Elimina todos los elementos de una lista.
llistobj.clear();
8) Clonar objeto (): Devuelve la copia de la lista.
Por ejemplo, My linkedList tiene cuatro elementos: texto1, texto2, texto3 y texto4.
Object str= llistobj.clone(); System.out.println(str);
Salida: La salida del código anterior sería:
[text1, text2, text3, text4]
9) booleano contiene (objeto objeto): Comprueba si el elemento especificado está en la lista o no. Si el elemento está presente, devuelve verdadero; de lo contrario, falso.
boolean var = llistobj.contains("TestString");
Verificará si la cadena “TestString” existe en la lista o no.
10) Obtener objeto (índice int): Devuelve el elemento de índice especificado de la lista.
Object var = llistobj.get(2);
Buscará el tercer elemento de la lista.
11) Objeto GetFirst (): Recupera el primer elemento de la lista.
Object var = llistobj.getFirst();
12) Objeto GetLast (): Recupera el último elemento de la lista.
Object var= llistobj.getLast();
13) int indexOf (objeto objeto): Devuelve el índice del elemento especificado.
llistobj.indexOf("bye");
14) int lastIndexOf (objeto objeto): Devuelve el índice de la última aparición del elemento especificado.
int pos = llistobj.lastIndexOf("hello);
La variable entera pos tendrá el índice de la última aparición de la cadena “hola”.
15) Objeto de encuesta (): Devuelve y elimina el primer elemento de la lista.
Object o = llistobj.poll();
dieciséis) Objeto PollFirst (): igual que el método poll (). Elimina el primer elemento de la lista.
Object o = llistobj.pollFirst();
17) PollLast Object (): Devuelve y elimina el último elemento de la lista.
Object o = llistobj.pollLast();
18) Objeto eliminar (): Elimina el primer elemento de la lista.
llistobj.remove();
19) Eliminar objeto (índice int): Elimina el elemento de la lista que está presente en el índice especificado.
llistobj.remove(4);
Eliminará el quinto elemento de la lista.
20) Eliminar objeto (Objeto obj): Elimina el objeto especificado de la lista.
llistobj.remove("Test Item");
21) Objeto RemoveFirst (): Elimina el primer elemento de la lista.
llistobj.removeFirst();
22) Objeto RemoveLast (): Elimina el último elemento de la lista.
llistobj.removeLast();
23) Object removeFirstOccurrence (objeto objeto): Elimina la primera aparición del elemento especificado.
llistobj.removeFirstOccurrence("text");
Eliminará la primera aparición de la cadena “texto” de la lista.
24) Object removeLastOccurrence (objeto objeto): Elimina la última aparición del elemento especificado.
llistobj.removeLastOccurrence("String1);
Eliminará la última aparición de la cadena “String1”.
25) Conjunto de objetos (índice int, objeto objeto): Actualiza el elemento de índice especificado con el valor dado.
llistobj.set(2, "Test");
Actualizará el tercer elemento con la cadena “Prueba”.
26) int tamaño (): Devuelve el número de elementos de la lista.
llistobj.size();
Tutorial sobre LinkedList
Aquí están los tutoriales que compartí en LinkedList.
Conceptos básicos de LinkedList
- Cómo iterar LinkedList
Agregar eliminar
- Agregar un elemento a LinkedList
- Agregar elemento a un índice específico en LinkedList
- Agregar elemento al principio y al final de LinkedList
- Agregar un elemento al comienzo de LinkedList
- Eliminar el primer y último elemento de LinkedList
- Eliminar artículo de índice específico
- Eliminar el elemento especificado de LinkedList
- Eliminar todos los elementos de LinkedList
- Agregar todos los elementos de una lista a LinkedList
Obtener / Buscar
- Obtenga el primer y último elemento de LinkedList
- Obtenga el elemento del índice específico de LinkedList
- Elemento de búsqueda en LinkedList
- Obtenga una sublista de LinkedLists
Iterador / ListIterator
- Ejemplo de iterador LinkedList
- Ejemplo de LinkedList ListIterator
- Iterar una LinkedList en orden inverso
Más tutoriales
- Reemplazar el elemento con un nuevo valor en LinkedList
- Compruebe si existe un elemento en particular en LinkedList
- Clonar una LinkedList en otra LinkedList
- Obtener el índice de la última aparición de un elemento en LinkedList
- LinkedList push () y pop ()
- LinkedList poll (), pollFirst () y pollLast ()
- LinkedList peek (), peekFirst () y peekLast ()
Conversión
- Convertir LinkedList en ArrayList
- Convertir LinkedList en matriz
Diferencias
- LinkedList vs ArrayList