background Layer 1

Collection framework

It is a set of interfaces and classes which provide a ready-made architecture. The Iterable interface is the root interface. A class that implements the Iterable can be used with the for-loop. Then goes the Collection interface that extends Iterable interface. It is implemented through its subinterfaces like List, Set, and Queue.

List interface

It is an ordered collection that allows us to store and access elements sequentially. Classes that implement this interface are: ArrayList, LinkedList, Vector, Stack.

Classes ArrayList vs LinkedList

Common:

  1. Both implement interface List
  2. Not fixed lenth
  3. Maintain the insertion order of the items
  4. Can hold duplicate items

Difference:

ArrayList:

  1. There is an usual Array inside
  2. When we need to add an item but there is no space:
    - a new inner Array is created inside ArrayList, that 1.5 bigger than a previouse one
    - all items are copied from the old inner Array to the new one
    - the old Array will be destroyed
  3. Operations like add and remove elements from a middle of an ArrayList work slower then in LinkedList, because all elements all elements after that position are shifted
  4. Operations get and set work faster because we make direct request to the item by its index. Also add value to the end of an ArrayList works faster then in LinkedList.
  5. Has Random access that means that we can reach a needed element directly, we don't need to iterate all elements.
  6. Stores a single value in a single position

LinkedList:

  1. There is a collection of nodes inside, that have links to each other (Doubly Linked List, each node stores 3 values (previous address, data, and next address))
  2. Operations like add or remove nodes work faste because nodes are not shifted, just links are changed
  3. Operations like get or set element by index work slower because to get a node for example with index 140 we need to check all nodes from the start or from the end (sequential access)
  4. Linked lists have a special member called "Head", which gives the address of the first node.
  5. Implements the Queue and the Deque interface

Summary:

1 – Use ArrayList if there are a lot of get() operations, or add() at the end of a list.

2 – Use LinkedList if there are a lot of add(), remove() operations, especially from the middle or start of a list