List Type Data Structures Overview : You will be implementing my version of a li
ID: 3829937 • Letter: L
Question
List Type Data Structures
Overview :
You will be implementing my version of a linked list. This is a linked list which has possible sublists descending from each node. These sublists are used to group together all nodes which share a common category value. You will be designing custom nodes with three categories on which to group. By the end you will have a list which is similar to the one shown below.
NOTE: The number of nodes here is for demonstration only. Your list should be able to dynamically add new nodes either to the main list, or a specific sublist based on the criteria described in the rest of these directions.
Observe that the main list is doubly-linked, while the sub-lists are not.
The Node Class
The Node class represents one "Node" of your LinkedList. The Node class must be Generic with three different parameterized types. The Generic types could each be different, so you cannot use the same generic label for each type. An example of what I mean is demonstrated in the following Node instantiation:
Node<Integer, String, Double> myNode = new Node<Integer, String, Double>();
The following defines the requirements for the Node class. You are not allowed to change / add / omit anything in the requirements.
Member Variables
This class shall have one member variable called category1 which will store information related to the first grouping category. This data field shall be generic and shall have package-level access.
This class shall have one member variable called category2 which will store information related to the second grouping category. This data field shall be generic and shall have package-level access.
This class shall have one member variable called category3 which will store information related to the third grouping category. This data field shall be generic and shall have package-level access.
This class shall have one member variable called right which is a pointer to the next item in the main list. This data field shall have package-level access.
This class shall have one member variable called left which is a pointer to the previous item in the main list. This data field shall have package-level access.
This class shall have one member variable called down which is a pointer to the next item in the sub-list This data field shall have package-level access.
No other member variables are allowed.
Constructor
This class shall have one constructor which has parameters to initialize the three category data fields.
No other constructors are allowed.
Methods:
This class shall have getters for each of the three category variables.
Node<Integer, String, String> node = new Node<Integer, String, String>(27, "blue", "musician");
NOTE: That all Node instantiation and manipulation will be done within your LinkedList class. The types for the parameters will also come from the corresponding generic parameters in the LinkedList class. Nodes will NOT be instantiated in any classes OTHER than LinkedList.
The LinkedList Class
This will be the class which is responsible for all of the functionality of your LinkedList. This must be aGenericclass where the generic parameter types could each be different. An example of instantiating a LinkedList might be:
LinkedList<Integer, String, String> list = new LinkedList<Integer, String, String>();
NOTE: The parameterized types will be the same type and in the same order as the parameterized types for the Nodes for this list.
The key with properly designing this class is in how a new node is added to your list. All nodes will be grouped together based on one of the three categories from the Node class. At any given time, the user can choose how to group the nodes, and the initial grouping will always use the first category. Nodes which have the same value in the current grouping category. will be added to the same sub-list. Nodes which do not have the same value as any of the existing sub-lists will be added to the main list.
Example: Lets say I have five people P1, P2, P3, P4, and P5, and each person has the following values in their respective categories (age, eye color, profession):
P1: 25, blue, doctor
P2: 34, brown, pilot
P3: 25, brown, uber driver
P4: 25, green, doctor
P5: 34, green, uber driver
If I were to group my list based on the age category (category1), my list might look something like:
You should also be able to regroup your list based on the other two categories as well.
Member Variables:
This class shall have one member variable called head which will store a pointer to the first Node in the LinkedList.
This class shall have one member variable called size which will store the total number of elements in the list (this includes all nodes in the main list as well as the sub lists). This should be a read-only property which cannot be changed outside of the LinkedList class.
This class shall have one member variable called category1Label which will store the label for category1 from the Node class. This should be a read-only property which cannot be changed once the initial list has been created. In the above example, the label for category1 would be "Age".
This class shall have one member variable called category2Label which will store the label for category2 from the Node class. This should be a read-only property which cannot be changed once the initial list has been created. In the above example, the label for category1 would be "Eye Color".
This class shall have one member variable called category3Label which will store the label for category1 from the Node class. This should be a read-only property which cannot be changed once the initial list has been created. In the above example, the label for category1 would be "Profession".
This class shall have one member variable called groupingCategory which will store the current category number upon which the list should be grouped. The default grouping category is category1.
No other member variables are allowed.
Constructors:
This class shall have one no-arg constructor which creates an empty list.
This class shall have one constructor which takes an integer parameter, which is the number of the current category upon which you want your list to group. This constructor should also create an empty list.
This class shall have one constructor which takes a File object parameter and an integer parameter. This File is the input file from which a list can be generated and populated. The integer parameter is the current grouping property. See below for the required format of the input file. This constructor should take the File and create a list based on the values in the File.
Methods:
NOTE: These methods should be implemented with generics in mind. It will be your job to figure out how to do this.
add(value1, value2, value3):
This method shall have three parameters. These parameters are the values of the categories in a Node.
Use the parameters to create a new Node and add it to the list.
The Node must be added in such a way that it maintains the current grouping category of the list.
clear():
This method shall clear the list.
deleteFirst():
This method shall delete the first Node in the main list.
This method shall NOT delete any nodes in the first Node's sublist. The remaining Nodes in the sublist should be "reattached" to the beginning of the main list.
deleteLast():
This method shall delete the last Node in the main list.
This method shall NOT delete any nodes in the last Node's sublist. The remaining Nodes in the sublist should be "reattached" to the end of the main list.
delete(mainIndex, subIndex):
This method shall delete a specific node from anywhere in the list, given the mainIndex and subIndex.
This method should ONLY delete the requested Node and should "reconnect" any Nodes that may be attached to the deleted Node.
get(mainIndex, category):
This method shall have an integer parameter, mainIndex, which is an index (starting from 0) which indicates the Node from the main branch you want to retrieve.
This method shall have another integer parameter, category, which is a category number (1 - 3) that will indicate which category's value you want to retrieve.
This method shall return the chosen category value, from the chosen Node in the main list. The category value should be returned as a String.
If the index is out of bounds, this method should throw an IndexOutOfBoundsException with an appropriate error message indicating whether it was the main index or category value that was out of bounds.
get(mainIndex, subIndex, category):
This method shall have an integer parameter, mainIndex, which is an index (starting from 0) which indicates the Node from the main branch you want to retrieve.
This method shall have an integer parameter, subIndex, which is an index (starting from 0) which indicates the Node from the sub-list of the chosen main branch Node.
This method shall have another integer parameter, category, which is a category number (1 - 3) that will indicate which category's value you want to retrieve.
This method shall return the value from the chosen category, in the indicated sub-list. The category value should be returned as a String.
If any of the parameters are out of bounds, this method should throw an IndexOutOfBoundsException with an appropriate error message indicating whether it was the main index, sub index or category value that was out of bounds.
regroup(groupingCategoryNumber):
This method shall be responsible for regrouping your LinkedList based on the given regrouping category number.
Example: I could take the above list from the diagram, which was initially grouped based on the Age category (category 1), and I could regroup the list based on the Profession category (category 3).
If the groupingCategoryNumber is out of bounds, display an IndexOutOfBoundsException with an appropriate error message.
size():
This method shall return the size of the main list.
The size is the number of nodes in the main list.
size(index):
This method shall return the size of the sub-list at the given index.
If the given index is out of bounds, this method should throw an IndexOutOfBoundsException with an appropriate error message.
No other methods are allowed, except you may add a toString() method for testing purposes only.
Input File Format
The input file shall be in the following format:
The first three lines of the file will be the labels of each category
The next line is a blank line
The values for each category are comma separated, with one node's values per line.
example:
The GUI
Design a GUI which will display a graphical representation of your list. It should show the main list and any sub-lists in a diagram similar to what is pictured above.
The "nodes" should also display the values of the three categories stored in a node.
You must also provide a way for the user to manipulate the list using any of the previously designed methods.
Sub List(s) Main ListExplanation / Answer
Hello this is lengthy exercise. Please post the GUI as a separate question along with this code. Completed the code for the list functionality. Check the main function on using the code. comments inline. Please delete display fuction. its for testing purpose. Please rate the answer if it helped. Thanks.
LinkedList.java
-----------
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class LinkedList<T1, T2, T3> {
protected Node<T1, T2, T3> head; //the head of the linked list
protected int size; //the total number of elements in the main and sublists inclusive
protected String category1Label,category2Label,category3Label; //labels for the 3 categories
protected int groupingCategory; //the category number on which the list is grouped. default is 1.
//default constructor
public LinkedList()
{
groupingCategory=1; //set the default grouping category
}
//Constructor specifying the grouping category
public LinkedList(int category)
{
groupingCategory=category;
}
public LinkedList(File infile,int category) throws FileNotFoundException
{
groupingCategory=category;
//read the file
//TODO: reading a file and instantiate generic node objects
}
protected void add(T1 value1,T2 value2,T3 value3)
{
Node<T1,T2,T3> node=new Node<T1,T2,T3>(value1,value2,value3);
//System.out.println(node);
if(head==null) //list is empty
head=node;
else
{
Node<T1,T2,T3> p=head; //start from beginning of list
boolean inserted=false;
while(!inserted)
{
//if grouping is by category 1 and both node's category1 values matches or
//if grouping is by category 2 and both node's category2 values match or
//if grouping is by category 3 and both node's category3 values match
if(
(groupingCategory==1 && p.getCategory1().equals(node.getCategory1())) ||
(groupingCategory==2 && p.getCategory2().equals(node.getCategory2())) ||
(groupingCategory==3 && p.getCategory3().equals(node.getCategory3())))
//found the correct sublist
{
//go down the sublist to end and add
while(p.down!=null) //stop at the last node of sublist
{
p=p.down;
}
p.down=node;
inserted=true;
}
else
{
if(p.right!=null) //move to next item in mainlist
p=p.right;
else //reached the end of main list
{
p.right=node; //link the last nodes left to new node
node.left=p; //link the new nodes right to last node in mainlist
inserted=true;
}
}
}
}
size++;
}
/**
* Clears the list by setting head to null and sets the size to 0
*/
protected void clear()
{
head=null; //all nodes will go out of scope. garbage collector will collect
size=0;
}
/**
* Delete first node in the mainlist. Reattach the sublist
*/
protected void deleteFirst()
{
delete(0,0);//delete node with mainindex=0 and subindex=0
}
/**
* Delete last node in the mainlist. Reattach the sublist
*/
protected void deleteLast()
{
int mainIndex=0;
Node<T1, T2, T3> p=head;
//get the last index in main list
while(p.right!=null)
{
p=p.right;
mainIndex++;
}
//reuse the function to delete a node given mainindex and subindex
delete(mainIndex,0);
}
protected void delete(int mainIndex,int subIndex)
{
if(mainIndex<0 || head==null)
throw new IndexOutOfBoundsException("Main Index out of bound : "+mainIndex);
if(subIndex<0 || head==null)
throw new IndexOutOfBoundsException("Sub Index out of bound : "+subIndex);
int mi=0; //mainindex
int si=0; //subindex
Node<T1,T2,T3> p=head,prev=null;
while(mi<mainIndex && p.right!=null) //move to right in the main list till we reach the specified mainindex node
{
p=p.right;
mi++;
}
if(mi!=mainIndex) //we could not move so many locations in main list
throw new IndexOutOfBoundsException("Main Index out of bound : "+mainIndex);
while(si<subIndex && p.down!=null) //move to down in the sub list till we reach the specified subindex node
{
prev=p;
p=p.down;
si++;
}
if(si!=subIndex) //we could not move so many locations in sub list
throw new IndexOutOfBoundsException("Sub Index out of bound : "+subIndex);
Node<T1,T2,T3> newnode=p.down,left=p.left,right=p.right;
if(subIndex>0) //not the 1st node in sublist
{
prev.down=newnode; //simply link the previous top node to the next bottom node ignoring the current node
}
else // its the first node in the sublist
{
if(left==null) //there is no left node and its 1st in sublist, so its the head node
{
head=newnode; //update head
}
else
left.right=newnode;
// set up all links from leftside and rightside of mainlist to this newnode from sublist moving up
if(newnode!=null)
{
newnode.left=left;
newnode.right=right;
}
if(right!=null)
right.left=newnode;
}
size--;
}
protected String get(int mainIndex,int category)
{
return get(mainIndex,0,category);
}
protected String get(int mainIndex,int subIndex,int category)
{
if(mainIndex<0 || head==null)
throw new IndexOutOfBoundsException("Index out of bound : "+mainIndex);
if(subIndex<0 || head==null )
throw new IndexOutOfBoundsException("Sub Index out of bound : "+subIndex);
int mi=0; //mainindex
int si=0; //subindex
Node<T1,T2,T3> p=head;
while(mi<mainIndex && p.right!=null) //move to right in the main list till we reach the specified mainindex node
{
p=p.right;
mi++;
}
if(mi!=mainIndex) //we could not move so many locations in main list
throw new IndexOutOfBoundsException("Main Index out of bound : "+mainIndex);
while(si<subIndex && p.down!=null) //move to down in the sub list till we reach the specified subindex node
{
p=p.down;
si++;
}
if(si!=subIndex) //we could not move so many locations in sub list
throw new IndexOutOfBoundsException("Sub Index out of bound : "+subIndex);
if(groupingCategory==1)
return p.getCategory1().toString();
else if(groupingCategory==2)
return p.getCategory2().toString();
else if(groupingCategory==3)
return p.getCategory3().toString();
else
throw new IndexOutOfBoundsException("Category number out of bounds: "+category);
}
protected void regroup(int groupingCategoryNumber)
{
if(groupingCategoryNumber>3 || groupingCategoryNumber<0)
throw new IndexOutOfBoundsException("Grouping category nubmer out of bound : "+groupingCategoryNumber);
if(head==null)
return;
Node<T1, T2, T3> newhead=null,mainnode,subnode,p,right,down;
boolean inserted=false;
groupingCategory=groupingCategoryNumber; //set the new grouping category
for(mainnode=head;mainnode!=null;mainnode=right) //for each node in mainlist
{
right=mainnode.right;
for(subnode=mainnode;subnode!=null;subnode=down) //for each node in sublist
{
down=subnode.down;
subnode.left=subnode.right=subnode.down=null; //clear old values
if(newhead==null)
{
newhead=subnode;
continue;
}
else
{
p=newhead;
inserted=false;
}
while(!inserted)
{
//if grouping is by category 1 and both node's category1 values matches or
//if grouping is by category 2 and both node's category2 values match or
//if grouping is by category 3 and both node's category3 values match
if(
(groupingCategory==1 && p.getCategory1().equals(subnode.getCategory1())) ||
(groupingCategory==2 && p.getCategory2().equals(subnode.getCategory2())) ||
(groupingCategory==3 && p.getCategory3().equals(subnode.getCategory3())))
//found the correct sublist
{
//go down the sublist to end and add
while(p.down!=null) //stop at the last node of sublist
{
p=p.down;
}
p.down=subnode;
inserted=true;
}
else
{
if(p.right!=null) //move to next item in mainlist
p=p.right;
else //reached the end of main list
{
p.right=subnode; //link the last nodes right to new node
subnode.left=p; //link the new nodes right to last node in mainlist
inserted=true;
}
}
}
}
}
}
protected int size()
{
return size;
}
protected int size(int index)
{
if(index<0 || head==null)
throw new IndexOutOfBoundsException("Index out of bound : "+index);
int mi=0,count=0;
Node<T1,T2,T3> p=head;
while(mi<index && p.right!=null) //move to left in the main list till we reach the specified mainindex node
{
p=p.right;
mi++;
}
if(mi!=index) //we could not move so many locations in main list
throw new IndexOutOfBoundsException(" Index out of bound : "+index);
while(p!=null) //move down in the sub list end of sublist
{
count++;
p=p.down;
}
return count;
}
/************** JUST FOR TESTING PURPOSE , REMOVE THIS FUNCTION WHEN SUBMITTING CODE *******************/
void display()
{
Node<T1, T2, T3> p,q;
for(p=head;p!=null;p=p.right)
{ System.out.println("sublist: ");
for(q=p;q!=null;q=q.down)
System.out.println(q.toString());
}
System.out.println("--------------------------");
}
/******************************************************************************************************/
public static void main(String a[])
{
File file=new File("c:\test\list.dat");
Scanner scanner;
LinkedList<Integer, String, String > list=new LinkedList<Integer,String,String>(); //create a empty list
try {
scanner = new Scanner(file); //read a file and fill in details
//get the category labels
list.category1Label=scanner.nextLine();
list.category2Label=scanner.nextLine();
list.category3Label=scanner.nextLine();
//read the blank line
scanner.nextLine();
Scanner linescanner;
//read the data lines
while(scanner.hasNext())
{
linescanner=new Scanner(scanner.nextLine());
linescanner.useDelimiter(","); //separate tokens using , delimiter
list.add(new Integer(linescanner.nextInt()), linescanner.next(), linescanner.next());
linescanner.close();
}
scanner.close();
list.regroup(3);
list.display();
list.delete(1,1);
list.display();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
---------------
Node.java
------------
package dd;
//A Generic node class with 3 generic parameters
public class Node<T1, T2, T3> {
//membes with package level access
T1 category1;
T2 category2;
T3 category3;
Node<T1,T2,T3> left,right,down;
/**
* Constructor to initialize the category member variables by using the arguments
* @param t1 value for category1
* @param t2 value for category2
* @param t3 value for category3
*/
public Node(T1 t1,T2 t2,T3 t3)
{
category1=t1;
category2=t2;
category3=t3;
}
public T1 getCategory1() {
return category1;
}
public void setCategory1(T1 category1) {
this.category1 = category1;
}
public T2 getCategory2() {
return category2;
}
public void setCategory2(T2 category2) {
this.category2 = category2;
}
public T3 getCategory3() {
return category3;
}
public void setCategory3(T3 category3) {
this.category3 = category3;
}
//for testing
public String toString()
{
return "["+category1+","+category2+","+category3+"]";
}
}
-------------sample output with the data given in question----------------
sublist:
[25, blue, doctor]
[25, green, doctor]
sublist:
[25, brown, uber driver]
[34, green, uber driver]
sublist:
[34, brown, pilot]
--------------------------
sublist:
[25, blue, doctor]
[25, green, doctor]
sublist:
[25, brown, uber driver]
sublist:
[34, brown, pilot]
--------------------------
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.