En el artículo anterior, analizamos la implementación subyacente de ArrayList y sabíamos que la implementación subyacente de ArrayList se basa en matrices, por lo que tiene las características de búsqueda rápida y modificación, mientras que la inserción y la deleción lenta. La LinkedList presentada en este artículo es otra implementación de la interfaz de la lista. Su capa subyacente se basa en una lista vinculada bidireccional. Por lo tanto, tiene las características de inserción y eliminación rápidas, mientras que la búsqueda y la modificación lenta. Además, las funciones de colas y pilas se pueden realizar mediante la operación de la lista vinculada bidireccional. La estructura subyacente de Linkedlist se muestra en la figura a continuación.
F representa la referencia del nodo del cabecera, L representa la referencia del nodo de cola, y cada nodo en la lista vinculada tiene tres elementos, a saber, la referencia del nodo hacia adelante (P), el valor del elemento del nodo (E) y la referencia de nodo posterior (n). El nodo está representado por el nodo de clase interna, veamos su estructura interna.
// Nodo Clase interna Nodo de clase estática privada <E> {e item; // elemento nodo <E> Siguiente; // siguiente nodo de nodo <E> prev; // nodo de nodo anterior (nodo <E> previo, e elemento, nodo <e> next) {this.item = element; this.next = siguiente; this.prev = prev; }}El nodo de clase interna es en realidad muy simple, con solo tres variables miembros y un constructor. El elemento representa el valor del nodo, el siguiente es la referencia al siguiente nodo, y previamente es la referencia al nodo anterior. Estos tres valores se pasan a través del constructor. A continuación, echemos un vistazo a las variables y constructores de miembros de LinkedList.
// El número de elementos establecidos se traduce intsule = 0; // El nodo de encabezado hace referencia al nodo transitorio <e> primero; // El nodo de cola hace referencia al nodo transitorio <e> last; // El constructor sin parámetros sin constructor public en LinkedList () {} // el constructor se encuentra en la colección externa pública LinkedList (colección <? Extends e> c) {this ();); addall (c);}LinkedList contiene una referencia al nodo del encabezado y una referencia al nodo de cola. Tiene dos constructores, uno es un constructor sin parámetros y el otro es un constructor que pasa a la colección externa. A diferencia de ArrayList, LinkedList no especifica el constructor de tamaño inicial. Consulte sus métodos para agregar, eliminar, modificar y buscar.
// add (add) public boolean add (e e) {// agregar linklast (e); return true;} // add (insert) public void add (int index, e elemento) {checkpositionIndex (index); if (index == size) {// Agregar linklast (elemento); } else {// insertar linkbefore (elemento, nodo (index)); }} // eliminar (dar índice) public e remove (int index) {// verifique si el subíndice es legal checkelementIndex (índice); return Unlink (nodo (index));} // delete (elemento dado) public boolean remove (objeto o) {if (o == null) {for (nodo <e> x = primero; x! = null; x = x.next) {if (x.item == null) {noink (x); devolver verdadero; }}} else {// Lista de enlaces de tranquilidad para (nodo <e> x = primero; x! = null; x = x.next) {if (o.equals (x.item)) {// eliminar Unlete (x); devolver verdadero; }}} return false;} // cambiar public e set (int index, e element) {// verifique si el subíndice es legal checkelementIndex (índice); // Obtener la referencia del nodo del nodo de subíndice especificado <E> x = nodo (índice); // Obtener el valor del nodo de subíndice especificado E OldVal = X.Item; // Establecer el elemento de nodo en el nuevo valor x.item = elemento; // devuelve el valor anterior return OldVal;} // verifique el público e get (int index) {// verifique si el subíndice es legal checkelementIndex (índice); // devuelve el valor del nodo del nodo de retorno de subíndice especificado (índice) .Item;}El método de agregar elementos en LinkedList es principalmente para llamar a los dos métodos Linklast y LinkBefore. El método Linklast es vincular un elemento detrás de la lista vinculada, y el método LinkBefore es insertar un elemento en el medio de la lista vinculada. El método Eliminar de LinkedList elimina un elemento de la lista vinculada llamando al método Unlink. Echemos un vistazo al código central de las operaciones de inserción y eliminación de la lista vinculada.
// Antes de vincular al nodo especificado void linkbefore (e e, nodo <e> succ) {// Obtener la referencia del nodo anterior del nodo final dado <e> pred = succ.prev; // Crear un nuevo nodo, la referencia del nodo anterior del nuevo nodo apunta al nodo anterior del nodo dado // la referencia del siguiente nodo del nuevo nodo apunta al nodo final dado <e> newnode = nuevo nodo <> (pred, e, succ); // apunte la referencia del nodo anterior del nodo dado al nuevo nodo succ.prev = newnode; // Si el nodo anterior del nodo dado está vacío, significa que el nodo dado es el nodo de encabezado if (pred == null) {// señala la referencia del nodo del encabezado al nuevo nodo primero = newnode; } else {// de lo contrario, apunte a la siguiente referencia del nodo al nuevo nodo pred.next = newnode; } // Agregue el número de elementos establecidos de un tamaño ++; // Agregue el número de modificaciones un ModCount ++; } // Descargue el nodo especificado e Unlink (nodo <e> x) {// Obtenga el elemento del nodo dado el elemento e elemento = x.Item; // Obtenga la referencia al siguiente nodo del nodo del nodo dado <e> next = x.next; // Obtenga la referencia al nodo anterior del nodo final dado <e> prev = x.prev; // Si el nodo anterior del nodo dado está vacío, explicación: El nodo dado es un nodo de encabezado if (prev == null) {// apunte la referencia del nodo del encabezado al siguiente nodo del nodo dado primero = next; } else {// Referencia al nodo sucesor del nodo anterior que apunta al nodo posterior del nodo dado previo.next = next; // Referencia al nodo anterior del nodo dado x.prev = null; } // Si el siguiente nodo del nodo dado está vacío, significa que el nodo dado es un nodo de cola if (next == null) {// apunte la referencia del nodo de cola al nodo anterior del nodo dado último = prev; } else {// Referencia al nodo avanzado del siguiente nodo que apunta al nodo anterior del nodo dado next.prev = prev; x.next = nulo; } // vaciar el elemento del nodo dado x.item = null; // Resta el número de elementos establecidos por tamaño--; // agregar modcount ++; elemento de retorno;} Linkbefore y Onlink son operaciones representativas de nodos de vinculación y nodos desinstalantes. Otros métodos para vincular y desinstalar nodos en ambos extremos son similares, por lo que nos centramos en los métodos de enlace y no unk.
Diagrama de proceso del método LinkBefore:
Diagrama de proceso del método Unlink:
A través de la ilustración anterior, la complejidad del tiempo de las operaciones de inserción y eliminación de la lista vinculada es O (1), y las operaciones de búsqueda y modificación de la lista vinculada requieren atravesar la lista vinculada para ubicar elementos. Ambas operaciones se llaman método Node (INT Index) para localizar elementos para ver cómo localiza elementos a través de subíndices.
// Obtener nodo de nodo <E> nodo (int index) {// Si el índice está en la primera mitad de la lista vinculada, verifique desde el principio if (index <(tamaño >> 1)) {nodo <E> x = primero; for (int i = 0; i <index; i ++) {x = x.next; } return x; } else {// Si el índice está en la segunda mitad de la lista vinculada, verifique desde el nodo final <E> x = último; para (int i = size-1; i> index; i--) {x = x.prev; } return x; }} Al colocar el subíndice, primero determine si se encuentra en la mitad superior o en la mitad inferior de la lista vinculada. Si está en la mitad superior, comience desde el principio, y si es la mitad inferior, comience desde el final. Por lo tanto, la complejidad del tiempo de la operación de buscar y modificar el subíndice es O (n/2). A través del funcionamiento de la lista vinculada bidireccional, también se pueden realizar las funciones de colas de un solo elemento, colas de dos vías y pilas.
Operación de cola unidireccional:
// Obtener el nodo de encabezado public e peek () {nodo final <e> f = primero; return (f == nulo)? null: f.Item;} // Obtener el nodo de encabezado public e element () {return getFirst ();} // Pop up el nodo de encabezado public e enchufe () {nodo final <e> f = primero; return (f == nulo)? NULL: UNLINKFIRST (F);} // Eliminar el nodo del encabezado public e remove () {return removeFirst ();} // Agregar nodo al final de la oferta booleana pública de cola (e e) {return add (e);}Operación de cola de dos vías:
// Agregar oferta pública booleana (e e) {addfirst (e); return true;} // Agregar oferta booleano público (e e) {addlast (e); return true;} // Obtener el nodo de encabezado public e peekFirst () {nodo final <e> f = primero; return (f == nulo)? NULL: F.Item; } // Obtener el nodo de cola public e peeklast () {nodo final <e> l = último; return (l == nulo)? NULL: L.Item;}Operación de pila:
// colocar la pila public void push (e e) {addfirst (e);} // colocar la pila public e pop () {return removeFirst ();} Ya sea que se trate de una cola unidireccional, una cola de dos vías o una pila, en realidad operan en los nodos de cabeza y cola de la lista vinculada. Sus implementaciones se basan en los cuatro métodos: addFirst (), addLast (), removeFirst () y eliminar (). Sus operaciones son similares a LinkBefore () y Unlink (), excepto que uno debe operar en ambos extremos de la lista vinculada, y la otra es operar en el medio de la lista vinculada. Se puede decir que estos cuatro métodos son casos especiales de métodos LinkBefore () y Unlink (), por lo que no es difícil comprender sus implementaciones internas, por lo que no los presentaré aquí. En este punto, nuestro análisis de LinkedList está a punto de terminar, y resumiremos los puntos clave en todo el texto:
1. LinkedList se implementa en función de una lista vinculada de dos vías. Ya sea que se trate de la adición, eliminación, modificación y método de búsqueda o la implementación de colas y pilas, se puede implementar a través de nodos de operación.
2. LinkedList no necesita especificar la capacidad por adelantado, porque según las operaciones de la lista vinculada, la capacidad de la colección aumentará automáticamente con la adición de elementos.
3. La memoria ocupada por la colección después de que LinkedList se elimine se reduce automáticamente, y no hay necesidad de llamar al método Trimtosize () como ArrayList
4. Todos los métodos de LinkedList no están sincronizados, por lo que no es seguro de hilo y debe evitarse en entornos de múltiples subprocesos.
5. El análisis anterior se basa en JDK1.7, y otras versiones tendrán algunas diferencias, por lo que no se puede generalizar.
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.