help ! HOW TO WRITE A TWO DIMENSIONAL LINKED LIST

I need help with some homework as to how you write  a two dimensional linked list, the top level list contains terms that i course can be offered and then it is linked to a list that contains a list of courses offered that term, I have read up and am ok on the implementation of a single linked list but to link it to another list i haven't grasped that yet, so pleas help am doing it in java
mkahuguAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

JakobACommented:
So you have a linked list of objects of some class. to attacht a secondary linked list to each link in that list all you need is a reference.  You can add that by extending your normal linked-list class

public class LinkedList2D extends LinkedList {
      public LinkedList secondDim = null;       // here you attach the secondary linkedlist

      // You may want to insert constructor and access methods for the secondary list here

} //endclass LinkedList2D.

regards JakobA
0
jimmackCommented:
If you mean a bi-directional linked list (where you can move forwards and backwards through it), then you need to modify your Node class to include a "previous" reference in addition to the "next" reference.
0
smitty22Commented:
I think you can just use your original LinkedList.

Assuming that your LinkedList class just holds Objects in its data field (see example), then you could just store the child LinkedList in the data field.  You know that the "Object" in the main linkedlist actually contains a LinkedList so you can cast accordingly to get the child linkedlist.

public class LinkedList {
  private Object data;
  private LinkedList next;
}

Example (copy this into notepad or other monospaced editor):
++++++++++++++++++++++++++++++++++++++
--> |Data-Next| --> |Data-Next| --> |Data-Next| --> NULL
       |               |               |
       v               v               v
    |Data-Next|     |Data-Next|      NULL
            |               |
            v               v
         |Data-Next|      NULL
                 |
                 v
               NULL
++++++++++++++++++++++++++++++++++++++

0
Cloud Class® Course: Microsoft Office 2010

This course will introduce you to the interfaces and features of Microsoft Office 2010 Word, Excel, PowerPoint, Outlook, and Access. You will learn about the features that are shared between all products in the Office suite, as well as the new features that are product specific.

JakobACommented:
As far as I can see you have no need for the sequence information you get vit a linked list where one link is 'first', another is 'second', etc.

So have you considered replacing the second dimension (list of courses that term) with a bitset after giving each possible course a number corresponding to at bit in that bitmap. after that you sust clear and set bits to show which courses are in each term. ( java.util.BitSet )
0
mkahuguAuthor Commented:
JakobA,
I think you are on the right track, please guide me on the following requirements, the program is due in 6hrs so i really appreciate your help, example code will really help, like the one you had before.

For this assignment, you should replace your Database class with another implementation
which uses a sorted two-level linked lists to store the information internally.
The nodes in the upper-level linked list will represent academic terms, with one node per
academic term. Each term node will contain a reference to a linked list of courses for that
term.
You should maintain the items in each linked list in sorted order, sorting the upper list
by term (in numerical order) and the lower list by course number (in standard dictionary
order).
You may use any variation on linked lists which you desire; doubly-linked, dummy head
nodes, head/end pointers, etc.. You may implement additional classes as desired in order
to manage the list, except as noted above. In particular, consider implementing “ListNode”
classes which contain links to other objects such as Courses.
0
smitty22Commented:
We can't do your HW for you.  JakobA's is probably a good solution, but be aware that it is outside the constraints of your assignment -- which is to implement 2D linked list.  I would check with your instructor before attempting such a solution.
0
mkahuguAuthor Commented:
This is the code i have written so for for my top level linked list



public class  CourseNode
 {
   private CourseNode head, current;
   public  Course course;
   public  CourseNode next;
   public  CourseNode prev;
   public CourseNode (Course lesson)
         {
            this (lesson,null,null);
        }
   public  CourseNode (Course lesson, CourseNode n,CourseNode p)
   {
       course = lesson;
       next = n;
       prev = p;
   }
 
  public String toString()
 {
 String result="";

  CourseNode current =head;
    while  (current !=null )
  {
     result +=current.course + "\n";
   
     current=current.next;
   }
  return result;
 }
 }


This is what I have written for my Terms Node

public class  TermNode
 {
   public  CourseNode courseptr;//am trying to reference my CouseNode here am not sure    
if   its correct
   public  TermNode next;
   public  TermNode prev;
   public TermNode (CourseNode semester)
         {
            this (semester,null);
        }
   public  TermNode (CourseNode semester, TermNode n)
   {
       courseptr= semester;
       next = n;
   }
   
    public String toString()
 {
 String result="";
  TermNode current = head;
    while  (current !=null )
  {
     result +=current.courseptr + "\n";
   
     current = current.next;
   }
  return result;
 }
   
   
  }
0
JakobACommented:
with the lists sorted you DO ned the sequence information, so it has to be lists.
Have you had priority lists yet? that is essentially what is wanted only in 2 dimensions.

For homework all we will give is general blather like this until you provide some code to 'build on' (else you would never learn anything).

I recommend you start with the sorted, linked list of courses.  later we can build on that to make the list of terms.

So how does you proposed linked list for courses look ?

regards JakobA
0
mkahuguAuthor Commented:
my proposed list of courses is as follows
public class  CourseNode
 {
   private CourseNode head, current;
   public  Course course;
   public  CourseNode next;
   public  CourseNode prev;
   public CourseNode (Course lesson)
         {
            this (lesson,null,null);
        }
   public  CourseNode (Course lesson, CourseNode n,CourseNode p)
   {
       course = lesson;
       next = n;
       prev = p;
   }

and my Course class is as follows

public class Course
{
 
protected int term; //variable represention term course was taken
protected String course_number;//variable for the course number
protected int course_credit;//variable for the course credit
protected String course_title;//variable for the course title
protected String grade;//variable for the course grade
   
public Course(int term, String course_number, int course_credit, String course_title, String grade)
      {
      
      this.term = term;
      this.course_number = course_number;
      this.course_credit = course_credit;
      this.course_title = course_title;
      this.grade = grade;
      
      }

       
public int getTerm()
      {
            return term;
      }      

public String getCourseNumber()
        {
                return course_number;
        }
     
public int getCourseCredit()
        {
                return course_credit;
        }


public String getCourseTitle()
        {
                return course_title;
        }

public String getGrade()
        {
              return grade;
        }
       
 public String toString()
        {
        String out;
        out = "Term; " + term + "\tCourseName; " + course_number + "\tCourseCredit: " + course_credit + "\tCourseTitle; " + course_title + "\tGrade:" + grade;
        return out;
        }
       
       
     
}      
            
      

      

0
JakobACommented:
Ahh, you have posted already. good. forget about the term nodes for now and concentrate on the course node class.

We will need 3 new methods

    public boolean insertCourse( Course course ) {
         // code to insert a node with this courser in its proper place in the list
         // What if that course is already in the list. are duplicated ok? should we ingnore or call it an error or what ?
        // return true on inserted OK, else false
   } //endmethod insertCourse

   public Course findCourse( CourseID courseId ) {
       // ...
       // return null if not found, the Course if found
   } //endmethod findCourse

    public boolean removeCourse( CourseID courseId ) {
         // ...
         // return truo on removed, false if not found
   } //endmethod removeCourseourse

try making these. they all start at the head and search down through the list until finding a 'greater' course or the end, then insert, find or remove before that.

regards JakobA
0
mkahuguAuthor Commented:
am getting it done right know....,
thanks, be back is a sec...!
0
mkahuguAuthor Commented:
This is what i have been able to achieve so far


public class  CourseNode
 {
   private CourseNode head, tail, current;
   public  Course course;
   public  CourseNode next;
   public  CourseNode prev;
   public CourseNode (Course lesson)
         {
            this (lesson,null,null);
        }
   public  CourseNode (Course lesson, CourseNode n,CourseNode p)
   {
       course = lesson;
       next = n;
       prev = p;
   }
 public boolean isEmpty()
 {
     return head == null;
 }
 
       
public boolean insertCourse(Course lesson)
    {
     // code to insert a node with this course in its proper place in the list
    if (!isEmpty())
    {
        tail = new CourseNode(lesson, null, tail);
        tail.prev.next = tail;
    }
    else
       head = tail = new CourseNode(lesson);  
         // What if that course is already in the list. are duplicated ok? should we ingnore or call it an error or what ?
    //if the course already exists i would like to call and error and ask the user to try again
        // return true on inserted OK, else false
     //am not sure of the return  
   } //endmethod insertCourse
public Course findCourse(Course lesson )
    {
        CourseNode tmp;     // A pointer for traversing the list.
        tmp = head;          //Start by looking at the head of the list.
      for (;tmp !=null && !lesson.equals(tmp.course); tmp = tmp.next);
        if (tmp == null)
               return null;
        else return tmp.course;
       
        // ...
       // return null if not found, the Course if found
    } //endmethod findCourse

public void removeCourse( Course lesson)             //find and remove course
    {                                                                  
        if (head !=null)                                //if non empty list
            if (lesson.equals(head.course))             //if head needs to be removed
                head = head.next;
            else
            {
             CourseNode pred = head, tmp = head.next;
             for (;tmp !=null && !(tmp.course.equals(lesson)); pred = pred.next,
                    tmp = tmp.next);
             
             if (tmp != null) //if found
                 pred.next = tmp.next;
            }
       
         // ...
         // return truoe on removed, false if not found
   } //endmethod removeCourseourse
}
0
mkahuguAuthor Commented:
Anyone?
0
JakobACommented:
Ok.
please take care with your indentation, I'm a stickler for that :-)

If head is null you make a tail (defined as a variable where?) but not a value for head so it is sure to be null the next time too.

if head is not null you overwrite the value it has with a reference to a brand new object. so we cannot possibly search the list head pointed to before to to find where in the list the new object should be inserted.

I do not think this will work.   Use local variables in the method, so you can be sure you do not destroy your information before you have used it

public boolean insertCourse(Course lesson)
    {
     // code to insert a node with this course in its proper place in the list
    if (!isEmpty())
    {
        tail = new CourseNode(lesson, null, tail);
        tail.prev.next = tail;
    }
    else
       head = tail = new CourseNode(lesson);  
         // What if that course is already in the list. are duplicated ok? should we ingnore or call it an error or what ?
    //if the course already exists i would like to call and error and ask the user to try again
        // return true on inserted OK, else false
     //am not sure of the return  
   } //endmethod insertCourse


0
mkahuguAuthor Commented:
ok, i will work on that
0
JakobACommented:
Actually we have a problem here the method  insertCourse  is not static so in order to call it we must already have an instance of the class  CourseNode.

So lets make a root node for the list. this node is always the head, and does not contain any coursedata. it is just an administrative aid so we can find the list (and know where it begins and ends)

    public static CourseNode rootNode() {
        CourseNode newOne = new CourseNode( null );
        newOne.head = newOne;
        newOne.prev = newOne;
        newOne.next = newOne;        
        return newOne;
    }

Later when we get to the tems each new termNode ovject will have to create its own root node for its courselist. for now we kust say that it HAS been creatied. and the  insertCourse  method we call are in that node (or in any other node in the list that node is the root for). the variable head in all the nodes in the list point to the root node.

now we can write the insert method:

        // code to insert a node with this course in its proper place in the list
        // return true on inserted OK, else false
    public boolean insertCourse( Course course ) {
        CourseNode prevOne = this.head;
        while (  prevOne.next.course != null       // stop at the root node  
              && prevOne.next.course.compareTo( course ) <= 0
              ) {
            prevOne = prevOne.next;    // move down the list to end or greater node
        }
        if (  prevOne.course != null
           && prevOne.course.compareTo( course ) <= 0
           ) {
            // that course is already in the list. so calling method can test and handle
            return false;
        } else  {
            // that course can be inserted
            CourseNode newOne = new CourseNode( course );
            newOne.head = this.head;            // all .head's point to the root
            newOne.prev = prevOne;             // setup linkage
            newOne.next = prevOne.next;
            newOne.next.prev = newOne;
            newOne.prev.next = newOne;
            return true;
        }
    } //endmethod insertCourse

by making the list as a circular list with the root as a 'marker' between the last and the first node in the list we awoid the need to take account of edge conditions. We do not need to test for or insert  a null value at the end of the list.

so now you do the others. thak care. the root node must NEVER be removed. (or found)

regasrds JakobA


 
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
mkahuguAuthor Commented:
thanks
0
JakobACommented:
So how is it going ?
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.