What is the difference between ArrayList and LinkedList? Why are they needed if arrays exist?

ArrayList and LinkedList are two implementations of the List interface in Java, but they differ in internal structure and performance.

• ArrayList is based on a dynamic array. It provides fast index-based access (O(1)), but insertions and deletions in the middle of the list require shifting elements (O(n)).
• LinkedList is implemented as a doubly linked list. Access by index is slower (O(n)), but insertions and deletions in the middle of the list are faster (O(1)), if there is a reference to the node.

Why are these structures needed if there is an array?

• Arrays have a fixed size and cannot be dynamically expanded.
• ArrayList and LinkedList allow dynamic resizing of the collection.
• They provide convenient methods for working with elements (adding, removing, searching).

Example of using ArrayList:

ArrayList<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
System.out.println(list.get(1)); // Python

The choice between them depends on the scenario: if fast random access is needed — ArrayList, if you often insert/delete in the middle — LinkedList.