Homework SourseGive an algorithm for finding the second to last node in a s
Give an algorithm for finding the second to last node in a singly linked list in which the last node is indicated by a null next reference. It needs to have a main Java class with main() function, inside which you can demonstrate the correctness and outputs from your Java code.
Solution
Hi, Please find my implementation.
Please let me know in case of any issue.
######### LinkedList.java ##########
class NodeList {
int data;
NodeList next;
public NodeList(int data) {
this.data = data;
next = null;
}
}
public class LinkedList {
private NodeList head;
private int size;
public LinkedList() {
head = null;
size = 0;
}
public void addFront(int data) {
NodeList newNode = new NodeList(data);
newNode.next = head;
head = newNode;
size = size+1;
}
public int removeFront(){
if(head == null){
System.out.println(\"List is empty\");
return -999;
}
int value = head.data;
head = head.next;
size = size-1;
return value;
}
public void addBack(int value){
if(head == null){
head = new NodeList(value);
}else{
NodeList temp = head;
while(temp.next != null)
temp = temp.next;
temp.next = new NodeList(value);
}
size = size+1;
}
public int removeBack(){
// list is empty
if(head == null){
System.out.println(\"List is empty\");
return -999;
}
// only one node
if(head.next == null){
int value = head.data;
head = null;
return value;
}
NodeList temp = head;
while(temp.next.next != null)
temp = temp.next;
int value = temp.next.data;
temp.next = null;
size = size-1;
return value;
}
public int getLength(){
return size;
}
public void display(){
NodeList temp = head;
while(temp != null){
if(temp.next!=null)
System.out.print(temp.data+\"-->\");
else
System.out.println(temp.data);
temp = temp.next;
}
System.out.println();
}
public NodeList getSecondToLastNode(){
// fewer node (it should be at leat 2)
if(head == null || head.next == null)
return null;
NodeList p1 = head;
NodeList p2 = head.next;
while(p2 != null){
p2 = p2.next;
p1 = p1.next;
}
return p1; // it points to econd last node
}
}
######### Test #######
public class LinkedListTest {
public static void main(String[] args) {
LinkedList list = new LinkedList();
System.out.println(\"Adding elements to the front......\");
list.addFront(8);
list.display();
list.addFront(33);
list.display();
list.addFront(58);
list.display();
System.out.println(\"Length of linked list: \"+list.getLength());
System.out.println();
System.out.println(\"Adding elements to the back......\");
list.addBack(1);
list.display();
list.addBack(34);
list.display();
list.addBack(20);
list.display();
System.out.println(\"Length of linked list: \"+list.getLength());
System.out.println();
System.out.println(\"Removing elements from the front.....\");
list.removeFront();
list.display();
list.removeFront();
list.display();
System.out.println(\"Length of linked list: \"+list.getLength());
System.out.println();
System.out.println(\"Removing elements from the back.....\");
list.removeBack();
list.display();
list.removeBack();
list.display();
System.out.println(\"Length of linked list: \"+list.getLength());
System.out.println();
System.out.println(\"Second last Node Demo---------\ \");
NodeList secondLast = list.getSecondToLastNode();
System.out.println(\"Value of second last node: \"+secondLast.data);
}
}
/*
Sample run:
Adding elements to the front......
8
33-->8
58-->33-->8
Length of linked list: 3
Adding elements to the back......
58-->33-->8-->1
58-->33-->8-->1-->34
58-->33-->8-->1-->34-->20
Length of linked list: 6
Removing elements from the front.....
33-->8-->1-->34-->20
8-->1-->34-->20
Length of linked list: 4
Removing elements from the back.....
8-->1-->34
8-->1
Length of linked list: 2
Second last Node Demo---------
Value of second last node: 1
*/
