| In this program, we will create a singly linked list and delete a node from the end of the list. To accomplish this task, we first find out the second last node of the list. Then, make second last node as the new tail of the list. Then, delete the last node of the list. In the above example, Node was the tail of the list. Traverse through the list to find out the second last node which in this case is node 4. Make node 4 as the tail of the list. Node 4's next will point to null. Algorithm
a. DeleteFromEnd[] will delete a node from the end of the list:
a. display[] will display the nodes present in the list:
Program:public class DeleteEnd { //Represent a node of the singly linked list class Node{ int data; Node next; public Node[int data] { this.data = data; this.next = null; } } //Represent the head and tail of the singly linked list public Node head = null; public Node tail = null; //addNode[] will add a new node to the list public void addNode[int data] { //Create a new node Node newNode = new Node[data]; //Checks if the list is empty if[head == null] { //If list is empty, both head and tail will point to new node head = newNode; tail = newNode; } else { //newNode will be added after tail such that tail's next will point to newNode tail.next = newNode; //newNode will become new tail of the list tail = newNode; } } //deleteFromEnd[] will delete a node from end of the list public void deleteFromEnd[] { //Checks if the list is empty if[head == null] { System.out.println["List is empty"]; return; } else { //Checks whether the list contains only one element if[head != tail ] { Node current = head; //Loop through the list till the second last element such that current.next is pointing to tail while[current.next != tail] { current = current.next; } //Second last element will become new tail of the list tail = current; tail.next = null; } //If the list contains only one element //Then it will remove it and both head and tail will point to null else { head = tail = null; } } } //display[] will display all the nodes present in the list public void display[] { //Node current will point to head Node current = head; if[head == null] { System.out.println["List is empty"]; return; } while[current != null] { //Prints each node by incrementing pointer System.out.print[current.data + " "]; current = current.next; } System.out.println[]; } public static void main[String[] args] { DeleteEnd sList = new DeleteEnd[]; //Adds data to the list sList.addNode[1]; sList.addNode[2]; sList.addNode[3]; sList.addNode[4]; //Printing original list System.out.println["Original List: "]; sList.display[]; while[sList.head != null] { sList.deleteFromEnd[]; //Printing updated list System.out.println["Updated List: "]; sList.display[]; } } } Output: Original List: 1 2 3 4 Updated List: 1 2 3 Updated List: 1 2 Updated List: 1 Updated List: List is empty Next TopicJava Programs |
- Send your Feedback to [email protected]
The problem deals with removing the last element present in the linked list. Say for example we have a list 1 -> 2 -> 3 -> 4 -> 5 so after removeLast[] operation our list will be 1 -> 2 -> 3 -> 4.
We are given a linked list class which has three data members:
1. Head: It points to the starting node of the linked list.
2. Tail: It points to the last node of the linked list.
3. Size: It stores the current length [or size] of the linked list.
The problem can be categorized into the following cases:
1. When size == 0
This is the case when our list is empty. As we can not remove an element from an empty list so in this case we just need to prompt an error message and return without changing the data members of the linked list class.
2. When size == 1
This is the case when our list has only one node. Removing this node will result in an empty list. As we know that for an empty list both head and tail points to null and the size is equal to zero, so we just need to update the data members in this case.
3. When size > 1
This is the general case of our problem. Earlier in our removeFirst[] problem we just update our head with head.next and we get our result, but in a singly linked list there is no way to do something like this, tail = tail.prev so we need to go the traditional way, i.e. by traversing the list up to the node before tail node and then set its next data member to null and we also need to decrement the size of our list.
Below is the implementation in Java:
public void removeLast[] { if [size == 0] { System.out.println["List is empty"]; } else if [size == 1] { head = tail = null; size = 0; } else { Node temp = head; for [int i = 0; i < size - 2; i++] { temp = temp.next; } tail = temp; tail.next = null; size--; } }
java false
Time Complexity: O[n]
The time complexity for the function is linear as the traversal of the linked list is involved.
Space Complexity: O[1]
The space complexity for the function is constant as we have only used referenced variables in our algorithm.
Js program for Delete last node of linked list. Here problem description and explanation.
/* Node JS program for Delete the last node of singly linked list */ // Linked list node class LinkNode { constructor[data] { this.data = data; this.next = null; } } class SingleLL { constructor[] { this.head = null; this.tail = null; } // Add new node at the end of linked list addNode[value] { // Create a new node var node = new LinkNode[value]; if [this.head == null] { this.head = node; } else { this.tail.next = node; } // Set new last node this.tail = node; } // Display linked list element display[] { if [this.head == null] { console.log["Empty Linked List"]; return; } var temp = this.head; // iterating linked list elements while [temp != null] { process.stdout.write[temp.data + " → "]; // Visit to next node temp = temp.next; } console.log["NULL"]; } // Delete last node of singly linked list deleteLastNode[] { if [this.head == null] { console.log["Empty Linked List"]; return; } else { var temp = this.head; var find = null; // Find second last node while [temp.next != null] { find = temp; temp = temp.next; } if [find == null] { // Delete head node of linked list this.head = null; this.tail = null; } else { // Set new last node this.tail = find; find.next = null; } } } } function main[] { var sll = new SingleLL[]; // Linked list // 1 → 2 → 3 → 4 → 5 → 6 → NULL sll.addNode[1]; sll.addNode[2]; sll.addNode[3]; sll.addNode[4]; sll.addNode[5]; sll.addNode[6]; console.log["Before Delete "]; sll.display[]; sll.deleteLastNode[]; console.log["After Delete "]; sll.display[]; } // Start program execution main[];Output
Before Delete 1 → 2 → 3 → 4 → 5 → 6 → NULL After Delete 1 → 2 → 3 → 4 → 5 → NULL