What is a Linked List, Anyway ?
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.
In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list.
Arrays Vs Linked List
Why Linked List?
Suppose your program expects some input from the user. Now there are 3 possible scenarios: 1. You and and your user both know the size of input, in this case go for array as it has fastest insert, search times. 2ndly you may not but user may know the size of input. Then you can ask for the size and then declare array of that size dynamically.
But if your user also does not know the input size (It may happen, think you are writing a text editor)?
You may declare a huge array, but still there is chance of overflow, or huge wastage of space.
Linked list here comes into play, you allocate one unit of space at a time and link it with a new one when required. This helps you to optimize space.
linked list has got another advantage, as the space needs not be contiguous, chances of space unavailability is quite less, which happens in case of large dynamic array allocation.
time and algorithmic advantages are also there as mentioned brilliantly in the other answers.
Advantages of Linked Lists over arrays:
- Dynamic Array.
- Ease of Insertion/Deletion.
Representation of Linked Lists:
A linked list is represented by a pointer to the first node of the linked list. The first node is called the head of the linked list. If the linked list is empty, then the value of the head points to NULL.
Each node in a list consists of at least two parts:
- A Data Item (we can store integer, strings, or any type of data).
- Pointer (Or Reference) to the next node (connects one node to another) or An address of another node
In C, we can represent a node using structures. Below is an example of a linked list node with integer data.
// A linked list node
struct Node {
int data;
struct Node* next;
};
In Java or C#, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.
class LinkedList {
Node head; // head of the list
/* Linked list Node*/
class Node {
int data;
Node next;
// Constructor to create a new node
// Next is by default initialized
// as null
Node(int d)
{
data = d;
next = null;
}
}
In C#
class LinkedList {
// The first node(head) of the linked list
// Will be an object of type Node (null by default)
Node head;
class Node {
int data;
Node next;
// Constructor to create a new node
Node(int d) { data = d; }
}
}
Types of Linked Lists:
- Simple Linked List — In this type of linked list, one can move or traverse the linked list in only one direction.
- Doubly Linked List — In this type of linked list, one can move or traverse the linked list in both directions (Forward and Backward)
- Circular Linked List — In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer and the first/head node contains the link of the last node of the linked list in its previous pointer
- Doubly Circular Linked List —Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two consecutive elements are linked or connected by the previous and next pointer and the last node points to the first node by the next pointer and also the first node points to the last node by the previous pointer.
Advantages Of Linked List:
- Dynamic data structure: A linked list is a dynamic arrangement so it can grow and shrink at runtime by allocating and deallocating memory. So there is no need to give the initial size of the linked list.
- No memory wastage: In the Linked list, efficient memory utilization can be achieved since the size of the linked list increase or decrease at run time so there is no memory wastage and there is no need to pre-allocate the memory.
- Implementation: Linear data structures like stacks and queues are often easily implemented using a linked list.
- Insertion and Deletion Operations: Insertion and deletion operations are quite easier in the linked list. There is no need to shift elements after the insertion or deletion of an element only the address present in the next pointer needs to be updated.
Drawbacks of Linked Lists:
- Random access is not allowed. We have to access elements sequentially starting from the first node(head node). So we cannot do a binary search with linked list efficiently with its default implementation.
- Extra memory space for a pointer is required with each element of the list.
- Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.
