| title | description | hide_table_of_contents | keywords | ||||
|---|---|---|---|---|---|---|---|
Linked List |
A linked list is a linear data structure that consists of nodes. Each node stores some data as well as the address of the next node. |
false |
|
In this tutorial you will learn about Linked Lists, and its implementation using Java.
Problem with using Arrays was that we have to have some idea about the size of the array that we require. To counter this we learnt about dynamic arrays. Linked list is another approach to tackle this problem. In linked lists we do not have to worry about the size at all.
A linked list is a linear data structure that has a series of connected nodes. Each node has two fields,
Each node in a linked list contains:
- A data item
- Address of next node
Both of these items are wrapped together in a class:
class Node {
int data;
Node next;
public Node(){
this.data = data;
this.next = null;
}
}Now we will create a Linked list using this Node class:
class LinkedList {
Node node1 = new Node();
Node node2 = new Node();
Node node3 = new Node();
// set 10 as the value for 1st node
node1.data = 10;
// set node2 as the next node for node1
node1.next = node2;
// set 20 as the value for 2nd node
node2.data = 20;
// set node3 as the next node for node2
node2.next = node3;
// set 30 as the value for 3rd node
node3.data = 30;
// this is not required. By default next of a node is NULL
node3.next = null;
}So now we have our first linked list.
The asterisk (*) signifies the address of the node, and not the value of that node.
In arrays the elements are contiguous, which means they are placed one after the other in the memory. However, in linked lists, the elements are scattered in the memory.
When we declare an integer array of size
That is the advantage linked lists have over array when it comes to memory. We have to look for smaller spaces to store the items, rather than chunks of contiguous space.
Numbers with # behind them are the addresses in memory where these nodes are stored. Here,
- Traversal
- Insertion
- Deletion
- Search
Let's see their implementation in a linked list.
We have to access each element of the linked list. Remember, the
Traversing through the linked list is fairly simple. We keep moving from the head towards the end of the list. We would know we have reached the last node when
// temp pointer that points to head initially
Node temp = head;
// check if next points to null
while (temp.next != null) {
// print the data stored in the current node
System.out.println(temp.data);
// move temp to the next node
temp = temp.next;
}You are given the head of a linked list and a number. Check if the given number is present in the linked list or not. Return true if present, else return false.
We will traverse the list and at each node we will check if we have the required element in the current node or not. If we found the element, return true. If we have iterated over the list and not not found the number, we will return false.
public static boolean findElement(Node head, int target){
Node ptr = head;
while (ptr != null) {
// compare the node element and the target number
if (ptr.data == target) {
// number found
return true;
}
// move pointer to the next node
ptr = ptr.next;
}
// number not found
return false;
}We can add element to the beginning, middle or at the end of the linked list.
You are given a linked list
Approach:
- Allocate memory for a new node
- Store the data
- Point
$next$ of new node to$head$ - Point
$head$ to the new node
// allocate memory
Node newNode = new Node();
// store data
newNode.data = 1;
// point next of new node to head
newNode.next = head;
// make head point to new node
head = newNode;You are given a linked list
Approach:
- Allocate memory for the new node
- Store the data in the new node
- Traverse to the node just before the required index
- Change the pointers
Node newNode = new Node();
newNode.data = 7;
Node temp = head;
// position at which we want to insert the new element
int pos = 3;
// loop runs only for i=2. when i=3, pos=3 as well, hence loop terminates.
for (int i = 2; i < pos; i++) {
if(temp.next!=null) {
temp = temp.next;
}
}
// here temp points to the 2nd node
newNode.next = temp.next;
// new node inserted after temp.
temp.next = newNode;One important thing to note here is that before breaking any connection in the linked list, we must first make the new connections. Make first, break later.
You are given a linked list
Approach:
- Allocate memory for the new node
- Store the data in the new node
- Traverse till the end of the list
- Make the
$next$ of the last node point to the new node
Node newNode = new Node();
newNode.data = 7;
Node temp = head;
// when temp.next is null, we'll know we are at the last node
while (temp.next != null) {
// move pointer to the next node
temp = temp.next;
}
// temp is now at the last node.
// point $next$ of the last node to the new node
temp.next = newNode;We can delete the first node, or the last node, or some other position in the middle.
To delete from the beginning we just have to move the
// change the pointer from the head node, to the next node.
head = head.next;- Move the pointer to the second last node
- Set the
$next$ pointer of second last node to point to$null$
Node temp = head;
// move the pointer to the second last node
while (temp.next.next != null) {
// move the current pointer to the next node
temp = temp.next;
}
temp.next = null;- Traverse to the element just before the node to delete
- Change the next of this node to point to next of the node to delete
Node temp = head;
// we are running the loop from 2 node because we have to move to the node
// just before the node we want to remove
for (int i = 2; i < pos; i++) {
// change pointer from current node to the next node
temp = temp.next;
}
temp.next = temp.next.next;- Make a temporary pointer
$ptr$ point to$head$ - Move
$ptr$ to next node until$ptr$ is$null$ - At each iteration, check if the data in
$ptr$ is same as the number we want. If yes, then return$true$ - Return
$false$ if number not found
Node ptr = head;
while (ptr != null) {
// check if data in current node matches the number we are looking for
if (ptr.data == num) {
// return true if number found
return true;
}
// move ptr to the next node
ptr = ptr.next;
}
// return false if number not found
return false;| Operation | Complexity | Explanation |
|---|---|---|
| Look up | We will have to iterate from head till the element we want | |
| Insertion at beginning | Simply change the head pointer | |
| Insertion at the end | Move from the head to the last item then change the pointers | |
| Deletion from the beginning | Simply change the head pointer | |
| Deletion from the end | Move from the head to the node just before the item you want to delete |
Example: 0237 - Delete Node in a Linked List
There is a singly linked list. You have to delete a
$node$ from the list. You are given the$node$ to delete but not the$head$ of the > list. Delete the given$node$ . Note that by deleting the$node$ , we$do not$ mean removing it from memory. We mean:
- The value of the given node should not exist in the linked list.
- The number of nodes in the linked list should decrease by one.
- All the values before node should be in the same order.
- All the values after node should be in the same order.
Change the value of the
class Solution {
// we are given a node to delete
public void deleteNode(ListNode node) {
// check if the current node is second last node
while(node.next.next!=null){
// change the value of current node to the value of next node
node.val = node.next.val;
// move node to the next node
node=node.next;
}
// we are at the second last node
// change value of the last node to the value of next node
node.val = node.next.val;
// change the next of last node to null
node.next = null;
}
}Given the head of a linked list, remove the nth node from the end of the list and return its head. Given Linked list:
$[1]$ ->$[2]$ ->$[3]$ ->$[4]$ ->$[5]$ for$n = 2$ change the list to$[1]$ ->$[2]$ ->$[3]$ ->$[5]$ .
- First we find the size of the list
-
$nth$ node from the$end$ is the$size - (n + 1)th$ node from the$front$ - Once we have the size, we can iterate over the list till the node just before the node to remove
- Change the pointers to remove the node
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode ptr = head;
// find the size
int size = findSize(head);
ptr = head;
// if size is equal to the n, remove node at head
if (size == n) {
ptr = ptr.next;
head = ptr;
return head;
}
// move ptr to the node just before the node to remove
for (int i = 0; i< size - n - 1; i++) {
ptr = ptr.next;
}
// check if the node to remove is the last node
if (ptr.next.next != null){
ptr.next = ptr.next.next;
} else {
ptr.next=null;
}
return head;
}
// method to find the size of the list
public int findSize(ListNode head) {
// temporary pointer at head
ListNode ptr = head;
int size = 0;
// increase the size till we reach the end of the list
while (ptr != null) {
size += 1;
ptr = ptr.next;
}
return size;
}
}Example: 0234 - Palindrome Linked List
Given the
$head$ of a singly linked list, return$true$ if it is a$palindrome$ or$false$ otherwise.
- We use
$two pointer$ method and$recursion$ to solve this problem - We keep a
$global$ left pointer, that points to the current left node - As we go deep in recursion we move our
$right$ pointer forward towards the end of the list - When
$right$ pointer is at the end we compare its value to the$left$ node - If they are same we move
$left$ pointer forward and come out of the recursion - As we come out of the recursive call, out
$right$ pointer would move towards$left$ - If at any point the values are not same, we return
$false$
class Solution {
// global left pointer
static ListNode left;
public boolean isPalindrome(ListNode head) {
// point the left to head
left = head;
boolean b = check(head);
return b;
}
// recursive method that moves pointer towards right and compares values
private boolean check(ListNode right){
// if right is null, we have reached the end of the list
if(right == null){
return true;
}
boolean b = check(right.next);
// if at any point b is false, we return false. If this happens even once,
// no further comparisons would happen and each recursive call would return false
if(b == false){
return false;
} else {
// else compare the values
// if values are equal, move left towards right and return true to the previous call
if (left.val == right.val) {
left = left.next;
return true;
} else {
// if values not same, return false
return false;
}
}
}
}Example: 0328 - Odd Even Linked List
Given the
$head$ of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.The
$first$ node is considered$odd$ , and the$second$ node is$even$ , and so on.Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.
- We maintain three pointers,
$odd$ at the first node,$even$ at the second node and$evenhead$ also at the second node. -
$evenhead$ will not be changed. It will point to the starting of the list of even nodes. - The node after every even node, is an odd node.
- So,
$next$ node for current$odd$ node, would be$next$ node of the current$even$ node. - And
$next$ node for the current$even$ node, would be$next$ node of the just changed$odd$ node.
class Solution {
public ListNode oddEvenList(ListNode head) {
// we check if there are at least three nodes in the list
// if there are only two nodes, then first node is even and second node is odd
// if only one node, then first node is odd
// so just return head
if (head == null || head.next == null || head.next.next == null) {
return head;
}
// odd is at head
ListNode odd = head;
// make second node as even
ListNode even = head.next;
// keep a pointer evenhead at even. This will not be changed.
ListNode evenHead = even;
// we have to move odd to next of even
// so we check is even.next is null of even is null
while (even != null && even.next != null) {
// if not, then make odd.next point to even.next
odd.next = even.next;
// move odd to odd.next
odd = odd.next;
// even.next to odd.next
even.next = odd.next;
// move even to even.next
even = even.next;
}
// at this point we have connected all the even nodes together, and all odd nodes together
// now we connect the odd nodes, and even nodes
odd.next = evenHead;
return head;
}
}export const suggestedProblems = [ { "problemName": "206. Reverse Linked List", "difficulty": "Easy", "leetCodeLink": "https://leetcode.com/problems/reverse-linked-list/", "solutionLink": "" }, { "problemName": "86. Partition List", "difficulty": "Medium", "leetCodeLink": "https://leetcode.com/problems/partition-list/", "solutionLink": "" }, { "problemName": "148. Sort List", "difficulty": "Medium", "leetCodeLink": "https://leetcode.com/problems/sort-list/", "solutionLink": "" }, ]