wake-up-neo.com

Was ist der beste Weg, um das erste Element aus einem Array zu entfernen?

Ich habe ein String-Array (String[]) und muss das erste Element entfernen. Wie kann ich das effizient machen? 

70
NullVoxPopuli

Die Größe von Arrays in Java kann nicht geändert werden. Technisch gesehen können Sie also keine Elemente aus dem Array entfernen.

Eine Möglichkeit, das Entfernen eines Elements aus dem Array zu simulieren, besteht darin, ein neues, kleineres Array zu erstellen und dann alle Elemente aus dem ursprünglichen Array in das neue, kleinere Array zu kopieren.

String[] yourArray = Arrays.copyOfRange(oldArr, 1, oldArr.length);

Allerdings , würde ich die obige Methode nicht vorschlagen. Sie sollten wirklich einen List<String> verwenden. Listen können Sie Elemente hinzufügen und aus jedem Index entfernen. Das würde ungefähr so ​​aussehen:

List<String> list = new ArrayList<String>(); // or LinkedList<String>();
list.add("Stuff");
// add lots of stuff
list.remove(0); // removes the first item
133
jjnguy

Der einfachste Weg ist wahrscheinlich der folgende: Grundsätzlich müssen Sie ein neues Array erstellen, das um ein Element kleiner ist, und dann die Elemente, die Sie behalten möchten, an die richtigen Positionen kopieren.

int n=oldArray.length-1;
String[] newArray=new String[n];
System.arraycopy(oldArray,1,newArray,0,n);

Wenn Sie feststellen, dass Sie diese Art von Operation häufig ausführen, kann dies ein Zeichen dafür sein, dass Sie tatsächlich eine andere Art von Datenstruktur verwenden sollten, z. eine verknüpfte Liste. Das Erstellen eines neuen Arrays ist immer eine O(n) - Operation, die teuer werden kann, wenn das Array groß ist. Eine verknüpfte Liste würde O(1) zum Entfernen des ersten Elements führen.

Eine alternative Idee ist, das erste Element überhaupt nicht zu entfernen, sondern lediglich eine Ganzzahl zu erhöhen, die auf den ersten verwendeten Index zeigt. Benutzer des Arrays müssen diesen Versatz berücksichtigen, dies kann jedoch ein effizienter Ansatz sein. Die Java-String-Klasse verwendet diese Methode tatsächlich beim Erstellen von Teilzeichenfolgen.

13
mikera

Du kannst es überhaupt nicht machen, geschweige denn schnell. Arrays in Java haben eine feste Größe. Zwei Dinge, die Sie tun könnten, sind:

  1. Verschieben Sie jedes Element um eins und setzen Sie das letzte Element auf null.
  2. Erstellen Sie ein neues Array und kopieren Sie es.

Sie können System.arraycopy für beide verwenden. Beide sind O (n), da sie alle Elemente außer einem Element kopieren.

Wenn Sie das erste Element häufig entfernen, sollten Sie stattdessen LinkedList verwenden. Sie können LinkedList.remove verwenden, das von der Queue-Schnittstelle stammt. Bei LinkedList ist das Entfernen des ersten Elements O (1). Tatsächlich ist das Entfernen eines Elements O(1), sobald Sie eine ListIterator an dieser Position haben. Der Zugriff auf ein beliebiges Element über den Index ist jedoch O (n).

5

Behalten Sie einen Index des ersten "live" -Elements des Arrays bei. Das Entfernen des ersten Elements (das Vortäuschen vor dem Entfernen) wird dann zu einer O(1)-Zeitkomplexitätsoperation.

2
msw

Zusammenfassend die Methode der schnellen Linkliste:

List<String> llist = new LinkedList<String>(Arrays.asList(oldArray));
llist.remove(0);
0
geordi_laforge