Linked List

1. introduction

LinkedList is a doubly linked list which implements the List and Queue Iterfaces. It is a part of Java's Collections framework.

2. Features

• It maintains the insertion order
• It can have duplicate and null values
• It is not synchronized, means it is not thread-safe
• It's Iterators and ListIterators are fail-fast, which means after the iterator's creation, if the list is modified a ConcurrentModificationException is thrown

Although LinkedList is not synchronized, we can get a synchronized version of it by calling the Collections.synchronizedList method.

List list = Collections.synchronizedList(new LinkedList(...));

3. Comparison to ArrayList

Both ArrayList and LinkedList implements the List interface, However, they differ completely in the way how they store and retrieve the elements.

3.1 Structure

An ArrayList is an index based data-structure backed by an Array. It provides random access to its elements with performance equal to O(1).