What is difference between ArrayList and LinkedList?

Answer 1

ArrayList

LinkedList

1. ArrayList uses a dynamic array.

1..Linked List uses doubly linked list.

2. ArrayList is not efficient for manipulation because a lot of shifting is required.

2.. LinkedList is efficient for manipulation

Answer 2

Both ArrayList and LinkedList are used to store and manipulate data items, but they have different properties associated with them. In ArrayList, the data items are stored at contiguous locations ( memory locations adjacent to each other ), while in LinkedList, elements are stored in noncontiguous memory locations.ArrayList uses an array of data structures for its implementation, while a LinkedList uses a doubly linked list data structure. The doubly linked list is a linear data structure where the elements are not stored separately but are stored as part of the node. A node is an object with two parts, the data-storing part and the address-storing part. The data storing part stores the data, while the address part holds the references of the next node and the previous node in the list. Due to this, random access to elements takes a lot of time compared to ArrayList because ArrayList stores the index of elements since they are stored in a contiguous memory location. The random access to an element takes O(1) time in ArrayList while O(n) time in a LinkedList.

Another important difference between the two classes are is that in ArrayList, the time taken to manipulate data items is very large compared to LinkedList.This is so because ArrayList is implemented through the array structure, so whenever we want to delete a data item or shift a data item internally, the whole array has to be traversed to shift the memory bits as it happens in arrays. While in LinkedList, there is no concept or need for shifting of memory bits; hence, operations such as deletion or adding an element in the middle of the list, etc., happen at a much faster rate than it happens in ArrayList.The insertion and deletion of an element take O(n) time in ArrayList while O(1) time in a LinkedList.

The memory allocation to the ArrayList is done at compile time, while the memory allocation to LinkedList is done at run time. The memory required in LinkedList is also more than in ArrayList.This is because, along with the data items that need to be stored, the LinkedList needs extra memory for storing the addresses of the next and previous node. Since the deletion and insertion operations are very efficiently done in LinkedList, they are preferred over ArrayList, where insertion and deletion are done to data frequently.ArrayList is preferred when data is not being modified often, but random access to data is needed.