Gain insights into Java Collections Framework. Delve into lists, sets, and hashmaps. Learn about data modification, sorting, thread-safety, and internal workings for efficient usage.

Collection is one of the most important topics for Java programming. Without the proper knowledge of every collection type in Java, it becomes difficult for you to decide which option to pick in a particular scenario.

This course will give you a great understanding of all collection types available in the Collections Framework like lists, linked lists, sets, and hashmaps. 

After completing this course, you will know how data can be modified within a collection, how to sort a collection, and how it can be made thread-safe. You will also cover the internal working of each Java collection so you can work with them more efficiently.

Collections in Java

The **LinkedList** class in Java implements the **List** and the **Deque** interface. Some of the salient features of a LinkedList are:

1. The elements are inserted in the order of insertion.

2. It supports duplicate elements.

3. We can add any number of null elements.




# Internal implementation of LinkedList

The **LinkedList** class has a static inner class called `Node`. This class contains three fields:

`item` - This contains the value of the current element.

`next` -  This contains the pointer to the next element.

`prev` - This contains the pointer to the previous element.

Below is the code for the `Node` class.

```Java
 private static class Node<E> {
     E item;
     Node<E> next;
     Node<E> prev;

     Node(Node<E> prev, E element, Node<E> next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
     }
 }
```

When an element is added to the **LinkedList**, a new `Node` instance is created. Depending on where the new node is being added, the **prev** and **next** fields are set.

When a node at index `i` is removed, the `next` field of node at index `i-1` is set to the node at index `i+1`. Similarly, the `prev` field of node at index `i+1` is set to node `i-1`.

# Time complexities for LinkedList operations

Let’s see what the time complexities are for different operations in a LinkedList.

## Adding an element
The complexity of adding an element in a **LinkedList** is $O(1)$. If we need to search for the position where the Node needs to be inserted, then the complexity is $O(n)$, but the element is usually inserted at the beginning or end, which makes it $O(1)$.

The biggest benefit of **LinkedList**, in comparison to an array, is that in a **LinkedList**, in comparison to an array, is that when new elements are added or removed, the other elements are not rearranged.

## Removing an element
Removing an element is also an $O(1)$ operation if we are aware of the position of the element that needs to be removed. If we need to search and remove an element, it is an $O(n)$ operation.

## Searching an element
Searching an element is an $O(n)$ operation, as the entire **LinkedList** is iterated to search the element in the worst case.

Let's Begin

Lists in Java

LinkedList in Java

CopyOnWriteArrayList in Java

Sets in Java

TreeSet in Java

HashMap In Java

TreeMap in Java

LinkedHashMap in Java

Additional Map Implementations

Arrays Class

Collections Class

LinkedList: Introduction

Internal implementation of LinkedList