2015-06-04 17 views
7

Chcę usunąć i usunąć pierwszy element z listy. widzę, mam dwie opcje:Skuteczny sposób na pobranie/usunięcie pierwszego elementu z listy?

Pierwsze podejście:

LinkedList<String> servers = new LinkedList<String>(); 
.... 
String firstServerName = servers.removeFirst(); 

Drugie podejście

ArrayList<String> servers = new ArrayList<String>(); 
.... 
String firstServerName = servers.remove(0); 

mam wiele elementów w moim liście.

  • Czy są jakieś preferencje, z których należy skorzystać?
  • Jaka jest różnica między powyższymi dwoma? Czy są technicznie rzecz biorąc pod względem wydajności? Jaka jest złożoność, jeśli mamy dużo elementów?

Jaki jest najbardziej wydajny sposób na zrobienie tego.

+0

a) określić wydajność. Istnieje wiele zmiennych, które można zmierzyć, takich jak czas, wydajność, wykorzystanie pamięci itp. B) Napisz kod testowy, używając stoperów (klasy, nie fizycznych) i rzeczy tego rodzaju, aby je porównać i dowiedzieć się. –

+1

"Jaki jest najskuteczniejszy sposób na zrobienie tego?" Zależy od twojego scenariusza. Zobacz http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Shar1er80

Odpowiedz

2

Korzystanie z połączonej listy jest znacznie szybsze.

LinkedList

To po prostu odwołać węzły więc pierwsza znika. enter image description here

ArrayList

Z listy tablicy to musi przenieść wszystkie elementy z powrotem jedno miejsce, aby utrzymać podstawową tablicę właściwe.

2

Usunięcie pierwszego elementu tablicy ArrayList to O (n). Dla połączonej listy jest O (1), więc pójdę z tym.

Sprawdź ArrayList documentation

Wielkość, operacje isEmpty, get, set, iteracyjnej i listIterator uruchomić w stałym czasie. Operacja dodawania działa w amortyzowanym czasie stałym, , czyli dodanie n elementów wymaga czasu O (n). Wszystkie inne operacje są uruchamiane w czasie liniowym (z grubsza rzecz biorąc). Stały współczynnik jest niski w porównaniu do tego dla implementacji LinkedList.

To faceci rzeczywiście dostał źródła OpenJDK link

+0

O (n)? Albo to literówka, albo moje rozumienie list.remove (0) nie jest poprawne. Czy możesz wyjaśnić, jak to jest O (n)? – prabugp

+0

@prabugp to nie jest literówka –

+1

@prabugp Elementy po tym muszą być przesunięte. –

3

Jeżeli porównanie do „usunięcia pierwszy” jest między ArrayList i LinkedList klasach LinkedList wyraźnie wygrywa.

Usunięcie elementu z połączonej listy kosztuje O(1), a robi to dla tablicy (lista tablic) kosztuje O(n).

5

Upewnij się, że rozumiesz różnicę między LinkedList i ArrayList. ArrayList jest zaimplementowany za pomocą Array.

LinkedList zajmuje stały czas, aby usunąć element. ArrayList może wymagać czasu liniowego, aby usunąć pierwszy element (aby potwierdzić, że muszę sprawdzić implementację, a nie eksperta java tutaj).

Myślę również, że LinkedList jest bardziej wydajny pod względem przestrzeni. Ponieważ ArrayList nie będzie (i nie powinien) zmieniać rozmiaru tablicy za każdym razem, gdy element zostanie usunięty, zajmuje więcej miejsca niż potrzeba.

+2

'ArrayList' w Javie nie jest podwójnie zakończony, więc musi przesunąć wszystko, kiedy usuniesz pierwszy element. 'ArrayList' jest bardziej efektywny pod względem przestrzeni niż' ListaBlączek' dla dużych list, ale ponieważ lista_połączeń używa 3 odniesień dla każdego elementu (wartość, następny i poprzedni), podczas gdy 'ArrayList' potrzebuje tylko jednego odniesienia na element plus nieużywane miejsce. – Raniz

+0

@Raniz plus słowo znacznika plus wskaźnik klasy, plus możliwe dopełnienie ... – immibis

+0

Nie zapominaj, że obiekt opakowania zajmuje również pamięć – xTrollxDudex

2

Jak słusznie zauważyli inni, LinkedList jest szybszy niż ArrayList w celu usunięcia pierwszego elementu z innej niż bardzo krótkiej listy.

Jednak aby dokonać wyboru między nimi, należy wziąć pod uwagę kompletny zestaw operacji. Na przykład, jeśli twoje obciążenie wykonuje miliony indeksowanych dostępów do setki elementów dla każdego usuwania pierwiastków, ArrayList będzie ogólnie lepszy.

2

Praktycznie rzecz biorąc, LinkedList#removeFirst jest bardziej efektywny, ponieważ działa na podwójnie połączonej liście, a usunięcie pierwszego elementu polega w zasadzie tylko na odłączeniu go od nagłówka listy i zaktualizowaniu następnego elementu jako pierwszego:

private E unlinkFirst(Node<E> f) { 
    // assert f == first && f != null; 
    final E element = f.item; 
    final Node<E> next = f.next; 
    f.item = null; 
    f.next = null; // help GC 
    first = next; 
    if (next == null) 
     last = null; 
    else 
     next.prev = null; 
    size--; 
    modCount++; 
    return element; 
} 

ArrayList#remove pracuje na wewnętrznej matrycy wymagającej shiftting wszystkie subsequents elementów jednej pozycji w lewo o kopiowaniu przez subarray:

public E remove(int index) { 
    rangeCheck(index); 

    modCount++; 
    E oldValue = elementData(index); 

    int numMoved = size - index - 1; 
    if (numMoved > 0) 
     System.arraycopy(elementData, index+1, elementData, index, 
         numMoved); 
    elementData[--size] = null; // clear to let GC do its work 

    return oldValue; 
} 

z drugiej ręcznie, operacja LinkedList#get wymaga przewinięcia połowy całej listy w celu pobrania elementu z określonego indeksu - w najgorszym przypadku. ArrayList#get ma bezpośredni dostęp do elementu o określonym indeksie, ponieważ działa on w tablicy.

Moja zasada rekomendacji dotyczących efektywności tutaj byłoby:

  • Zastosowanie LinkedList jeśli dużo add/remove zrobić w porównaniu z pobierania operacji (np .: get);
  • Użyj ArrayList, jeśli wykonasz wiele operacji pobierania w porównaniu z add/remove.
0

Trzeci aproach.

Jest narażony przez interfejs java.util.Queue. LinkedList jest implementacją tego interfejsu.

Interfejs kolejki udostępnia metodę E poll(), która skutecznie usuwa nagłówek listy (kolejki).

Pod względem wydajności metoda poll() jest porównywalna do metody removeFirst(). W rzeczywistości używa pod maską metody removeFirst().

1

Myślę, że to, czego potrzebujesz, to ArrayDeque (niesprawiedliwie przeoczona klasa w java.util). Jego metoda removeFirst działa w trybie O (1), podobnie jak w przypadku LinkedList, podczas gdy generalnie pokazuje lepszą charakterystykę przestrzeni i czasu z zakresu ArrayList. Jest zaimplementowany jako okrągła kolejka w tablicy.

Powinieneś bardzo rzadko używać LinkedList. Raz w ciągu 17 lat pracowałem jako programista Java i z perspektywy czasu żałowałem.

+0

Możesz również użyć 'List.subList (...)', zobacz moją odpowiedź https://stackoverflow.com/a/46211629/480894 – Roland

+0

Możesz, @Roland. Jeśli zarówno dodawanie, jak i usuwanie jest kontynuowane, nie widzę, jak będzie to praktyczne. Jeśli lista jest wypełniona tylko raz, a potem tylko usunięta z, 'subList()' powinna być w porządku. –

0

W przypadku ArrayList usuwanie pierwszego elementu ma złożoność O (n), więc jako alternatywę można uzyskać pierwszy element i zamiast usuwać go po prostu zadzwonić List.subList(int fromIndex, int toIndex):

final String firstServerName = servers.get(0); 
servers = servers.subList(1, servers.size()); 
Powiązane problemy