Describe and implement a singly-linked list in Java.
A Linked List is a collection of nodes (implemented as a class – see below at Node.java) where each node is connected to the next node by reference (address).
Each node is implemented as a class containing two private variables
- Data value (could be a String/integer/double/another class)
- Reference value of the next node
Unlike an array, where each cell had a specific cell number and could be accessed independent of other cells, access to a node (say, X) in a linked list is dependent on having a reference to the previous node (say, Y).
public class Node {
// Setting instance variables as private means only the containing class
// (in this case, Node) can access them directly. Outside classes need
// to use the 'getter' and 'setter' methods implemented below.
private int data;
private Node next;
// The constructor. This method creates a new Node with some int data 'value'
// and some next Node reference 'ref'
public Node(int value, Node ref) {
data = value;
next = ref;
}
// 'Getter' method for the data. Since only a getter method
// is defined for 'data', it is considered read-only or immutable.
public int getData() {
return data;
}
// 'Getter' method for the next Node
public Node getNextReference() {
return next;
}
// 'Setter' method for the next Node. Since both a setter
// and a getter method are defined, the instance variable
// 'next' is considered read/write or mutable.
public void setNextReference(Node value) {
next = value;
}
// Allows us to println references and be human-readable
public String toString()
{
String data = String.valueOf(this.data);
return "Data: " + data;
}
}public class LinkedList {
// References to the beginning (head) and end (tail)
// of the list
private Node head;
private Node tail;
// No-argument constructor. When we make a new list,
// it is empty, so both instance variables are set
// to null, or nothing
public LinkedList() {
head = null;
tail = null;
}
// Example:
// If the list is 1->2->3, then list.insertAtBack(4) gives us
// 1->2->3->4
public void insertAtBack(int word) {
// Only if we have a new, empty list. We need to set the head
// of the list. Since there is only one element in the list,
// that element is both the head and tail.
if (head == null) {
head = new Node(word, null);
tail = head;
}
// Otherwise, we do not have an empty List. We first save
// the current tail in a temporary variable. Then, the
// tail is updated to a new node with the given data, and
// then the previous tail's next reference to the new tail
else {
Node tempref = tail;
tail = new Node(word, null);
tempref.setNextReference(tail);
}
}
public void printList() {
// We assume that the head is only null if the list is empty
if (head == null) {
System.out.println ("The List is Empty");
}
// Otherwise, we need to traverse the list
else {
// Setting a temporary variable to the head of the list
// is necessary to traverse the list, and not lose the
// reference to the beginning
Node tempref = head;
System.out.println("The values so far in the list : ");
// If tempref is null, we're at the end of the list
while (tempref != null) {
// Print the data
System.out.print(tempref.getData());
// Move along the list
tempref = tempref.getNextReference();
// If we have another Node, and therefore are not
// at the end, print a connecting arrow.
if (tempref != null) {
System.out.print (" --> ");
}
}
System.out.println("\n");
}
}
}import java.util.Scanner;
public class LinkedListTest {
// Prints a helpful menu for the user
public static void Menu() {
System.out.println("1 - Insert At Back ");
System.out.println("2 - Quit");
}
public static void main(String[] args) {
System.out.println("Linked Lists");
// Two Scanner objects are required, due to a Java quirk
// in how streams are scanned.
Scanner scanner = new Scanner(System.in);
Scanner scanner1 = new Scanner(System.in);
int choice = 0, status = 0, entry = 0;
boolean flag = true;
LinkedList list = new LinkedList();
while (flag) {
// Print the menu
Menu();
status = 0;
// try-catch statements prevent Java Exceptions, or
// runtime errors. The Integer.parseInt() method can
// returned either the parsed integer, or causes an
// Exception if it is not a number. This Exception is
// 'caught' with the catch statement. By defining the
// Exception object as the generic 'Exception' type,
// it will catch all Exceptions that are subclasses of
// Exception, or all built-in Exceptions.
try {
choice = Integer.parseInt(scanner.nextLine());
}
catch (Exception e) {
System.out.println("Integers Only - Enter Again");
status = 1;
}
// The user chose to add a value to the list
if (choice == 1) {
System.out.println ("Enter the value?");
entry = scanner1.nextInt();
list.insertAtBack(entry);
}
// The user chose to end the program
else if (choice == 2) {
flag = false;
System.out.println ("End of Program");
}
// The user entered a number that was not a legal menu
// option, but still parsable by Integer.parseInt()
else if (status == 0) {
System.out.println ("Invalid Entry - Enter Again");
}
// Print the list after every entered value
list.printList();
}
}
}Linked Lists
1 - Insert At Back
2 - Quit
> what
Integers Only - Enter Again
The List is Empty
1 - Insert At Back
2 - Quit
> 34
Invalid entry - Choose from menu
The List is Empty
1 - Insert At Back
2 - Quit
> 1
Enter the value?
> 90
The values so far in the list:
90
1 - Insert At Back
2 - Quit
> 1
Enter the value?
> 789
The values so far in the list:
90 --> 789
1 - Insert At Back
2 - Quit
> 1
Enter the value?
> 678
The values so far in the list:
90 --> 789 --> 678
1 - Insert At Back
2 - Quit
> 2
End of Program
The values so far in the list:
90 --> 789 --> 678Add the following methods to the Linked List
isEmpty(), which returns true if the list is empty and false if the list is not empty.insertAtFront(int input), which inserts the input value at the front of the list.removeFromFront(), which removes the front value of the list.removeFromBack(), which removes the tail value of the list.Remains the same
public class LinkedList {
private Node head;
private Node tail;
public LinkedList() {
head = null;
tail = null;
}
public void insertAtBack(int num) {
if (head == null) {
head = new Node(num, null);
tail = head;
} else {
Node tempref = tail;
tail = new Node (num, null);
tempref.setNextReference(tail);
}
}
public void insertAtFront (int num) {
if (head == null) {
head = new Node(num, null);
tail = head;
} else {
Node tempref = new Node(num, head);
head = tempref;
}
}
public boolean isEmpty() {
return head == null;
}
public void removeFromFront() {
if (head == null) {
System.out.println ("List is Empty");
} else {
head = head.getNextReference();
}
}
public void removeFromBack() {
if (this.isEmpty()) {
System.out.println("The list is empty.");
} else if (head == tail) {
head = null;
tail = head;
} else {
Node prev = head;
Node curr = head;
while (curr != tail) {
prev = curr;
curr = curr.getNextReference();
}
prev.setNextReference(null);
tail = prev;
}
}
public void printList() {
if (head == null) {
System.out.println ("The List is Empty");
}
else {
Node tempref = head;
System.out.println("The values so far in the list : ");
while (tempref != null) {
System.out.print(tempref.getData());
tempref = tempref.getNextReference();
if (tempref != null) {
System.out.print (" --> ");
}
}
System.out.println("\n");
}
}
}import java.util.Scanner;
public class LinkedListTest {
public static void Menu() {
System.out.println("1 - Insert At Back ");
System.out.println("2 - Insert At Front");
System.out.println("3- Remove From Front");
System.out.println("4- Remove From Back");
System.out.println("5 - Quit");
}
public static void main (String[] args) {
System.out.println("Linked Lists");
Scanner scanner = new Scanner(System.in);
Scanner scanner1 = new Scanner(System.in);
int choice = 0, status = 0, entry = 0;
boolean flag = true;
LinkedList list = new LinkedList();
while (flag) {
Menu();
status = 0;
try {
choice = Integer.parseInt(scanner.nextLine());
} catch (Exception e) {
System.out.println("Integers Only - Enter Again");
status = 1;
}
if (choice == 1) {
System.out.println("Enter the value?");
entry = scanner1.nextInt();
list.insertAtBack(entry);
} else if (choice == 2) {
System.out.println("Enter the value?");
entry = scanner1.nextInt();
list.insertAtFront(entry);
} else if (choice == 3) {
list.removeFromFront();
} else if (choice == 4) {
list.removeFromBack();
} else if (choice == 5) {
flag = false;
System.out.println("End of Program");
} else if (status == 0) {
System.out.println("Invalid Entry - Choose From Menu");
}
list.printList();
}
}
}Linked Lists
1 - Insert At Back
2 - Insert At Front
3 - Remove From Front
4 - Remove From Back
5 - Quit
> 1
Enter the value?
> 34
The values so far in the list :
34
1 - Insert At Back
2 - Insert At Front
3 - Remove From Front
4 - Remove From Back
5 - Quit
> 2
Enter the value?
> 12
The values so far in the list :
12 --> 34
1 - Insert At Back
2 - Insert At Front
3 - Remove From Front
4 - Remove From Back
5 - Quit
> 2
Enter the value?
> 134
The values so far in the list :
134 --> 12 --> 34
1 - Insert At Back
2 - Insert At Front
3 - Remove From Front
4 - Remove From Back
5 - Quit
> 3
The values so far in the list :
12 --> 34
1 - Insert At Back
2 - Insert At Front
3 - Remove From Front
4 - Remove From Back
5 - Quit
> 4
The values so far in the list :
12
1 - Insert At Back
2 - Insert At Front
3 - Remove From Front
4 - Remove From Back
5 - Quit
> 3
The List is Empty
1 - Insert At Back
2 - Insert At Front
3 - Remove From Front
4 - Remove From Back
5 - Quit
> 5
End of Program
The List is EmptyAdd an additional choice in the Menu for Problem #1 which does the following:
Remains the same
public class LinkedList {
// The previous linked list code stays the same
public int getMaxValue() {
Node tempRef = head;
int max = Integer.MIN_VALUE;
while (tempRef != null) {
int value = tempRef.getData();
if (value > max) {
max = value;
}
tempRef = tempRef.getNextReference();
}
return max;
}
public Node getMaxReference() {
Node tempRef = head;
int max = this.getMaxValue();
if (this.isEmpty()) {
return null;
}
while (tempRef.getData() != max) {
tempRef = tempRef.getNextReference();
}
return tempRef;
}
// inserts the maximum value to the end of the list
public void maxToBack() {
if (head != null) {
int max = getMaxValue();
Node maxad = getMaxReference(max);
if (head != tail) {
if (head == maxad) {
removeFromFront();
insertAtBack(max);
} else if (tail != maxad) {
Node curr = head;
Node prev = head;
while (curr != maxad) {
prev = curr;
curr = curr.getNextReference();
}
prev.setNextReference(curr.getNextReference());
insertAtBack(max);
}
}
}
}
}Add the new choices as demonstrated in Problem 2.
Linked Lists
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 1
Enter the value?
> 45
The values so far in the list :
45
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 5
The values so far in the list :
45
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 2
Enter the value?
> 908
The values so far in the list :
908 --> 45
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 5
The values so far in the list :
45 --> 908
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 1
Enter the value?
> 1900
The values so far in the list :
45 --> 908 --> 1900
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 5
The values so far in the list :
45 --> 1900 --> 908
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 1
Enter the value?
> 999
The values so far in the list :
45 --> 1900 --> 908 --> 999
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 5
The values so far in the list :
45 --> 1900 --> 908 --> 999
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 2
Enter the value?
9999
The values so far in the list :
9999 --> 45 --> 1900 --> 908 --> 999
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 5
The values so far in the list :
45 --> 1900 --> 908 --> 999 --> 9999
1 - Insert At Back
2 - Insert At Front
3- Remove From Front
4- Remove From Back
5 - Max to Back
6 - Quit
> 6
End of Program
The values so far in the list :
45 --> 1900 --> 908 --> 999 --> 9999