**Introduction of Linked List in general:**

Linked List can be classified as Singly Linked List or Doubly Linked List. For this tutorial, we will concentrate only on Singly Linked List.

In Linked List, each element holds two things. Value of current element and a link that points to the next element in a List. The last element points to the null.

Linked List is dynamic data structure and hence preferred over simple array when size of the array can not be determined in advance. Linked List can increase or decrease its size dynamically.

**Similarity between Array and Linked List:**

Both are index based data structure.

**Difference between Array and Linked List:**

Size of an Array is fixed and can not be changed at run time while Linked List can expand or shrink at run time.

**Linked List in JAVA:**

Linked List is an implementation of List interface. It is not synchronized. If more than one thread try to access elements in List simulataneously and one of the thread modifies the element, JVM throws concurrentmodification exception. Hence, Linked List should be synchronized in a multi threaded enviornment.

**Complexity Analysis of Linked List:**

1. Adding element at the head : This function is performed in constant time. Hence, complexity of adding element at the head is O(1).

2. Adding element at perticular index: This function requires program to iterate till N^{th} index and hence it depends on number of elements in Array List. Hence, this function is called Linear function. Complexity of adding element at the given index is O(n).

3. Updating element at the head : Again, this function is performed in constant time. Hence, complexity of updating element at the head is O(1).

4. Updating element at perticular index: This function requires program to iterate till N^{th} index. Complexity of Updating element at the given index is O(n).

5. Removing element at the head : This function is performed in constant time. Hence, complexity of removing element at the head is O(1).

6. Removing element at perticular index: This function requires program to iterate till N^{th} index and hence it depends on number of elements in Array List. Hence, this function is called Linear function. Complexity of Removing element at the given index is O(n).

Linked List class in JAVA provides following methods:

1. add(int index, Object element)

2. add(Object element)

3. addAll(int index, Collection elements)

4. addAll(Collection elements)

5. addFirst(Object element)

6. addLast(Object element)

7. contains(Object element)

8. get(int index)

9. getFirst()

10. getLast()

11. indexOf(Object element)

12. remove(int index)

13. remove(Object element)

14. toArray()

More about Linked List including time complexity is coming very soon.

Java is a trademark of Oracle.

Apekshit.com is just for learning and testing. To improve basic understanding we provide some examples. We are constantly reviewing it to avoid errors, but we cannot warrant full correctness of all content.