Java ArrayList, wie Elemente am Anfang hinzugefügt werden

181

Ich muss einer ArrayListWarteschlange Elemente hinzufügen , aber wenn ich die Funktion zum Hinzufügen eines Elements aufrufe, möchte ich, dass sie das Element am Anfang des Arrays hinzufügt (damit es den niedrigsten Index hat) und wenn das Array 10 Elemente hinzufügt Ein neues Ergebnis führt zum Löschen des ältesten Elements (des Elements mit dem höchsten Index).

Hat jemand irgendwelche Vorschläge?

ZeDonDino
quelle
Meinst du wie removeund add?
Peter Lawrey
Wofür Sie Ihre arraylist stack queue whateverals Hinzufügen zum Anfang eines Arrays verwenden, wird am besten vermieden, und es klingt so, als ob Sie eine andere Sammlung verwenden sollten.
Peter Lawrey
Zuerst solltest du etwas selbst machen. Was hast du bis jetzt gemacht?
Yegoshin Maxim

Antworten:

301

Listhat die Methode add(int, E), so können Sie verwenden:

list.add(0, yourObject);

Anschließend können Sie das letzte Element löschen mit:

if(list.size() > 10)
    list.remove(list.size() - 1);

Möglicherweise möchten Sie jedoch Ihre Anforderungen überdenken oder eine andere Datenstruktur verwenden, z Queue

BEARBEITEN

Vielleicht werfen Sie einen Blick auf Apache CircularFifoQueue:

CircularFifoQueue ist eine First-In-First-Out-Warteschlange mit einer festen Größe, die das älteste Element ersetzt, wenn es voll ist.

Initialisieren Sie es einfach mit Ihrer maximalen Größe:

CircularFifoQueue queue = new CircularFifoQueue(10);
Baz
quelle
10
Ich würde keine Apache-Bibliothek mit einer zehn Fuß langen Stange berühren, zumal es Guavas Sammlungsklassen gibt. Guavas EvictingQueue könnte hier eine gute Wahl sein.
DPM
27

Verwenden spezifischer Datenstrukturen

Es gibt verschiedene Datenstrukturen, die für das Hinzufügen von Elementen am ersten Index optimiert sind. Beachten Sie jedoch, dass die Konversation wahrscheinlich eine zeitliche und räumliche Komplexität von benötigt, wenn Sie Ihre Sammlung in eine dieser konvertierenO(n)

Deque

Das JDK enthält die DequeStruktur, die Methoden wie addFirst(e)und bietetofferFirst(e)

Deque<String> deque = new LinkedList<>();
deque.add("two");
deque.add("one");
deque.addFirst("three");
//prints "three", "two", "one"

Analyse

Die räumliche und zeitliche Komplexität der Einfügung ist LinkedListkonstant ( O(1)). Siehe das Big-O-Cheatsheet .

Liste umkehren

Eine sehr einfache, aber ineffiziente Methode ist die Verwendung von umgekehrt:

 Collections.reverse(list);
 list.add(elementForTop);
 Collections.reverse(list);

Wenn Sie Java 8-Streams verwenden, könnte Sie diese Antwort interessieren.

Analyse

  • Zeitliche Komplexität: O(n)
  • Raumkomplexität: O(1)

Bei der JDK-Implementierung ist diese O(n)zeitlich komplex und daher nur für sehr kleine Listen geeignet.

Patrick Favre
quelle
Liste zweimal umkehren. Wird die Laufzeit des Algorithmus im Vergleich zu der oben akzeptierten Lösung erheblich erhöht?
Samyak Upadhyay
Es fügt 2n hinzu, also ja, aber wenn Sie eine Liste von <50 haben, können Sie den Unterschied auf den meisten modernen Maschinen nicht mikro-messen
Patrick Favre
8

Sie können sich das Add (int index, E element) ansehen :

Fügt das angegebene Element an der angegebenen Position in diese Liste ein. Verschiebt das aktuell an dieser Position befindliche Element (falls vorhanden) und alle nachfolgenden Elemente nach rechts (fügt eins zu ihren Indizes hinzu).

Sobald Sie hinzugefügt haben, können Sie die Größe der ArrayList überprüfen und die am Ende entfernen.

npinti
quelle
5

Vielleicht möchten Sie sich Deque ansehen. Sie haben direkten Zugriff auf das erste und das letzte Element in der Liste.

Evvo
quelle
1
Ich bin überrascht, dass Sie die einzige Antwort sind, die über Deque spricht. Dies ist offensichtlich die beste optimale Lösung.
Guillaume F.
4

Was Sie beschreiben, ist eine geeignete Situation Queue .

Da willst du addneues Element und removedas alte. Sie können am Ende hinzufügen und am Anfang entfernen. Das wird keinen großen Unterschied machen.

Warteschlange hat Verfahren add(e)und remove()die fügt am Ende das neue Element und entfernt von Anfang an das alte Element, respectively.

Queue<Integer> queue = new LinkedList<Integer>();
queue.add(5);
queue.add(6);
queue.remove();  // Remove 5

Jedes Mal, wenn Sie dem ein Element hinzufügen queue, können Sie es mit einem removeMethodenaufruf sichern.


UPDATE : -

Und wenn Sie die Größe der festlegenQueue möchten , können Sie sich Folgendes ansehen: -ApacheCommons#CircularFifoBuffer

Aus dem documentation: -

CircularFifoBuffer ist ein First-In-First-Out-Puffer mit einer festen Größe, der sein ältestes Element ersetzt, wenn es voll ist.

Buffer queue = new CircularFifoBuffer(2); // Max size

queue.add(5);
queue.add(6);
queue.add(7);  // Automatically removes the first element `5`

Wie Sie sehen können, entfernt das Hinzufügen eines neuen Elements automatisch das erste eingefügte Element, wenn die maximale Größe erreicht ist.

Rohit Jain
quelle
2

Ich denke, das Implement sollte einfach sein, aber angesichts der Effizienz sollten Sie LinkedList verwenden, aber nicht ArrayList als Container. Sie können auf den folgenden Code verweisen:

import java.util.LinkedList;
import java.util.List;

public class DataContainer {

    private List<Integer> list;

    int length = 10;
    public void addDataToArrayList(int data){
        list.add(0, data);
        if(list.size()>10){
            list.remove(length);
        }
    }

    public static void main(String[] args) {
        DataContainer comp = new DataContainer();
        comp.list = new LinkedList<Integer>();

        int cycleCount = 100000000;

        for(int i = 0; i < cycleCount; i ++){
            comp.addDataToArrayList(i);
        }
    }
}
Feikiss
quelle
1

Sie können diesen Code verwenden

private List myList = new ArrayList();
private void addItemToList(Object obj){
    if(myList.size()<10){
      myList.add(0,obj);
    }else{
      myList.add(0,obj);
      myList.remove(10);
    }
}
MaVRoSCy
quelle
1

Sie können Listenmethoden verwenden, entfernen und hinzufügen

list.add(lowestIndex, element);
list.remove(highestIndex, element);
Mich_
quelle
0

Sie können verwenden

public List<E> addToListStart(List<E> list, E obj){
list.add(0,obj);
return (List<E>)list;

}

Ändern Sie E mit Ihrem Datentyp

Wenn das älteste Element gelöscht werden muss, können Sie Folgendes hinzufügen:

list.remove(list.size()-1); 

vor der Rückgabeerklärung. Andernfalls fügt list Ihr Objekt am Anfang hinzu und behält auch das älteste Element bei.

Dadurch wird das letzte Element in der Liste gelöscht.

ein Lernender
quelle
0
import java.util.*:
public class Logic {
  List<String> list = new ArrayList<String>();
  public static void main(String...args) {
  Scanner input = new Scanner(System.in);
    Logic obj = new Logic();
      for (int i=0;i<=20;i++) {
        String string = input.nextLine();
        obj.myLogic(string);
        obj.printList();
      }
 }
 public void myLogic(String strObj) {
   if (this.list.size()>=10) {
      this.list.remove(this.list.size()-1);
   } else {
     list.add(strObj); 
   }
 }
 public void printList() {
 System.out.print(this.list);
 }
}
Machhindra Neupane
quelle
0

Nehmen Sie dieses Beispiel: -

List<String> element1 = new ArrayList<>();
element1.add("two");
element1.add("three");
List<String> element2 = new ArrayList<>();
element2.add("one");
element2.addAll(element1);
Ashish Mehta
quelle
-1

Ich hatte ein ähnliches Problem, als ich versuchte, ein Element am Anfang eines vorhandenen Arrays hinzuzufügen, die vorhandenen Elemente nach rechts zu verschieben und das älteste (Array [Länge-1]) zu verwerfen. Meine Lösung ist möglicherweise nicht sehr leistungsfähig, funktioniert aber für meine Zwecke.

 Method:

   updateArray (Element to insert)

     - for all the elements of the Array
       - start from the end and replace with the one on the left; 
     - Array [0] <- Element

Viel Glück

FabianUx
quelle