Linked List
A Linked List is a linear data structure, where each element we can call it as a Node. Each node contains 1. Data (value) and 2. pointer/reference to the next node.
It doesn’t store the elements in contiguous memory
🧱 Structure of a Node (Singly Linked List):
class ListNode {
int val;
ListNode next;
}
Here ‘val’ -> holds the data
‘next’ -> points to the next node in the list
The last node’s next indicates with ‘null’, which means it is end of the list.
THE ONE AND ONLY ADVANTAGE IS IN THE LINKED LIST: We can add and remove elements in any position with just O(1)
If suppose, you want to create a Linked List in the following way:
1->2->3.
This is the way You supposed to do
public class Example {
public static class ListNode {
int val;
ListNode next;
ListNode (int val) {
this.val = val;
}
}
public static void main(String[] args) {
ListNode one = new ListNode(1);
ListNode two = new ListNode(2);
ListNode three = new ListNode(3);
one.next = two;
two.next = three;
ListNode head = one;
System.out.println(head.val);
System.out.println(head.next.val);
System.out.println(head.next.next.val);
}
}
🔁 Types of Linked Lists:
- Single Linked List
- Double Linked List
- Circular Linked List