ArrayList vs LinkedList

An ArrayList uses an array to store its elements. This means it's fast for random access (e.g. get me element #9832), because the array index gets you right to that element.



It's slow for adding and deleting at the beginning and middle of the list, since you have to then copy all the later elements forward or back.



It also suffers when you fill up the array, and then have to create a new one and copy the old elements into it.



A linked list uses a node that stores its element and a pointer to the next element. A singly linked list only has pointers to next. A doubly linked list has a pointer to the next and the previous element. This makes walking the list backward easier.



Linked lists are slow for random access. Gettting element #9832 means you have to walk either forward from the beginning or backward from the end (depending on whether 9832 is less than or greater than half the list size), calling next or previous, until you get to that element.



Linked lists are fast for inserts and deletes anywhere in the list, since all you do is update a few next and previous pointers.



Each element of a linked list (especially a doubly linked list) uses a bit more memory than its equivalent in array list, due to the need for next an d previous pointers.



サンのJava Forumより

＜日本語訳＞



ArrayList

アレイを使ってデータを保存している。

インデックス指定のランダムアクセスが早い。

リストの最初や途中のデータ入力、消去には時間がかかる。

（アレイをコピーしないといけないので）

アレイが一杯になってしまった場合も新しい物を作成しコピーしなければならないので時間がかかる。



LinkedList

ポジション指定のランダムアクセスの際、最初から順番にポインターを動かすため時間がかかる。

データの入力、消去はリンクを変更するだけなので位置に関係なく素早くできる。

次のデータへのポインターが必要なため、ArrayListよりもメモリを必要とする。