Jaka jest różnica między LinkedList i ArrayList, a kiedy użyć której?

Question

Jaka jest różnica między LinkedList i ArrayList? Skąd mam wiedzieć, kiedy go użyć?

Answer 1

Nie należy również używać. Użyj System.Collections.Generic.List<T>.

To naprawdę jest moja rekomendacja. Prawdopodobnie niezależnie od tego, jaka jest twoja aplikacja, ale tutaj jest trochę więcej kolorów, na wypadek, gdybyś zrobił coś, co wymaga tutaj precyzyjnie dostrojonego wyboru.

ArrayList i LinkedList to różne implementacje mechanizmu magazynowania dla List. ArrayList używa tablicy, którą musi zmienić rozmiar, jeśli twoja kolekcja przerasta bieżący rozmiar pamięci. Z drugiej strony, LinkedList wykorzystuje strukturę danych z list powiązanych z CS 201. LinkedList jest lepsza dla niektórych obciążeń ciężkich podczas wstawiania głowicy lub ogona, ale ArrayList jest lepsza dla obciążeń dostępu losowego.

Answer 2

Różnica polega semantyki jak List interfejs * jest realizowany:

http://en.wikipedia.org/wiki/Arraylist i http://en.wikipedia.org/wiki/LinkedList

---

* Znaczenie ten basic list operations

Answer 3

różnica jest wewnętrzna struktura danych używana do przechowuj obiekty.

An ArrayList użyje macierzy systemowej (np. Object[]) i zmieni jej rozmiar w razie potrzeby. Z drugiej strony, LinkedList użyje obiektu, który zawiera dane i wskaźnik do następnego i poprzedniego obiektu na liście.

Różne operacje będą miały różną złożoność algorytmiczną ze względu na tę różnicę w reprezentacji wewnętrznej.

Answer 4

Mają różną wydajność na "wkładkach" (dodawanie nowych elementów) i sprawdzeniach. Dla insertów ArrayLists utrzymuje tablicę wewnętrznie (początkowo 16 elementów), a po osiągnięciu maksymalnej pojemności podwaja rozmiar tablicy. Obiekt LinkedList jest pusty i dodaje element (węzeł) w razie potrzeby.

Myślę, że z ArrayList można indeksować elementy, podczas gdy z LinkedList trzeba "odwiedzić" przedmiot z głowy (lub linkList robi to automatycznie dla ciebie).

Answer 5

Główną różnicą pomiędzy ArrayList i List<T>, LinkedList<T> i innych podobnych rodzajowych jest ArrayList posiada Object s, podczas gdy inni posiadają typ, który zdefiniowanych (tj. List<Point> posiada tylko punkty).

Z tego powodu należy rzucić dowolny obiekt pobrany z ArrayList do faktycznego typu. Może to zająć dużo miejsca na ekranie, jeśli masz długie nazwy klas.

Ogólnie rzecz biorąc, znacznie lepiej jest używać List<T> i innych typów ogólnych, chyba że naprawdę potrzebujesz listy zawierającej wiele różnych typów obiektów.

Answer 6

ArrayList ma dobrą zastępczą, która jest List<T>.

Ogólnie List<T> jest nakładką na tablicy - umożliwia indeksowanie i uzyskiwania dostępu do elementów w O (1), ale za każdym razem, gdy przekraczają zdolności O (n) należy zwrócić.

LinkedList<T> nie pozwoli Ci uzyskać dostęp do elementów za pomocą indeksu, ale można liczyć, że wkładka zawsze będzie kosztować O (1). Ponadto można wstawiać elementy na początku listy i między istniejącymi pozycjami w O (1).

Myślę, że w większości przypadków domyślnym wyborem jest List<T>. Wiele typowych scenariuszy nie wymaga specjalnego porządku i nie ma ścisłych ograniczeń złożoności, dlatego preferowane jest ustawienie List<T> ze względu na jego prostotę użycia.

Answer 7

Jak stwierdził @sblom, należy użyć ogólnych odpowiedników obiektu LinkedList i ArrayList. Naprawdę nie ma powodu, aby tego nie robić, i wiele powodów.

Implementacja List jest skutecznie owijająca tablicę. Gdyby próba użytkownik wstawić elementy poza granice tablicy podkładowej, zostanie on skopiowany do większej tablicy (w znacznym kosztem, buit przejrzysty dla użytkowników Listy <T>)

LinkedList <T> ma całkowicie odmienna implementacja, w której dane przechowywane są w instancjach LinkedListNode <T>, które przenoszą odniesienia do dwóch innych instancji klasy LinkedListNode <T> (lub tylko jeden w przypadku nagłówka lub ogona listy). Nie tworzy się zewnętrznych odniesień do pozycji na środku listy. Oznacza to, że iteracja listy jest szybka, ale dostęp losowy jest powolny, ponieważ należy wykonać iterację węzłów z jednego lub drugiego końca. Najlepszym powodem użycia listy LinkedList jest umożliwienie szybkich wstawek, które polegają po prostu na zmianie referencji przechowywanych przez węzły, a nie przepisywaniu całej listy w celu wstawienia elementu (jak w przypadku listy T >)