Are lists dynamic arrays?

An Array is a simple structure of a fixed size for holding data. It is not a List, so it does not implement methods such as add[] and you cannot put more items in it once it is full. A Dynamic Array implements the List methods while using an Array internally to store the items.

Q: How does it implement add? When I add a regular item to an array, I need to keep track of the index!
A: It keeps an index internally of the next open spot in the array. It increments the index when an item is added, and 'decrements' the index when an item is removed.

Q: What happens when an item is added and its array is full? Will it cause the dreaded ArrayIndexOutOfBounds Exception?
A: No, it's a Dynamic Array. If the array is filled up, it will dynamically create a new larger array so it can hold more values. You can add items to the dynamic array without worrying about this behind-the-scenes process.

The dynamic array also lets you insert and delete items from it, and it will automatically shift over items on the right.

Dynamic Array Library Class

An ArrayList is Java's class for Dynamic Arrays. See Learneroo's ArrayList Tutorial or the ArrayList reference for more info. In Ruby and Javascript the Array is actually a Dynamic Array, as is the List in Python.

ArraysLists vs. LinkedLists

The ArrayList provides 'instant' access to any location inside them, while the LinkedList needs to iterate through the list to get to a specific location. However, the LinkedList can insert and delete items without copying over data, and it doesn't need to copy over data when full, since it doesn't use an internal array.

In general you should use an ArrayList since it performs better overall. However, if you're going to be inserting or deleting a large number of items and rarely access items by index value, a LinkedList can be faster.

Arrays vs. ArrayLists

In general, you should use ArrayLists, since they're more flexible. However, it sometimes makes sense to use an array such as if you are dealing with a fixed amount of data or if you have extreme performance requirements.

Challenge

In this challenge, an operation is each time a Node in a list or a cell in an array is accessed. How many operations will be performed on the LInkedList in the code below? How many operations will be performed if the LinkedList is changed to an ArrayList?