Lista de enlaces java
Después de repasar diferentes tutoriales sobre Listas Enlazadas estoy viendo que algunos mencionan la clase Java Node para enlazar con los nodos anteriores y siguientes y otros no la utilizan en absoluto al crear una LinkedList.
Digamos que tenemos una lista de estudiantes. La responsabilidad natural de cada objeto Student es tener (“conocer”) la información de contacto del estudiante, los cursos en los que está matriculado, las calificaciones obtenidas, etc. No es responsabilidad natural de un objeto Estudiante saber que forma parte de una lista enlazada, por no hablar de si esa lista está simple o doblemente enlazada. Para esta responsabilidad tenemos la clase Node.
El diseño con la clase Node tiene además la ventaja potencial de que se puede diseñar y codificar una lista enlazada genérica y utilizarla para instanciar una lista de estudiantes, una lista de profesores, una lista de cursos, etc. Stephen C en la otra respuesta menciona otras ventajas.
Antecedentes históricos: Donde yo aprendí estructuras de datos alrededor de 1980, dotábamos a cada registro de estudiantes de un puntero siguiente. (Aprendimos las listas enlazadas simples. Las listas doblemente enlazadas sólo se mencionaban de pasada). Lo que hoy en día se considera un diseño pobre. Esperaba que hace tiempo que había dejado de usarse.
Recorrer una lista enlazada java
Una estructura de datos lineal utilizada para almacenar los elementos en ubicaciones contiguas se denomina lista enlazada en Java. Tiene direcciones y punteros que se utilizan para enlazar los elementos, y cada elemento de la lista enlazada consta de dos partes, a saber, la parte de datos y la parte de direcciones. La parte de datos es el valor del elemento, y la parte de direcciones consiste en los punteros y direcciones que se utilizan para enlazar los elementos. Cada elemento de la lista se denomina nodo.
La lista enlazada extiende a la Lista Secuencial Abstracta, que a su vez implementa una lista que extiende la interfaz collection, que a su vez extiende la interfaz Iterable. La lista enlazada implementa la interfaz deque extiende la interfaz Queue, que a su vez extiende la interfaz collection, que a su vez extiende la interfaz Iterable.
Es el tipo de lista enlazada que consiste en una secuencia de nodos donde cada nodo consiste en datos y un enlace al siguiente nodo y el último nodo de la lista (también llamado cola) que apunta al primer nodo de la lista (también llamado cabeza) se llama como Lista Enlazada Circular.
Linkedlist java реализация
Si no tenemos una referencia a la cola de la primera lista, entonces es un tiempo O(n) donde n es la longitud de la primera lista, pero lo importante es que el paso en el que sumamos las dos listas enlazadas consta de 1 paso (enlazar la cola de la primera lista con la cabeza de la segunda)
Esto no es cierto en general para las estructuras de datos de listas que están encapsuladas dentro de una API, como LinkedList. En el caso de las listas encapsuladas, la API determinará si esto es posible. Para LinkedList no es posible. Las APIs no lo permiten…
Sin embargo, se podría diseñar un ADT en el que fuera posible el empalme de listas O(1). La “pega” es que cuando se empalma la segunda lista al final de la primera, ya no es una lista de “primera clase”. La semántica es más difícil de razonar; por ejemplo, la segunda lista puede cambiar como resultado de operaciones en la primera. No todas las operaciones la modifican. (Este tipo de cosas es la razón por la que las implementaciones de listas estándar de Java no soportan el empalme).
Tampoco es cierto en general para las listas no encapsuladas. Por ejemplo, si (sólo) tienes las cabezas de dos listas enlazadas individualmente, necesitas atravesar la cola de la primera lista antes de poder empalmar la segunda con el final de la misma. El empalme es O(1) pero obtener la cola de la primera lista es O(N).
Lista doblemente enlazada
Introducción a la Lista Enlazada en JavaMuchas veces es posible que no sepamos el número de elementos que se almacenarán en el array o que no tengamos suficiente memoria contigua para inicializar el array. Una lista enlazada es una estructura de datos lineal en la que cada elemento se almacena como un objeto en posiciones de memoria no contiguas. Cada objeto almacena dos cosas, una es el dato y la segunda es la ubicación de memoria del siguiente o anterior o la dirección del siguiente y anterior objeto. Como su nombre indica, una lista enlazada significa que varios objetos están vinculados entre sí para actuar como una estructura de datos lineal. El primer objeto de la lista enlazada se conoce como la cabeza y el último objeto se conoce como la cola de la lista enlazada:
Crear una Lista Enlazada en JavaAhora debes haber entendido que necesitamos un objeto para cada elemento. Así que antes de inicializar el objeto, debemos declarar una clase. Vamos a nombrar esta clase como Node y esta clase tendrá dos miembros de datos, uno es los datos y el segundo es la ubicación del siguiente nodo.class Main {
