Updated: Jun 3, 2022
Linked list is a linear data structure. Each element in a linked list is an individual object. These individual objects are called nodes. As the name suggests a linked list is formed by interconnecting a series of such nodes. Nodes are connected using pointers.
Each node internally contains data and a link to the next node (address of the next node). In general a node in a linked list appears as shown in figure below:
The first node in a linked list is called a head node. The head node is the entry point to a linked list. Unlike arrays linked list elements are not indexed, we cannot access any random element using an index like arrays. We always start traversing the linked list from the head node no matter which element we need to access in the list.
The last node in a linked list is not connected to any node. The next pointer of the last node always points to null.
Linked list can contain any type of data like int, string, character etc. Elements can all be unique or it can also contain duplicates. Also the elements in a linked list can be sorted or unsorted.
Unlike arrays elements in a linked list are not stored in contiguous locations in memory. Each node is stored in arbitrary location in memory and connected to each other using next pointer.
Why Linked List?
Arrays are fixed size structures. Once an array is declared you cannot change its size. If the array is full and a new element needs to be added, you need to declare a new array (of larger size) and copy all the elements from the old array into the new array. This can be an expensive operation especially for large arrays. Linked list unlike arrays are dynamic in nature, they do not have a fixed size. We just a have to create a new node and link it to our list each time a new element needs to be added.