LinkedList - perché non diretta .next () sugli elementi?

Naviga le tue risposte
3

Non l'ho mai capito: perché non riesco a trovare una API di raccolte di base da qualche parte che mi consenta di recuperare elementi che hanno un metodo diretto .next () o .previous () su di essi senza tutto il boilerplate o dover implementare la mia versione di LinkDList. Il vantaggio? Posso scorrere direttamente i miei elementi restituiti senza la necessità di un iteratore, il che mi sembra un possibile motivatore principale di avere una LinkedList in primo luogo. 

class Link { ... }
LinkedList<Link> linksByPosition = ...
Map<String,Link> linksByName = ...
Link linkWithName = linksByName.get("name");
Link nextLink = ??? // Do you get how complex it is?

Riesci a capire quanto sia complesso il ??? ? Devo considerare una scansione di ogni elemento per trovare quello corrispondente prima di sapere in che posizione si trova, prima che possa ottenere il prossimo ...

Ora considera questa forma modificata, con un SmarterLinkedList che mi restituisce le implementazioni di un LinkdListNode predefinito. 

class Link extends AbstractLinkedListNode<Link> { ... }
SmarterLinkedList<Link> linksByPosition = ...
Map<String,Link> linksByName = ...
Link linkWithName = linksByName.get("name");
Link nextLink = linkWithName.next();

Se internamente, sta già monitorando il collegamento, perché non vorresti esporre quella parte dell'API allo sviluppatore? Mi sembra infinitamente utile?

Ora diciamo, renderò i requisiti un po 'più complessi, ora voglio anche aggiungere un elemento subito dopo quello che sto tenendo. Nella prima versione del codice, mentre cerco il Link corrispondente, posso anche mantenere un indice quindi so a che punto inserire. In questo modo posso chiamare il metodo LinkedList.add(index+1,newLink) . Sai cosa sta facendo dietro le quinte, giusto? Sì, internamente, di nuovo itera alla giusta posizione index+1 volte finché non raggiunge la posizione corretta per l'inserimento.

Tuttavia se LinkedListNode mi richiede anche di esporre i metodi per insertAfter , insertBefore , removeSelf ... lo rende più potente, vero?

UPDATE

Sembra già che il consenso sarà "implementare uno tuo". Ma sto pensando che "codice troppo generico" può essere evitato senza rischiare eccessivamente esponendo gli interiora della gestione dei nodi.

Spero che alla fine qualcuno inciamperà su questo, e dimmi che c'è qualcosa che lo offre esattamente.

    
posta YoYo 11.03.2016 - 04:09
fonte

1 risposta

12

È esposto.

Questo è un Iterator .

Tuttavia, esporre le componenti interne dell'implementazione interrompe l'incapsulamento della classe. Il modo in cui è implementato è sotto le copertine - singolarmente collegate, doppiamente collegate, dequeue (incidentalmente, l'implementazione è cambiata da Java 1.5 a 1.6 con l'aggiunta dell'interfaccia Deque ), accessibile dallo stream (leggermente modificata di nuovo tra 1.6 e 1.8) .

L'iteratore è esposto. Se vuoi iterare su questo, è lì. Se vuoi implementare la tua lista collegata (e ho in passato proprio per questo motivo - essere in grado di accedere alla rappresentazione sottostante e lavorare con essa), non è quella difficile da fare.

Fornire accesso alla classe Node (o Entry a seconda della versione di Java) sottostante significherebbe che la stessa LinkedList potrebbe entrare in uno stato incoerente. In particolare, LinkedList conosce gli elementi di inizio e fine. Ha la capacità di rimuovere prima, rimuovere l'ultimo, ottenere l'ultimo, ottenere prima e così via (tutta la parte del deque). Fornire l'accesso al nodo significherebbe che qualcun altro potrebbe scollegare la testata, o modificare la dimensione (size () in LinkedList restituisce un valore - non contando tutti i nodi).

Se non sai dove si trova la fine della lista, add(E e) (aggiungi alla fine della lista) diventa O (n) invece di O (1). Se non sai quanto è grande l'elenco tramite l'accesso tramite LinkedList.add (E e), il metodo size () diventa O (n) piuttosto che O (1). Queste sono garanzie importanti su come funziona la Lista.

Poi c'è anche il problema di sincronizzare la lista. Questo può essere fatto limitando i metodi aggiungi e rimuovi tipi sulla lista stessa. Fornire l'accesso alla classe sottostante e tutte le garanzie su come la sincronizzazione lavora fuori dalla finestra perché non si controlla più la sincronizzazione di aggiungere e rimuovere su ciascun elemento.

    
risposta data 11.03.2016 - 04:24
fonte

Leggi altre domande sui tag

Come faccio a gestire i membri ereditati non necessari? Dal punto di vista dello sviluppo del ciclo di vita del software, il dattilografia è un vantaggio o un problema?