Mappage d'arborescences aux nœuds de liste liée

Question

Je souhaite être en mesure d'accéder à un certain nœud dans ma liste Doublement Liée en O (1) fois. Je sais que si je traverse la liste pour trouver un certain noeud, cela prendra du temps O (n) donc je veux mapper les noeuds à une liste de tableau où je peux accéder aux noeuds en O (1) fois. Je ne sais pas très bien comment je ferais ce mapping. Je voudrais voir un exemple de comment cela peut être fait.

Editer: Je voudrais pouvoir accéder à n'importe quel nœud de la liste chaînée afin de pouvoir déplacer les nœuds en O (1) fois. Exemple: Déplacer le nœud avec l'ID 5 à la fin de la liste en O (1) temps.

Edit 2: J'uploadé un exemple d'image de ce que je suis en train d'accomplir

Answer 1

Vous ne pouvez pas faire cela avec les structures de données intégrées ArrayList et LinkedList.

En général, il est pas possible du tout d'avoir deux

• O (1) d'indexation (par position dans la liste)
• O (1) l'élimination/ajout/déplacement dans toute la liste.

Les possibilités:

• Vous pouvez accéder à O (log (N)) pour ces deux si vous utilisez une structure arborescente.
• Vous pouvez accéder à O (1) pour l'indexation avec une structure basée sur un tableau, mais la suppression/ajout au milieu prend O (n).
• Vous pouvez utiliser une structure similaire à Hash-Map en ajoutant/supprimant dans O (1), mais elle n'autorise que l'accès O (1) par clé, pas l'accès par index (autre que itération, ie O (n)) .(Cela signifie que si vous ajoutez/supprimez quelque chose au milieu, les index après cela ne changeront pas.)

Même si vous essayez de combiner une liste chaînée avec un tableau, vous aurez O (n) pour supprimer/ajouter (puisque vous devez encore mettre à jour le tableau).

---

D'accord, avec votre image ajoutée pour montrer ce que vous voulez, c'est faisable. Vous réimplémentez en fait quelque chose comme LinkedHashMap, mais seulement avec des clés entières consécutives et avec la possibilité de manipuler la partie "Linked".

Si votre liste liée est constituée d'objets Node, vous aurez un ArrayList<Node>.

Vous n'ajouteriez des éléments à ArrayList que lors de l'ajout de nouveaux nœuds à la liste liée, sinon, utilisez ArrayList uniquement pour la recherche.

Voici un exemple:

class FastIndexLinkedIntList<X> { 
    class Node { 
     Node next; 
     Node prev; 
     int key; 
     X value; 
     Node(int key, X val) { this.key = key; this.value = val; } 
    } 

    ArrayList<Node> indexedNodes = new ArrayList<Node>(); 
    Node head; 
    Node tail; 


    public void add(X value) { 
     int key = indexedNodes.size(); 
     Node node = new Node(key, value); 
     insertAtEnd(node); 
     indexedNodes.add(node); 
    } 

    private void insertAtEnd(Node n) { 
     if(tail == null) { 
     assert head == null; 
     head = n; 
     tail = n; 
     return; 
     } 
     n.prev = tail; 
     n.next = null; 
     tail.next = n; 
     tail = n; 
    } 

    private void removeNode(Node n) { 
     if(n.next == null) { 
     assert n == tail; // last node 

     tail = n.prev; 
     tail.next = null; 
     } 
     else { 
     n.next.prev = n.prev; 
     } 

     if(n.prev == null) { 
     assert n == head; // first node 

     head = n.next; 
     head.prev = null; 
     } 
     else { 
     n.prev.next = n.next; 
     } 
    } 

    public void moveNodeToEnd(int key) { 
     Node n = indexedNodes.get(key); 
     removeNode(n); 
     insertAtEnd(n); 
    } 

} 

Vous pouvez ajouter d'autres opérations ici, mais ceux-ci suffisent pour l'exemple dans la question:

FastIndexedLinkedList<String> ll = new FastIndexedLinkedList<String>(); 
ll.add("0"); 
ll.add("1"); 
ll.add("2"); 
ll.add("3"); 
ll.moveNodeToEnd(2); 

Answer 2

Je ne suis pas tout à fait sûr de votre objectif, vous souhaitez simplement récupérer l'index de l'objet dans O (1)?

Voici comment cela ressemblerait:

LinkedList<Object> aList; // your LinkedList 
Map<Object, Integer> mapper = new HashMap<Object, Integer>(); 
Object[] arr = aList.toArray(); 
for(int i = 0; i < arr.length; i++){ 
    mapper.put(arr[i], i); 
} 

Maintenant, si vous voulez trouver un objet dans votre liste, ce que vous faites est d'obtenir son indice de l'objet mappeur avec

mapper.get(o); 

================================

Re: modifier votre

Vous ne pouvez pas (ou il y a non e dont je suis conscient). Vous exigez essentiellement le meilleur des deux mondes (listes chaînées et tableaux).

Answer 3

Utilisez la méthode toArray() pour convertir votre LinkedList à un tableau pour la récupération à temps constant:

LinkedList.toArray(arr)

Answer 4

LinkedHashMap: fournit O (1) le temps et les clés sont liste doublement chaînée ordonnée.