Java Generika doppelt verknüpfte Liste Swap

Question

http://users.cis.fiu.edu/~weiss/dsaajava3/code/MyLinkedList.java

Link oben zeigt den Code, den ich um ändern möchten Swap-Methode aus der doppelt verknüpften Liste zu haben. Ich entschuldige mich im Voraus, indem ich die URL verwende, da 300 Codezeilen hier nicht gut lesbar sind.


Für die Ausgabe würde Ich mag nur eine einzige Liste Ausgang haben, zum Beispiel:

[ 28 27 **21** 25 24 23 22 **26** 20 0 1 2 3 4 5 6 7 8 ] //(2, 7) swap 

Below mein Versuch ist (Teil des Codes umfassen/ändern zu original):

Swap-Methode:

public AnyType swap(int idx, int idx2) 
{ 
    return swap(getNode(idx), getNode (idx2)); 
} 

private AnyType swap(Node<AnyType> p, Node<AnyType> p2) 
{ 
    Node<AnyType> temp = p; //realize it doesn't work due to linking 
    p = p2; 
    p2 = temp; 

    return p.data; 
} 

Haupt:

class TestLinkedList 
{ 
    public static void main(String [ ] args) 
    { 
    MyLinkedList<Integer> lst = new MyLinkedList<>(); 

    for(int i = 0; i < 10; i++) 
      lst.add(i); 
    for(int i = 20; i < 30; i++) 
      lst.add(0, i); 

    lst.remove(0); 
    lst.remove(lst.size() - 1); 

    lst.swap(2, 7); 
    System.out.println("swap: " + lst); 
    } 
} 

Ausgang

swap: [ 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 ] 
21 

Ich weiß, dass mein Ansatz zur Lösung nicht die Verwendung von verketteten Liste ist. Ich habe den Code analysiert, den ich ändern soll. Allerdings habe ich Schwierigkeiten mit den Zeigern und der doppelt verketteten Liste, um den Kodierungsteil (nicht das Konzept) zu verstehen. Bitte erläutern Sie, wie ich zur Lösung gehen soll. Vielen Dank.

EDIT

/* Swaps idx and idx2 nodes 
* @param idx the index of the object 
* @param idx2 the index of the object 
*/ 
public void swap(int idx, int idx2) 
{ 
    swap(getNode(idx ), getNode (idx2)); 
      if(idx < 0 || idx >= size() || idx2 < 0 || idx2 >= size()){ 
     throw new IndexOutOfBoundsException("swap first index: " + idx + ", second index: " + idx2); 
    } 
} 

/** 
* Swaps node and data at p and p2 
* @param p the index of the object 
* @param p2 the index of the object 
*/ 
public void swap(Node<AnyType> p, Node<AnyType> p2) 
{ 

    Node<AnyType> temp = p; 
    p = p2; 
    p2 = temp; 

    temp = p.next.prev; 
    p.next.prev = p2.next.prev; 
    p2.next.prev = temp;   


    AnyType dataTemp = p.data; 
    p.data = p2. data; 
    p2.data = dataTemp; 
} 

Ausgang

[ 29 28 27 26 25 24 23 22 21 20 0 1 2 3 4 5 6 7 8 9 ] 
swap: [ 29 28 22 26 25 24 23 27 21 20 0 1 2 3 4 5 6 7 8 9 ] 

Es arbeitet jetzt. Habe ich es richtig gemacht? Allerdings bekomme ich einen Kompilierfehler mit. Ich nehme an, es hat mit public void swap(Node<AnyType> p, Node<AnyType> p2) Methode zu tun, die warning: exporting non-public type through public API hat. Was kann ich hier tun, um es zu beheben?

Answer 1

Lassen Sie uns sagen, dass Ihre Eingabe ist:

[ 1 2 3 4 5 6 7 8 9 ]

und Sie möchten 3 tauschen und 7:

[ 1 2 >7< 4 5 6 >3< 8 9 ]

Dies bedeutet, dass Sie alle diese Werte aktualisieren:

2.next = 7 
7.prev = 2 
7.next = 4 
4.prev = 7 
6.next = 3 
3.prev = 6 
3.next = 8 
8.prev = 3 

Das ist eine Summe von 8 Zuweisungen, nicht die Zuweisung zu temporären Variablen zählen.

---

Was passiert, wenn Sie tauschen 5 und 6 statt wollte:

[ 1 2 3 4 >6< >5< 7 8 9 ]

4.next = 6 
6.prev = 4 
6.next = 5 
5.prev = 6 
5.next = 7 
7.prev = 5 

Hmmm ... Das nur 6 Zuweisungen war.

---

Was passiert, wenn Sie erste und das letzte Element tauschen wollte:

[ >9< 2 3 4 5 6 7 8 >1< ]

Sie haben nicht diesen Teil teilen, aber ich nehme an, Sie haben beide einen Kopf und einen Schwanz Referenz, also:

head = 9 
9.prev = null 
9.next = 2 
2.prev = 9 
8.next = 1 
1.prev = 8 
1.next = null 
tail = 1 

Whoa, das war anders.

---

Jetzt müssen Sie nur noch alles codieren und darauf achten, alle Kombinationen zu handhaben.