What are important differences between array list and linked list. How array list is different from linked list. What are the key differences between linked list and array list.
What is Array List ?
Array list is a data structure used to store objects in the form of array. The array list is same as that of array except that array can’t grow in size where as array list can grow in size.
Why Array List Introduced ?
Initially when we are using array the size was fixed and initially at the time of creation of array itself we need to specify how many elements need to be stored in the array. But in some cases or most of the cases it will be not be known how many elements we are going to store in the array, so when we try to increase the size we can’t.
So in order to overcome this problem array list was introduced, whose size is dynamic and need not to specify at the time of declaration. So you can just declare a array list and start storing the elements inside it, so when we reach the end of array list capacity the size of the array will be automatically increased.
How does an Array List Work Internally ?
When we create an array list a memory will be allocated (default size unless given explicitly). As we add elemnts to the array list the elements will be stored according to sequence. Once we reach out to end of the array list and we still try to add elements to array list then new array list will be created according to the incremental size of the array list. Now all the elements in old memory will be copied to new memory location and further elements will be added to the new memory location and reference will be changed to new one.
Again the same step will be repeated if we reach at the end of the size of array. New memory location will be created depending on the incremental capacity formula and old elements will be copied to new memory location and reference will be given for new memory location.
What is Linked List ?
Linked list is a data structure where elements will be stored in the form of nodes. Where each node represents one element.
- Here each node will be holding one element.
- Each node will be storing address of previous node (node which is prior to present node) and future node (node which is ahead of present node).
- As it is storing the address of 2 nodes it is called as “Doubly linked list”. If it is storing only one node’s address it is called as singly liked list.
- The advantage of linked list is faster transactions, we can access the elements easily and faster.
- If we are doing repeated add and remove operations on data structure then we have to use Linked list, as add and remove operations will be faster in the linke list.
- So these are the reasons why linked list is preffered as compared to array list.
How a Linked List ?
When we create a linked list and add some elements, one element will be stored in the form of node. Again when we add another element it will be stored in the form of next node. So as we keep adding elements to linked list they will be stored in form of nodes. Here each node will be keeping the address of previous node and next node.
|Array List||Linked List|
|The elements are stored using growable arrays||The elements are stored using doubly liked list|
|Initial capacit is declared||No initial capacity is declared|
|Slower in operations||Faster in operations|
|Addition and removal of elements is slower ||Addition and removal of elements is faster|
|It is not preffered when repeated addition and deletion of elements is needed||It is preffered when repeated addition and deletion of elements is needed|
More Video on JAVA can be found Here