makigas - listas enlazadas en java explicacion

La complejidad del tiempo de la lista enlazada para sus operaciones

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Cuál es la complejidad de tiempo de LinkedList.getLast () en Java? 5 respuestas

Estoy implementando una lista vinculada en términos del programa de mercado de valores.

Tiene y operación - Comprar

Para Comprar el código es

//Stocks is a linked List like so 
//LinkedList<Integer> stocks = new LinkedList<Integer>();
public void buy(int q, int p) {
    stocks.addLast(q); //add number of stocks
    stocks.addLast(p); //for i stocks i +1 = price of stock
}

Esta operación addLast es para una lista vinculada. Obviamente, se agrega el elemento dado a una nueva posición al final de una lista actual.

Entonces, por ejemplo, si tengo una lista que tiene, digamos, los siguientes datos

//Stock, price, stock, price etc...
[100, 50, 5000, 30, 8000, 60]

Si addLast es la búsqueda de la Lista Enlazada para el último elemento y luego se agrega y, por lo tanto, la complejidad del tiempo sería O (n) (en términos de Big Oh solamente). ¿O se está indexando al final de la lista, al darse cuenta de que el final de la lista es decir stocks[5] luego insertar un nuevo nodo que haga referencia a los nuevos datos al final de la lista?

Entonces mi pregunta es, ¿es la operación addLast() para una complejidad de tiempo de lista enlazada de O (n) u O (1)?

Publique a continuación para cualquier aclaración

Answer 1

Al addLast la fuente de la clase LinkedList, parece que addLast realmente llama a un método llamado linkLast que es:

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

La parte relevante es donde se declara last en el transient Node<E> last; clase transient Node<E> last; parece que la clase tiene un "puntero" al último nodo. Luego se actualiza con el nuevo nodo dado. Entonces, debería ser O (1) independientemente del tamaño de la lista.

Answer 2

La complejidad de add() o addLast() es O(1) en la longitud de la lista. Esto es obvio al leer el código fuente LinkedList .

(Dado que este aspecto del comportamiento no se especifica precisamente en el javadoc ¹ , podría cambiarse ... en teoría. Sin embargo, podemos excluir con confianza esta posibilidad. Incluso si tenía sentido (¡y no es así!), Tales un cambio rompería muchas, muchas aplicaciones existentes. Eso solo es razón suficiente para descartarlo como no plausible).

^{1 - Argumentaría que la oración javadoc "[o] peraciones que indexan en la lista atravesará la lista desde el principio o el final, lo que esté más cerca del índice especificado" no se aplica inequívocamente a este método. Podría argumentar que el método add / addLast no se indexa en la lista.}

Answer 3

Si lee el javadoc para la clase LinkedList, indica: "Todas las operaciones funcionan como se podría esperar para una lista doblemente enlazada. Las operaciones que se indexan en la lista atravesarán la lista desde el principio hasta el final , lo que esté más cerca. al índice especificado ".

Esto significa que es O (1)

Editar

Si desea una mejor implementación de su nombre de archivo, lista de precios, creo que sería mejor crear una clase que contenga la descripción de las existencias:

public class Stock {
    private int stockName;
    private int stockPrice;

    // other methods, properties, constructor
}

Y luego crea una LinkedList<Stock>