Solved

help ! HOW TO WRITE A TWO DIMENSIONAL LINKED LIST

Posted on 2003-11-05
18
682 Views
Last Modified: 2010-03-31
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
0
Comment
Question by:mkahugu
  • 8
  • 7
  • 2
  • +1
18 Comments
 
LVL 15

Expert Comment

by:JakobA
ID: 9689850
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
 
LVL 15

Expert Comment

by:jimmack
ID: 9689878
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
 
LVL 2

Expert Comment

by:smitty22
ID: 9689932
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
 
LVL 15

Expert Comment

by:JakobA
ID: 9689953
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
 

Author Comment

by:mkahugu
ID: 9690024
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
 
LVL 2

Expert Comment

by:smitty22
ID: 9690060
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
 

Author Comment

by:mkahugu
ID: 9690070
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
 
LVL 15

Expert Comment

by:JakobA
ID: 9690116
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
 

Author Comment

by:mkahugu
ID: 9690164
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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 15

Expert Comment

by:JakobA
ID: 9690246
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
 

Author Comment

by:mkahugu
ID: 9690274
am getting it done right know....,
thanks, be back is a sec...!
0
 

Author Comment

by:mkahugu
ID: 9690586
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
 

Author Comment

by:mkahugu
ID: 9690813
Anyone?
0
 
LVL 15

Expert Comment

by:JakobA
ID: 9690830
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
 

Author Comment

by:mkahugu
ID: 9690888
ok, i will work on that
0
 
LVL 15

Accepted Solution

by:
JakobA earned 500 total points
ID: 9690946
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
 

Author Comment

by:mkahugu
ID: 9690996
thanks
0
 
LVL 15

Expert Comment

by:JakobA
ID: 9704933
So how is it going ?
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

706 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now