Results 1 to 15 of 15
  1. #1
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Question Trouble Developing Singly Linked Circular List

    Hello,

    I am attempting to create a singly linked circular list with the following methods

    Note: I have posted this on sun forums as well, looking for multiple input, please check the forum before posting so that you don't spend time answering my question and its already answered. under "New to Java"

    Now... I would like the only access to the list as a single reference "current" which can point to any link on the list and move around as needed. Please help me as I am confused as to how this all comes together.

    1. I should create two data types, "current" and "next" of type int say, is this correct?
    2. I can then create a constructor to initialize current, setting it to null, since there are no items in the circular linked list yet, correct?

    Insert() //Insert a new node into the circularly linked list

    If everything in my circularly linked list is named "current"...I don't understand where the node would be inserted into the list.

    Would below be acceptable? I just don't understand where this new node would be inserted?
    Java Code:
    Link newLink = new Link(int cd);
    newLink.next = current;
    current = newLink;

    Search()//Search for a node in the circularly linked list

    To do such a search I would obviously have to have a searchkey correct? But where would the search even begin?
    Something such as below only works when you have a "first" to start from, where would I be starting from here?

    Java Code:
    public Link find(int key)      // find link with given key
          {                           // (assumes non-empty list)
          Link current = first;              // start at 'first'
          while(current.iData != key)        // while no match,
             {
             if(current.next == null)        // if end of list,
                return null;                 // didn't find it
             else                            // not end of list,
                current = current.next;      // go to next link
             }
          return current;                    // found it
          }

    Delete()//Delete the next node after current in the circularly linked list

    Once more, would this require a utilizing a key? How would I arbitrarily delete the current.next for example?

    Display()//Display a node in the singly linked circular list
    I am assuming here I am to display an arbitrary node contained in the list since you may access the list at any spot, what's the logic behind this? Nodes don't have indexes unless iterators are attached, I am assumming it would probably be easiest to display say the first node or the last node? Yet how do you differentiate or reach these values if everything is "current"


    Step()//simply steps to the next node in the circularly linked list

    Would this only require such a statement such as current.next? How would this be utilized in my other methods?


    Any insight you could provide would be great, because I am having trouble understanding how to formulate such methods entirely.

  2. #2
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    7

    Default

    please post a link to the post at the sun forums. not all of us visit both.

    anyways, you seem to be a tad misunderstood of linked lists in general. once you understand how to conceptually play with a linked list (and circular linked list), the methods shouldn't be a problem once you get the hang of it.

  3. #3
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Default

    New To Java - Trouble Developing Singly Linked Circular List

    What am I misunderstanding about linked lists? I have a great understanding of how a general linked list works. Utilizing a "First" and "Next"

    However when it comes to starting with "Current" and moving to "Current.next" I get a little lost, specially when it has to be circular. Normally to make it circular I would have a first and last. And have last point to first. But I only have current....
    Last edited by VinceGuad; 02-25-2009 at 04:40 AM.

  4. #4
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    7

    Default

    just a little more:

    a barebones linked list is just a collection of nodes, where you can throw in a wrapper and add in classes as well. anyways, the node looks like this:

    Java Code:
    Node {
       Object value;
       Node next;
    }
    there is no "current" concept within the linked list. it is whatever uses the linked list that knows what is the "current" node.

    edit: btw, i'm just assuming you're confused about something (mostly about "current", though it's hard to understand really) because it didn't make much sense when you said this:
    1. I should create two data types, "current" and "next" of type int say, is this correct?
    2. I can then create a constructor to initialize current, setting it to null, since there are no items in the circular linked list yet, correct?

    Insert() //Insert a new node into the circularly linked list

    If everything in my circularly linked list is named "current"...I don't understand where the node would be inserted into the list.
    Last edited by emceenugget; 02-25-2009 at 03:48 AM. Reason: a little more...

  5. #5
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Question

    Would I maybe have

    First
    Last
    Current
    Next

    And do something like

    last.current points to first.current? to make it circular

    and to traverse through using current.next?



    Perhaps it was poor wording on my part, I understand how current works. Say I have a circle of nodes. Starting from the top node say this is current. Once I initiate current.next the nod to the right in the circle is now known as "current" ...
    Last edited by VinceGuad; 02-25-2009 at 03:53 AM.

  6. #6
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    7

    Default

    well in your terms, last.next would point to first.current

    but this is a circular linked list, and a circle has no edges, so there's really no concept of first or last unless you need them for some other reason.

    also, i still don't understand why you won't be able to tell where to insert a new node. you basically iterate through the list until you're where you want to be and then insert.

  7. #7
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Question

    So say I have a circular list of integers

    10, 14, 15, 124, 25, 12, 56, 41

    How would I say traverse to 124 which is known as "current" and insert an item after it? Or would I not look at the integer itself but its placement in the circular list.

    I guess I dont get how you would traverse to a specific object then insert after it...

    Unless.... maybe I utilized the "search" method in the insert method. Where I would search for a specific value then insert after that value. That sounds plasuable no?

    I would then do the same in the delete method. Call the search method and delete the node after the specified searchkey...

    Yes...No?

  8. #8
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    7

    Default

    yes, you would need to search then insert. in any data structure, you'll have to do some kind of search if you want to insert based on data held.

    however, when you make your search, remember that it's a circular list and will keep going if you don't tell it to stop.

  9. #9
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Default

    Java Code:
       public Link search(int key)      // find link with given key
          {                           // (assumes non-empty list)
          Link current = first;              // start at 'first'
          while(current.iData != key)        // while no match,
             {
             if(current.next == null)        // if end of list,
                return null;                 // didn't find it
             else                            // not end of list,
                current = current.next;      // go to next link
             }
          return current;                    // found it
          }
    // -------------------------------------------------------------
       public Link delete(int key)    // delete link with given key
          {                           // (assumes non-empty list)
          Link current = first;              // search for link
          Link previous = first;
          while(current.iData != key)
             {
             if(current.next == null)
                return null;                 // didn't find it
             else
                {
                previous = current;          // go to next link
                current = current.next;
                }
             }                               // found it
          if(current == first)               // if first link,
             first = first.next;             //    change first
          else                               // otherwise,
             previous.next = current.next;   //    bypass it
          return current;
          }
    Something of this sort? Now again...this uses first...how would I modify so it only has "current"

  10. #10
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    7

    Default

    instead of using the first node for anything, just use the current node as a starting point.

  11. #11
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Question

    Java Code:
       
    
    public Link search(int key)      // find link with given key
          {                           
          while(current.iData != key)        // while no match,
             {
             if(current.next == null)        // if end of list,
                return null;                 // didn't find it
             else                            // not end of list,
                current = current.next;      // go to next link
             }
          return current;                    // found it
          }
    
    
    // -------------------------------------------------------------
       public Link delete(int key)    // delete link with given key
          {                           // (assumes non-empty list)
          while(current.iData != key)
             {
             if(current.next == null)
                return null;                 // didn't find it
             else
                {
                previous = current;          // go to next link
                current = current.next;
                }
             }                               // found it
          if( previous.next = current.next; )    //    bypass it
    
          return current;
          }
    How about this? Would these methods work? Then again shouldn't there not even be a check to see if its null since its a circular list or should I leave this?

  12. #12
    emceenugget is offline Senior Member
    Join Date
    Sep 2008
    Posts
    564
    Rep Power
    7

    Default

    you shouldn't actually modify the current node within methods like you do, just store it to a local variable to be used

    and yea, there should be no check for null. you can stop traversing once you loop around. how you do that is up to you, though.

  13. #13
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Default

    so within each method then just create an int current; is what you are saying?

  14. #14
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Question

    Java Code:
    public Link search(int key)      // find link with given key
    int current;
    
          {                           
          while(current.iData != key)        // while no match,
             {
          current = current.next;      // go to next link
             }
          return current;                    // found it
          }
    
    
    // -------------------------------------------------------------
       public Link delete(int key)    // delete link with given key
    
    int current;
    
          {                           // (assumes non-empty list)
          while(current.iData != key)
             {
               previous = current;          // go to next link
               current = current.next;
             }                               // found it
          if( previous.next = current.next; )    //    bypass it
    
          return current;
          }
    Hows this? How do I tackle the problem say if I enter a search key that is not valid and its not found and cant be deleted? a System.out.println method? How do I halt the search

    How would I know the loop has looped around the circle and not found the key it was searching for or attempting to delete?
    Last edited by VinceGuad; 02-25-2009 at 04:35 PM.

  15. #15
    VinceGuad is offline Member
    Join Date
    Jan 2008
    Posts
    36
    Rep Power
    0

    Default

    Maybe....

    Java Code:
     if(current.next != key)
                System.out.println("Could not find");               // didn't find it
    But how does it know it completly looped around before printing this?

Similar Threads

  1. Replies: 9
    Last Post: 11-04-2011, 03:09 AM
  2. Circular Double Linked List
    By theonly in forum Advanced Java
    Replies: 3
    Last Post: 12-06-2009, 05:10 PM
  3. Linked list
    By rosh72851 in forum New To Java
    Replies: 1
    Last Post: 02-05-2009, 07:21 AM
  4. Linked List integer list
    By igniteflow in forum Advanced Java
    Replies: 1
    Last Post: 12-10-2008, 08:53 PM
  5. Linked List help
    By neobie in forum New To Java
    Replies: 8
    Last Post: 12-22-2007, 03:15 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •