Write a testing class that is similar to linkedListApplication class defined in p2-1 to test program p2-2 DoubleLinkedList. Make sure that you understand each operation in the program.

Use p2-1 linkedListClass as a reference, add the following operations in the class LinkedList;

Find the average data values of the linked list.

Find the item with largest key, and then delete the node.

Test ALL operations in the Main method. (Also display the average of the data values of the linked list, the largest key, the linked list before and after deleting the node with the largest key;

Modify p2-1 SingleLinedList programs so that it handles employee objects. Make your program menu-driven.

import java.util.Scanner;

public class employee

{

public int id;

public String name;

public double salary;

public void Input()

{

System.out.println("Enter name: ");

name = new Scanner(System.in).nextLine();

System.out.println("Enter ID: ");

id = Integer.parseInt(new Scanner(System.in).nextLine());

System.out.println("Enter Salary: ");

salary = Double.parseDouble(new Scanner(System.in).nextLine());

}

public void Output()

{

System.out.printf("Name: %1$s, ID: %2$s, Grade: %3$s ", name, id, salary);

}

public String toString()

{

return String.format("[Name: {0}, ID: {1}, Grade: {2}]", name, id, salary);

}

}

Program P2-1:

package p6_linkedList;

import java.util.*;

public class LinkedList

{

public Node header;

public LinkedList()

{

header = null;

}

public final Node Search(int key)

{

Node current = header;

while (current != null && current.item != key)

{

current = current.link;

}

return current;

}

public final void Append(int newItem)

{

Node newNode = new Node(newItem);

newNode.link = header;

header = newNode;

}

public final Node Remove()

{

Node x = header;

if (header != null)

{

header = header.link;

}

return x;

}

public final Node searchPrevious(int key)

{

if (header == null)

{

return header;

}

else

{

Node current = header;

while (!(current.link == null) && (current.link.item != key))

{

current = current.link;

}

return current;

}

}

public final void Insert(int newItem, int preKey)

{

Node current;

Node newNode = new Node(newItem);

current = Search(preKey);

if (current == null)

{

System.out.println("there is no such preKey!");

}

else

{

newNode.link = current.link;

current.link = newNode;

}

}

public final void Delete(int key)

{

if (header == null) // The list is empty!

{

System.out.println("The list is empty!");

}

else

{

if (header.item == key) // The only node in the list is to be deleted.

{

header = header.link;

}

else // The list has more than one node.

{

Node p = searchPrevious(key);

if (p.link == null)

{

System.out.println("There is no such item!");

}

else

{

p.link = p.link.link;

}

}

}

}

public final void ShowLinkedList()

{

if (header == null)

System.out.println("The list is empty!");

else

{

Node current = header;

System.out.printf("%1$s->", current.item);

while (!(current.link == null))

{

current = current.link;

System.out.printf("%1$s->", current.item);

}

System.out.printf("null");

System.out.println();

}

}

public final void PrintList()

{

if (header == null)

{

System.out.println("The list is empty!");

}

else

{

Node current = header;

System.out.println(current.item);

while (!(current.link == null))

{

current = current.link;

System.out.println(current.item);

}

}

}

}

Program P 2-2:

package p7_doubleLinkedList;

import java.util.*;

public class DoubleLinkedList

{

public Node header;

public Node tail;

public DoubleLinkedList()

{

header = null;

tail = null;

}

public void AppendToHead(int newItem)

{

Node newNode = new Node(newItem);

if (header == null)

{

header = newNode;

tail = newNode;

}

else

{

newNode.Flink = header;

header.Blink = newNode;

header = newNode;

}

}

public Node RemoveFromHead()

{

Node x = header;

if (header != null)

{

if (header == tail)

{

header = null;

tail = null;

}

else

{

header = header.Flink;

header.Blink = null;

}

}

else

{

System.out.println("the double linked list is empty");

}

return x;

}

public void AppendToTail(int newItem)

{

Node newNode = new Node(newItem);

if (tail == null)

{

tail = newNode;

header = newNode;

}

else

{

newNode.Blink = tail;

tail.Flink = newNode;

tail = newNode;

}

}

public Node RemoveFromTail()

{

Node x = tail;

if (tail != null)

{

if (header == tail)

{

header = null;

tail = null;

}

else

{

tail.Blink.Flink = null;

tail = tail.Blink;

}

}

else

{

System.out.println("the double lined list is empty");

}

return x;

}

public Node Search(int key)

{

Node current;

current = header;

while (current != null && current.item != key)

{

current = current.Flink;

}

return current;

}

public void Insert(int newItem, int preKey)

{

Node newNode = new Node(newItem);

Node current = Search(preKey);

if (current == null)

{

System.out.println("there is no such preKey!");

}

if (current != null)

{

if (current == tail)

{

newNode.Blink = current;

current.Flink = newNode;

}

else

{

newNode.Flink = current.Flink;

newNode.Blink = current;

current.Flink.Blink = newNode;

current.Flink = newNode;

if (newNode.Flink == null)

{

tail = newNode;

}

}

}

}

public void Delete(int key)

{

Node p = Search(key);

if (p == null)

{

System.out.println("there is no such a key.");

}

if (p != null)

{

if (p != header && p != tail)

{

p.Blink.Flink = p.Flink;

p.Flink.Blink = p.Blink;

};

if (p == header && p == tail)

{

header = null;

tail = null;

};

if (p == header && p != tail)

{

header = header.Flink;

header.Blink = null;

};

if (p != header && p == tail)

{

p.Blink.Flink = null;

tail = p.Blink;

}

}

}

public void PrintList()

{

Node current = header;

if (current == null)

{

System.out.println("The list is empty!");

return;

}

System.out.printf("(header)%1$s <==> ", current.item);

while (!(current.Flink == null))

{

current = current.Flink;

if (current.Flink == null)

System.out.printf("%1$s(tail)", current.item);

else

System.out.printf("%1$s <==> ", current.item);

}

System.out.println(" ");

}

}