Create a generic doubly linked list class using an internal node class: LinkedLi
ID: 667550 • Letter: C
Question
Create a generic doubly linked list class using an internal node class:
LinkedListUM<T> and NodeUM<T> Include these Methods for LinkedListUM<T>:
- void insertHead (T)
- void insertTail (T)
- T removeElementAt (int)
- T removeTail ()
- T removeHead ()
- T peekElementAt (int)
- T peekHead ()
- T peekTail ()
- String toString ()
Test your program using your previous class.
In your documentation answer, at what point does your program performance begin to degrade?
StudentA.java
import java.util.Scanner;
import java.util.ArrayList;
class StudentA implements Comparable <StudentA> {
static java.util.Random rn = new java.util.Random (); static ArrayList <String> firstNames = new ArrayList <>(); static ArrayList <String> lastNames = new ArrayList <>(); static SORTBY sortBy = SORTBY.LAST;static int nextUID = 1;
String first, last;
double gpa = 0;
int credits = 0;
int uid = 0;
static {
try {java.util.Scanner scFirst = new java.util.Scanner (new
java.io.File("firstNames.txt"));java.util.Scanner scLast = new java.util.Scanner (new
java.io.File("lastNames.txt"));while (scFirst.hasNext()) firstNames.add (scFirst.next()); while ( scLast.hasNext()) lastNames.add ( scLast.next());
}catch (java.io.FileNotFoundException e) {
System.out.println (e);
} // end try catch
} // end static intializerenum SORTBY {LAST, FIRST, CREDITS, GPA}public StudentA (String st) {this (new Scanner (st)) }
public StudentA (Scanner sc) {
uid = nextUID++;
first = sc.next();
last = sc.next();
credits = sc.nextInt();
gpa = sc.nextDouble();
} // end Scanner constructor
public StudentA () {uid = nextUID++;} // no parameter constructor
public int compareTo (StudentA x) {
switch (sortBy) {case LAST : return last.compareTo (x.last);
case FIRST : return first.compareTo (x.first); case CREDITS: return credits - x.credits;case GPA : return (gpa > x.gpa)? 1 : -1;
} // end switch
return 0;
} // end compareTo for Comparable interface
public String toString () {
return String.format ("%5d %15s, %15s: %5d %10.2f", uid, last, first, credits, gpa);
} // end method toString
public static StudentA [] makeRandom (int m) {
StudentA [] sa = new StudentA [m];
for (int i = 0; i < sa.length; i++) {
sa[i]
sa[i].first
sa[i].last
sa[i].credits = rn.nextInt (120);
sa[i].gpa = rn.nextDouble () * 4.0;
= new StudentA ();= firstNames.get (rn.nextInt (firstNames.size())); = lastNames.get (rn.nextInt ( lastNames.size()));
} // end for each student to instantiate
return sa;
} // end method makeRanom
public static void main (String args []) {
System.out.println (new StudentA
StudentA [] x = makeRandom (10);
for (StudentA m: x)
("james robinson 35 3.98"));
Last -----");
First -----");
Credits -----");
System.out.println (m);
java.util.Arrays.sort (x);
System.out.println ("----
for (StudentA m: x)
System.out.println (m);
System.out.println ("----
StudentA.sortBy = SORTBY.FIRST;
java.util.Arrays.sort (x);
for (StudentA m: x)
System.out.println (m);
System.out.println ("---- SORTED
StudentA.sortBy = SORTBY.CREDITS;
java.util.Arrays.sort (x);
for (StudentA m: x)
SORTED
SORTED
System.out.println (m);System.out.println ("---- SORTED GPA -----"); StudentA.sortBy = SORTBY.GPA; java.util.Arrays.sort (x);for (StudentA m: x)
System.out.println (m);
} // end main
} // end class StudentA
Explanation / Answer
working java code:
public class NodeUM<T> {
private T data;
private NodeUM<T> next;
private NodeUM<T> prev;
NodeUM(){
next=null;
prev=null;
data=null;
}
NodeUM(T data) {
this(data, null, null);
}
NodeUM(T data, NodeUM<T> next, NodeUM<T> prev) {
this.data = data;
this.next = next;
this.prev = prev;
}
T getData() {
return data;
}
public void setNextNode(NodeUM<T> next) {
this.next = next;
}
public NodeUM<T> getPrevNode() {
return prev;
}
public void setPrevNode(NodeUM<T> prev) {
this.prev = prev;
}
public void setData(T data) {
this.data = data;
}
public NodeUM<T> getNextNode() {
return next;
}
}
public class LinkedListUM<T> {
private NodeUM<T> head;
private NodeUM<T> tail;
//Returns the no. of nodes in Doubly linked list
public int getSize(){
int count = 0;
if(head==null)
return count;
else{
NodeUM<T> temp=head;
do{
temp=temp.getNextNode();
count++;
}while(temp!=tail);
}
return count;
}
//Traverse from head
public void traverseF(){
NodeUM<T> temp=head;
while(temp!=null){
System.out.print(temp.getData()+" ");
temp=temp.getNextNode();
}
}
//Traverse from tail
public void traverseB(){
NodeUM<T> temp=tail;
while(temp!=null){
System.out.print(temp.getData()+" ");
temp=temp.getPrevNode();
}
}
/* methods related to insertion in doubly linked list starts.*/
public void insertAtBeg(T data){
NodeUM<T> newnode=new NodeUM<T>(data);
if(head==null){
head=newnode;
tail=newnode;
newnode.setNextNode(null);
newnode.setPrevNode(null);
}else{
newnode.setNextNode(head);
head.setPrevNode(newnode);
head=newnode;
}
}
public void insertAtEnd(T data){
NodeUM<T> newnode=new NodeUM<T>(data);
if(tail==null){
head=newnode;
tail=newnode;
newnode.setNextNode(null);
newnode.setPrevNode(null);
}else{
newnode.setPrevNode(tail);
tail.setNextNode(newnode);
tail=newnode;
}
}
public void insertAtPosition(T data,int position){
if(position<0||position==0){
insertAtBeg(data);
}
else if(position>getSize()||position==getSize()){
insertAtEnd(data);
}else{
NodeUM<T>temp=head;
NodeUM<T> newnode=new NodeUM<T>(data);
for(int i=0;i<position-1;i++){
temp=temp.getNextNode();
}
newnode.setNextNode(temp.getNextNode());
temp.getNextNode().setPrevNode(newnode);
temp.setNextNode(newnode);
newnode.setPrevNode(temp);
}
}
/* methods related to insertion in doubly linked list ends.*/
/* methods related to deletion in doubly linked list starts.*/
//Removal based on a given node for internal use only
@SuppressWarnings("unused")
private void remove(NodeUM<T> node){
if(node.getPrevNode()==null)
head=node.getNextNode();
else if(node.getNextNode()==null)
tail=node.getPrevNode();
else{
NodeUM<T> temp=node.getPrevNode();
temp.setNextNode(node.getNextNode());
node.getNextNode().setPrevNode(temp);
}
node=null
}
public T remove(int position){
T data=null;
if(position==1){
data=head.getData();
head=head.getNextNode();
}else if(position==getSize()){
data=tail.getData();
tail=tail.getPrevNode();
tail.setNextNode(null);
}else{
NodeUM<T> temp=head;
for(int i=0;i<position;i++){
temp=temp.getNextNode();
}
NodeUM<T> node=temp.getNextNode();
node.setPrevNode(temp.getPrevNode());
temp.getPrevNode().setNextNode(node);
temp=null;
}
return data;//Deleted node's data
}
}
public class MainClass {
public static void main(String args[]){
LinkedListUM< Integer> dll=new LinkedListUM<Integer>();
dll.insertAtBeg(32);
dll.insertAtBeg(35);
dll.insertAtBeg(45);
dll.insertAtEnd(12);
dll.traverseF();
System.out.println();
dll.traverseB();
System.out.println("Size is:"+dll.getSize());
dll.insertAtPosition(46,0);
System.out.println();
dll.traverseF();
System.out.println("Removed at pos 5:"+dll.remove(5));
System.out.println("Size is:"+dll.getSize());
dll.traverseF();
dll.remove(1);
System.out.println();
dll.traverseF();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.