[java] ArrayList를 통해 LinkedList를 사용하는 경우


Answers

지금까지 아무도 LinkedListArrayList 보다 "많이 더 많다"는 일반적인 합의 이외에는이 두 목록의 메모리 사용량을 처리하지 못했습니다. 따라서 두 목록이 N 개의 null 참조에 대해 얼마나 많은 양을 차지하는지 정확히 보여주기 위해 숫자를 계산했습니다 .

참조는 상대 시스템에서 32 또는 64 비트 (null 일 때도 있음)이므로 32 비트 및 64 비트 LinkedListsArrayLists 대해 4 세트의 데이터를 포함 시켰습니다.

참고 : ArrayList 행에 표시된 크기는 트리밍 된 목록입니다 . 실제로 ArrayListArrayList 배열 용량은 일반적으로 현재 요소 수보다 큽니다.

참고 2 : (감사합니다 BeeOnRope) JDK6 중반부터 CompressedOops가 기본값으로 설정되었으므로 64 비트 시스템의 경우 아래의 값은 기본적으로 해당 32 비트 카운터와 기본적으로 일치합니다 (물론 특별히 지정하지 않은 경우).

결과는 LinkedListArrayList 보다 훨씬 더 많은 것을 특히 명확하게 보여줍니다. 특히 요소 수가 매우 높습니다. 메모리가 중요한 요소라면 LinkedLists .

제가 사용하는 공식은 제가 잘못한 것을 해줬는지 알려주고 그것을 고칠 것입니다. 'b'는 32 또는 64 비트 시스템에서 4 또는 8이고 'n'은 요소 수입니다. mod의 이유는 java의 모든 객체가 모두 사용되었는지 여부에 관계없이 8 바이트 공간의 배수를 차지하기 때문입니다.

ArrayList :

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList :

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
Question

나는 항상 단순하게 다음과 같이 사용했다.

List<String> names = new ArrayList<>();

인터페이스를 이식성을 위한 형식 이름으로 사용하므로 이러한 질문을 할 때 코드를 재 작업 할 수 있습니다.

LinkedListArrayList 이상으로 사용해야하는 경우는 언제입니까?




When should I use LinkedList ? When working with stacks mostly, or when working with buffers. When should I use ArrayList ? Only when working with indexes, otherwise you can use HashTable with linked list, then you get:

Hash table + linked list

  • Access by key O(1),
  • Insert by key O(1),
  • Remove by key O(1)
  • and there is a trick to implement RemoveAll / SetAll with O(1) when using versioning

It seems like a good solution, and in most of the cases it is, how ever you should know: HashTable takes a lot of disc space, so when you need to manage 1,000,000 elements list it can become a thing that matters. This can happen in server implementations, in clients it is rarely the case.

Also take a look at Red-Black-Tree

  • Random access Log(n),
  • Insert Log(n),
  • Remove Log(n)



It depends upon what operations you will be doing more on the List.

ArrayList is faster to access an indexed value. It is much worse when inserting or deleting objects.

To find out more, read any article that talks about the difference between arrays and linked lists.







Joshua Bloch, the author of LinkedList:

Does anyone actually use LinkedList? I wrote it, and I never use it.

Link: https://twitter.com/joshbloch/status/583813919019573248

I'm sorry for the answer for being not that informative as the other answers, but I thought it would be the most interesting and self-explanatory.




맞음 또는 틀린 : 로컬에서 테스트를 실행하고 직접 결정하십시오!

편집 / 제거는 ArrayList 보다 LinkedList 에서 빠릅니다.

Array 에 의해 뒷받침되는 ArrayList 는 크기가 두 배가되어야하며 대용량 응용 프로그램에서는 더 나쁩니다.

아래는 각 작업에 대한 단위 테스트 결과입니다. 타이밍은 나노초 단위로 표시됩니다.

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

코드는 다음과 같습니다.

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}



약 10 년 동안 매우 대규모의 SOA 웹 서비스에 대한 운영 성능 엔지니어링을 해오 고있는 누군가로서, 나는 ArrayList에 비해 LinkedList의 동작을 선호합니다. LinkedList의 정상 상태 처리량이 더 나빠서 하드웨어를 더 많이 구입할 수는 있지만 ArrayList가 압력을 받으면 클러스터의 응용 프로그램이 거의 동시에 배열을 확장 할 수 있으며 배열 크기가 크면 응답 성이 떨어질 수 있습니다 앱이 중단되고 압력이 가해지는 동안 파국적 인 행동입니다.

마찬가지로 기본 처리량 가비지 수집기의 앱에서 더 나은 처리량을 얻을 수 있지만 10GB 힙이있는 Java 앱을 얻으면 풀 GC 동안 25 초 동안 앱 잠금을 해제하여 SOA 앱의 시간 초과 및 오류를 유발할 수 있습니다 SLA가 너무 자주 발생하면 SLA가 손상됩니다. CMS 수집기가 더 많은 리소스를 사용하고 동일한 원시 처리량을 얻지는 못하지만 예측 가능한 대기 시간이 더 짧기 때문에 훨씬 더 나은 선택입니다.

ArrayList는 성능이 의미하는 것이 처리량이고 대기 시간을 무시할 수있는 경우에만 성능을위한 더 나은 선택입니다. 직장에서의 경험에서 나는 최악의 대기 시간을 무시할 수 없다.




Both remove() and insert() have a runtime efficiency of O(n) for both ArrayLists and LinkedLists. However the reason behind the linear processing time comes from two very different reasons:

In an ArrayList you get to the element in O(1), but actually removing or inserting something makes it O(n) because all the following elements need to be changed.

In a LinkedList it takes O(n) to actually get to the desired element, because we have to start at the very beginning until we reach the desired index. Actually removing or inserting is constant, because we only have to change 1 reference for remove() and 2 references for insert().

Which of the two is faster for inserting and removing depends on where it happens. If we are closer to the beginning the LinkedList will be faster, because we have to go through relatively few elements. If we are closer to the end an ArrayList will be faster, because we get there in constant time and only have to change the few remaining elements that follow it. When done precisely in the middle the LinkedList will be faster because going through n elements is quicker than moving n values.

Bonus: While there is no way of making these two methods O(1) for an ArrayList, there actually is a way to do this in LinkedLists. Lets say we want to go through the entire List removing and inserting elements on our way. Usually you would start from the very beginning for each elements using the LinkedList, we could also "save" the current element we're working on with an Iterator. With the help of the Iterator we get a O(1) efficiency for remove() and insert() when working in a LinkedList. Making it the only performance benefit I'm aware of where a LinkedList is always better than an ArrayList.




Let's compare LinkedList and ArrayList wrt below parameters:

1. Implementation

ArrayList is the resizable array implementation of list interface , while

LinkedList is the Doubly-linked list implementation of the list interface.

2. Performance

  • get(int index) or search operation

    ArrayList get(int index) operation runs in constant time ie O(1) while

    LinkedList get(int index) operation run time is O(n) .

    The reason behind ArrayList being faster than LinkedList is that ArrayList uses index based system for its elements as it internally uses array data structure , on the other hand ,

    LinkedList does not provide index based access for its elements as it iterates either from the beginning or end (whichever is closer) to retrieve the node at the specified element index.

  • insert() or add(Object) operation

    Insertions in LinkedList are generally fast as compare to ArrayList. In LinkedList adding or insertion is O(1) operation .

    While in ArrayList , if array is full ie worst case, there is extra cost of resizing array and copying elements to the new array , which makes runtime of add operation in ArrayList O(n) , otherwise it is O(1) .

  • remove(int) operation

    Remove operation in LinkedList is generally same as ArrayList ie O(n).

    In LinkedList , there are two overloaded remove methods. one is remove() without any parameter which removes the head of the list and runs in constant time O(1) . The other overloaded remove method in LinkedList is remove(int) or remove(Object) which removes the Object or int passed as parameter . This method traverses the LinkedList until it found the Object and unlink it from the original list . Hence this method run time is O(n).

    While in ArrayList remove(int) method involves copying elements from old array to new updated array , hence its run time is O(n).

3. Reverse Iterator

LinkedList can be iterated in reverse direction using descendingIterator() while

there is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.

4. Initial Capacity

If the constructor is not overloaded , then ArrayList creates an empty list of initial capacity 10 , while

LinkedList only constructs the empty list without any initial capacity.

5. Memory Overhead

Memory overhead in LinkedList is more as compared to ArrayList as node in LinkedList needs to maintain the addresses of next and previous node. 동안

In ArrayList each index only holds the actual object(data).

Source




ArrayList and LinkedList both implements List interface and their methods and results are almost identical. However there are few differences between them which make one better over another depending on the requirement.

ArrayList Vs LinkedList

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n) .

Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.

2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).

Conclusion: LinkedList element deletion is faster compared to ArrayList.

Reason: LinkedList's each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. Reason is same as explained for remove.

4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes

hence the memory consumption is high in LinkedList comparatively.

There are few similarities between these classes which are as follows:

  • Both ArrayList and LinkedList are implementation of List interface.
  • They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
  • Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method.
  • The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException ).

When to use LinkedList and when to use ArrayList?

  • As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)) .

    Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.

  • Search ( get method ) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n))

    so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.




ArrayList 는 무작위로 액세스 할 수 있지만 LinkedList 는 요소를 확장하고 제거하는 데 비용이 많이 듭니다. 대부분의 경우 ArrayList 가 좋습니다.

큰 목록을 작성하고 병목 현상을 측정하지 않았다면 차이점에 대해 걱정할 필요가 없을 것입니다.




If your code has add(0) and remove(0) , use a LinkedList and it's prettier addFirst() and removeFirst() methods. Otherwise, use ArrayList .

And of course, Guava 's ImmutableList is your best friend.




An important feature of a linked list (which I didn't read in another answer) is the concatenation of two lists. With an array this is O(n) (+ overhead of some reallocations) with a linked list this is only O(1) or O(2) ;-)

Important : For Java its LinkedList this is not true! See Is there a fast concat method for linked list in Java?




그래, 나도 알아, 이건 고대의 질문이지만, 나는 내 두 센트를 던질거야.

LinkedList는 거의 항상 잘못된 선택이며 성능에 현명한 선택입니다. LinkedList가 호출되는 매우 구체적인 알고리즘이 있습니다. 그러나 매우 희귀 한 알고리즘입니다. 알고리즘은 대개 LinkedList에서 탐색 한 요소를 비교적 빨리 목록에 삽입하고 삭제할 수있는 기능을 사용합니다 ListIterator를 사용합니다.

LinkedList가 ArrayList를 능가하는 일반적인 사용 사례가 하나 있습니다. 그러나 LinkedList 대신 성능이 목표라면 ArrayBlockingQueue (큐 크기의 상한을 미리 결정할 수 있고 모든 메모리를 앞에 할당 할 수있는 경우) 또는이 CircularArrayList 구현을 고려해야합니다 . (예, 2001 년 이후입니다. 따라서이를 일반화해야하지만, 최근의 JVM에서 기사에서 인용 된 것과 비교할 수있는 성능 비율을가집니다)




Related