When is it better to use LinkedList and when ArrayList.?

Navigation
4

I have problems to differentiate when to use one or the other .. For example, in an agenda in which you add contacts and delete them I think it would be LinkedList.

I would like an answer to easily understand when to use one or the other. A link to a source that explains it well would also be worth it.

  • It is desired to organize an agenda with the data of the clients of a company (name that will be assumed that it contains the surnames and name in this order and telephone). As the company is very messy, all the business cards are in a card holder placed one on top of the other. You want to empty this card and put all the cards in a calendar so that all those whose last name starts with the same letter are together (for example, all those starting with A will be on the first page, all those starting with B in the second, etc.)

    It asks:

    Establish what kind of data structure would be used to represent the necessary information: card, card holder, agenda and calendar pages.

    Write a Java program that implements the structures described and perform the following operations:

    • Create the card holder: several unordered cards will be inserted in the card holder (make sure there are several cards with the same initial in the name so that they are saved in the same page)

    • Create the agenda: all the cards will be removed from the card holder and will be saved in the agenda on the corresponding page according to the initial of the name.

    • See the agenda: it will list all its pages, using the Iterable interface that Agenda and Page must implement

    • Sort each page of the calendar by name, using the interface ((Comparable)) that Card must implement. The ordered calendar must be shown again. **

    • In that exercise I wanted to use an arrayList for the cards on the page but I was advised that in this case I would use Linkedlist.

        
    asked by David Palanco 13.06.2018 в 20:42
    source

    1 answer

    6

    Summary ArrayList is what you want LinkedList is almost always an error (performance).

    LinkedList and ArrayList are two different implementations of the interface of the List. LinkedList is implemented with a doubly linked list. ArrayList is implemented with a dynamic resizing matrix.

    As with the standard linked list and array operations, the various methods will have different algorithmic execution times.

    • LinkedList allows constant time insertions or deletions using iterators, but only sequential access of elements. In other words, you can scroll the list forward or backward, but finding a position in the list takes time proportional to the size of the list. Javadoc says that "the operations that index in the list will cross the list from the beginning or the end, whichever is closer", so these methods are O (n) (n / 4 steps) on average, although O ( 1) for index = 0.

    • ArrayList on the other hand, allows access Quick random read, so you can grab any item in constant time. But adding or deleting from any place except the end requires moving all the last elements, either to open or fill the space. Also, if you add more elements than the capacity of the underlying matrix, a new matrix is assigned (1.5 times the size), and the previous matrix is copied to the new one, so adding a ArrayList is O (n) in the worst case but constant on average.

    Then, depending on the operations you intend to do, you must choose the implementations accordingly. Iterating over any of the types of lists is practically as cheap. (The iteration over ArrayList is technically faster, but unless you are doing something really performance sensitive, you should not worry about this, both are constant).

    The main benefits of using LinkedList arise when you reuse existing iterators to insert and delete elements. These operations can be performed in O (1) by changing the list only locally. In a matrix list, the rest of the matrix must be moved (that is, copied). On the other hand, search in a LinkedList medium following the links in O (n) (n / 2 steps) for the worst case, while in a 'ArrayList desired position can be mathematically calculated and accessed in O (1 ).

    Another benefit of using LinkedList arises when it is added or removed from the list header, since those operations are O (1), whereas they are O (n) for ArrayList . Keep in mind that ArrayDeque can be a good alternative LinkedList to add and remove from the head, but it is not a List .

    Also, if you have large lists, keep in mind that the use of memory is also different. Each element of a LinkedList has more overload, since the pointers to the next and previous elements are also stored. ArrayLists do not have this overload. However, ArrayLists take up so much allocated memory for capacity, regardless of whether the elements have actually been added.

    The default initial capacity of a ArrayList is quite small (10 from Java 1.4 - 1.8). But since the underlying implementation is a matrix, the matrix must be resized if you add many elements. To avoid the high cost of resizing when you know you are going to add many elements, build 'ArrayList with a higher initial capacity.

      

    For more information, SO Source: When to use LinkedList over ArrayList?

    Other interesting sources (Translate from English):

      
        
    answered by 13.06.2018 / 21:05
    source
    Sort Array using an int variable from another class Do diagonal in CSS