Linked List

Linked List

What is LinkedList:

A linked list is a linear data structure where each element is a separate object, which is connected together via links. Linked list elements are not stored at contiguous locations. 

Why we need LinkedList:

• Arrays can store only linear data of similar types and contiguous locations.

• The size of the array is fixed: we must know the upper limit of the number of elements in advance.

• It may possible that we don’t have contiguous free memory, in this situation we can’t declare an array.

Drawbacks:

1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists efficiently with its default implementation.

2) Extra memory space for a pointer is required with each element of the list.

3) Not cache-friendly. Since array elements are contiguous locations, there is a locality of reference which is not there in case of linked lists.

Linked List vs Array:

1.  An array is the data structure that contains a collection of similar type data elements whereas the Linked list is considered as a non-primitive data structure contains a collection of unordered linked elements known as nodes.

2.  In a linked list though, you have to start from the head and work your way through until you get to the fourth element.

3.  Accessing an element in an array is fast, while Linked list takes linear time, so it is quite a bit slower.

4.  Operations like insertion and deletion in arrays consume a lot of time. On the other hand, the performance of these operations in Linked lists is fast.

5.  Arrays are of fixed size. In contrast, Linked lists are dynamic and flexible and can expand and contract its size.

6.  In an array, memory is assigned during compile time while in a Linked list it is allocated during execution or runtime.

7.  Elements are stored consecutively in arrays whereas it is stored randomly in Linked lists.

Why we need LinkedList:

What is LinkedList: