Brauchen Sie Hilfe bei der Implementierung einer Doubly Linked List in Java [Final]

Question

Hallo Leute Danke für die Hilfe bis jetzt Ich habe dieses Projekt ziemlich abgeschlossen.

Jetzt erkläre ich meinen Code und die Besonderheiten, die ich implementieren musste. 1. Meine verkettete Liste muss mit einer bestimmten Anzahl von Elementen beginnen, Sie sehen dies im DLL-Konstruktor 2. eine Methode, die neue Werte in die erstellten Elemente eingibt. 3. Ich habe eine Methode get, um den Wert an einem bestimmten Knoten zu erhalten. Dies erzeugt auch neue Knoten, wenn der Benutzer einen Indexwert aufruft, der größer als die Listengröße ist. 4. Ich habe auch eine Einfügemethode erstellt, die ein Element an einer bestimmten Stelle einfügt.

Meine Knotenklasse sieht wie folgt aus (sorry für die Kleinklassenname):

public class node { 

private int _value; 

public node(int v){ 
    _value = v; 
} 

public node(){ 

} 

public int get(){ 
    return _value; 
} 

public void set(int v){ 
    _value = v; 
} 

public node next = null; 
public node prev = null; 
} 

Meine DLL-Klasse (ungerade Name ich weiß, nur den Titel des Projekts):

public class BetterArray{ 

private int _size; 
private node _head; 
private node _tail; 

public BetterArray(int n){ 
    _head = null; 
    _tail = null; 
    _size = n; 

    if(_head == null){ 
     _head = new node(0); 
     _tail = _head; 
    } 

    for(int i = 1; i < n; i++){ 
     node current = _head; 
     for(int j = 1; j < i; j++){ 
      current = current.next; 
     } 
     node newNode = current.next; 
     current.next = new node(0); 
     current.next.next = newNode; 
     current.next.prev = current; 
     _tail = current.next; 
    } 
} 

public BetterArray(){   
} 

public int get(int index){ 
    int value = 0; 
    node temp = _head; 
    if(index < _size){ 
     for(int loc = 0; loc < index; loc++){ 
      temp = temp.next; 
     } 
     value = temp.get(); 
    } 
    else{ 
     for(int i = _size; i <= index; i++){ 
      node current = temp; 
      for(int j = _size; j < i; j++){ 
       current = current.next; 
      } 
      node newNode = current.next; 
      current.next = new node(0); 
      _size++; 
      current.next.next = newNode; 
      current.next.prev = current; 
      _tail = current.next; 
     } 
    } 
    return value; 
} 

public void put(int value, int index){ 
    node temp = _head; 
    if(index < _size){ 
     for(int loc = 0; loc < index; loc++){ 
      temp = temp.next; 
     } 
     temp.set(value); 
    } 
    else{ 
     for(int i = _size; i < index; i++){ 
      node current = temp; 
      for(int j = _size; j < i; j++){ 
       current = current.next; 
      } 
      node newNode = current.next; 
      current.next = new node(value); 
      _size++; 
      current.next.next = newNode; 
      current.next.prev = current; 
      _tail = current.next;   
     } 
    } 
} 

public void insert(int value,int index){ 
    node current = _head; 

     for(int loc = 0; loc < index - 1; loc++){ 
      current = current.next; 
     } 

     node temp = current.next; 
     current.next = new node(value); 
     _size++; 
     current.next.next = temp; 
     current.next.prev = current; 
     _tail = current.next; 
    } 
} 

public void delete(int index){ 
    node pre = _head; 

    for(int loc = 0; loc < index; loc++){ 
     pre = pre.next; 
    } 
    node current = pre.next; 
    pre.next = current.next; 
    _size--; 
} 
public int getSize(){ 
    return _size; 
} 

Answer 1

EDIT :

Nun, da ich besser verstehe, was Sie wollen (eine willkürlich indizierte Einfügefunktion für eine doppelt verknüpfte Liste Datenstruktur), hier ist ein Code, der Ihnen helfen könnte:

public class BetterArray{ 

    public node _head = null; 
    public node _tail = null; 

    public BetterArray(){ 
     _head = _tail = new node(); 
    } 

    public node insert(int val, int index) { 
     if (index < 0) { 
      throw new IllegalArgumentException("You must provide an index which is not negative"); 
     } 
     node current = _head; 
     for (int i = 0; i < index; i++) { 
      if (current.next == null) { 
       current.next = new node(); 
       current.next.prev = current; 
       _tail = current; 
      } 
      current = current.next; 
     } 
     current.set(val); 
     return current; 
    } 
} 

public class node { 

    private int _value; 
    private boolean _initialized; 

    public node(int v){ 
     _value = v; 
     _initialized = true; 
    } 

    public node(){ 
     _initialized = false; 
    } 

    public int get(){ 
     if (!_initialized) { 
      throw new IllegalArgumentException("This node has not been set with any value"); 
     } 
     return _value; 
    } 

    public void set(int v){ 
     _value = v; 
     _initialized = true; 
    } 

    public node next = null; 
    public node prev = null; 
} 

Sie können es auch ausprobieren. Tun Sie einfach so etwas:

BetterArray whatever = new BetterArray(); 
whatever.insert(5,3); 
System.out.println(whatever._head.next.next.next.get()); 

Nur damit Sie wissen, gibt es auch Standard-Java-Datenstrukturen bereits implementiert. Vielleicht möchten Sie einen Blick auf LinkedList werfen. Im Grunde ist das, was ich tue, das gleiche wie das Hinzufügen von Knoten, bis seine Größe verhindert, dass es einen IllegalArgumentException bekommt, dann macht man einen set.

ORIGINAL POST:

verlinkte Listen und Arrays sind zwei völlig unterschiedliche Datenstrukturen. Anstatt sich auf die Implementierung zu konzentrieren, sollten Sie überlegen, was Sie mit der Datenstruktur tun möchten. Benötigen Sie einen wahlfreien Zugriff auf Daten? Eine (doppelt) verknüpfte Liste benötigt O (n) Zeit, um das richtige Element für sowohl Lese- als auch Schreibvorgänge zu finden; Sie haben dies selbst mit der Logik gesehen, die Sie in der Beilage implementiert haben. Für Arrays ist der Direktzugriff eine O (1) konstante Zeitoperation. Wenn Sie eine Datenstruktur wie eine Liste schreiben möchten, um einen wahlfreien Zugriff zu erhalten, versuchen Sie es mit new node[n], und halten Sie das gesamte Array-Objekt privat im Speicher.

Wenn etwas größer ist, wird standardmäßig ein neues Array erstellt, das doppelt so groß wie der angeforderte Index ist, und alle alten Daten in das neue Array kopiert. Dies ist eine O (n) -Operation, während die Einfügung für eine verkettete Liste am Anfang oder Ende der Liste O (1) konstante Zeit ist.

Gibt es einen Mittelweg? Eigentlich gibt es! Wenn Sie einen ausgeglichenen Binärbaum implementieren, können Sie O (lg (n)) einfügen und O (lg (n)) auf Ihre Knoten zugreifen. Ich empfehle Ihnen, Ihre Datenstrukturen aufzufrischen. Versuch es auf Papier und Bleistift, bis du verstehst, wie sich die Strukturen anfühlen, und lege es dann auf den Code. Wenn Sie mit Java nicht vertraut sind oder es von Ihrer Klasse verlangt wird, halten Sie sich an die Sprache, die Sie zuerst gelernt haben (ich nehme C aufgrund des Stils an, den Sie schreiben, und der Art, wie Sie Dinge "Zeiger" nennen). Sonst wirst du zwei Dinge gleichzeitig lernen, was in der Regel schwieriger ist, als eine Sache nach der anderen zu lernen.