What's the difference between array and linked list. This is very important question and it is mostly asked in interviews. Apart from interviews, if you know when to use linked list and arrays in programming then definitely it'll improve your programming skills.
Both arrays and linked list is used to store linear data of similar types, but they both have some advantages and disadvantages over each other.
1. a) In Array element(data) is stored in contiguous memory location. That's why you can access it's value using subscript variable.
For example - int a[]={3,5,4,2,1}
I have declared an array. If i have to access the value at third index, i can easily access it's value by using a[2].
b) In linked list, An element is not stored in contiguous memory block. To access any value in a linked list we need to traverse it.
Insert a node at the head of linked list.
Insert a node at the tail of linked list.
2. a) In array, Insertion and deletion is expensive. To insert and delete an element in an array we need traverse and create the room for a new element. To create the room for a new element existing elements need to be shifted.
Let's understand this concept through example -
For example,
int a[] = {1, 2, 3,4,5,6.....}.
And if we want to insert a new element at 10th position, then we need to move the element after 10th position to create a room for new element.
Program to insert an element in an array
Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete an element stored at 10th index. After deleting an element of 10th index we have to shift all the element after 10th index.
Program to delete an element in an array.
1. You don't need to know in advance the number of elements to be stored in a list . Because memory in linked list is allocated dynamically. So it is easy to allocate memory when we need it.
2. Insertions and deletions can be handled efficiently without much overhead.
1. In Linked List Random access is not allowed so to access elements we need to traverse linked list sequentially.
2. Extra memory is required to store the pointer which points to the next node.
3. Array provides better cache locality that can make a pretty big difference in performance.
What is the difference between Array and Linked List
Both arrays and linked list is used to store linear data of similar types, but they both have some advantages and disadvantages over each other.
1. a) In Array element(data) is stored in contiguous memory location. That's why you can access it's value using subscript variable.
For example - int a[]={3,5,4,2,1}
I have declared an array. If i have to access the value at third index, i can easily access it's value by using a[2].
b) In linked list, An element is not stored in contiguous memory block. To access any value in a linked list we need to traverse it.
Insert a node at the head of linked list.
Insert a node at the tail of linked list.
2. a) In array, Insertion and deletion is expensive. To insert and delete an element in an array we need traverse and create the room for a new element. To create the room for a new element existing elements need to be shifted.
Let's understand this concept through example -
For example,
int a[] = {1, 2, 3,4,5,6.....}.
And if we want to insert a new element at 10th position, then we need to move the element after 10th position to create a room for new element.
Program to insert an element in an array
Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete an element stored at 10th index. After deleting an element of 10th index we have to shift all the element after 10th index.
Program to delete an element in an array.
b) In linked list memory is allocated dynamically and the pointer to that memory location is stored in Previous Node. So insertion and deletion can be done easily as compared to arrays.
Programming question on linked list, stack and arrays.
Programming question on linked list, stack and arrays.
Advantage of Linked List
1. You don't need to know in advance the number of elements to be stored in a list . Because memory in linked list is allocated dynamically. So it is easy to allocate memory when we need it.
2. Insertions and deletions can be handled efficiently without much overhead.
Disadvantage of Linked List
1. In Linked List Random access is not allowed so to access elements we need to traverse linked list sequentially.
2. Extra memory is required to store the pointer which points to the next node.
3. Array provides better cache locality that can make a pretty big difference in performance.
No comments:
Post a Comment