What is a Linked list?
Introduction:
A linked list is an ordered collection of data elements, each containing a link to its successor (and sometimes its predecessor). It is a linear data structure in which the entries are not kept in memory in the same order. A linked list's elements are connected via pointers.
A linked list is made up of nodes, each of which has a data field and a reference (link) to the next node in the list.
Why do we need Linked list?
You might think, why in the world do we need a linked list when we have arrays to store all our data already? To answer this we need to first understand the difference between Arrays and linked lists.
Difference between Arrays and Linked lists:
There are many differences between an Array and a Linked list. Here are just couple of them:
Because the size of the arrays is predetermined, we must know how many elements we can have ahead of time. Furthermore, regardless of the utilization, the allocated memory is always equal to the maximum limit. Sizes of linked list on the other hand can be dynamically modified.
Array uses static memory. The term "static memory" refers to memory that is fixed in size and cannot be modified during runtime, whereas dynamic memory is used by the linked list. The term "dynamic memory" refers to the ability to adjust the memory size at runtime to meet our needs.
In the case of an array, memory is allocated at compile-time whereas memory is allocated at run time in a Linked list.
Memory utilization is better in Linked list because memory can be allocated or deallocated at the run time according to our requirement. But in case of an Array, its inefficient. For eg. if you declare an Array of size 10 but it only contains 7 elements so the rest of the memory will be unused.
Types of Linked lists:
There are mainly three types of Linked lists.
Simple Linked list: Item navigation in a simple linked list is merely forward.
Doubly linked list: Items in a Doubly Linked List can be moved forward and backward.
Circular Linked List: The last item in a circular linked list has a link to the first element labelled next, and the first element has a link to the last element labelled previous.
All of them deserve a separate article to be understood properly.
This article is all about giving you a basic idea of what a Linked list is. You can check our other blogs and continue learning!