Well Let's Have a look into a image and i think this will completely clear your myths and know why do we really need and use Linked Lists. We all know this a good programmar always thinks in terms of memory
I Know its pretty confusing but lets see
Let's have a look into the following grid
Here there are yellow and blue datas
where blue datas are connected via some arrows which we call them as pointers
Yellow datas has been arrnaged in a contiguous pattern forming a array like data structure
Basic Element of linked list is its Node
A node consists of
Value
next pointer
we can consider it too the address(but we dont use while problem solving) jvm takes care of this
public class ListNode{
public int val;
public ListNode next;
public ListNode(int val){
this.val = val;
}
}
A linked lists can consists of N number of nodes a single head and a single null at the ending of the node which is generally referred as tail of the list
How can we insert Datas aka (Nodes) ?
case 1 : At the beginning
case 2 : At the end
case 3 : At a location
Case 1:
public ListNode insertAtBeginning(ListNode head, int valToInsert){
ListNode newNode = new ListNode(valToInsert);
newNode.next = head;
head = newNode;
return head;
}
Case 2:
public ListNode insertAttheEnd(ListNode head, int valToInsert){
ListNode ptr = head;
while(ptr.next != null){
ptr = ptr.next;
}
ListNode newNode = new ListNode(valToInsert);
ptr.next = newNode;
newNode.next = null;
return head;
}
Case 3:
public ListNode insertAtthePosition(ListNode head, int valToInsert, int position){
ListNode newNode = new ListNode(valToInsert);
ListNode ptr = head;
for(int i = 0; i < position; i++){
ptr = ptr.next;
}
ptr.next = newNode;
newNode.next = ptr.next.next;
return head;
}
How to Delete the datas aka (Nodes) ?
case 1: From the Beginning
case 2: From the End
case 3: From a Location
case 1:
public ListNode deletionFromTheBeginning(ListNode head){
head = head.next;
return head;
}
case 2:
public ListNode deletionFromTheEnd(ListNode head){
ListNode ptr = head;
while(ptr.next.next != null){
ptr = ptr.next;
}
ptr.next = null;
return head;
}
case 3:
public ListNode deletionFromThePosition(ListNode head, int position){
ListNode ptr = head;
for(int i = 0; i < position - 1; i++){
ptr = ptr.next;
}
ListNode nextNode = ptr.next.next;
ptr.next = nextNode;
return head;
}