Trouble Developing Singly Linked Circular List

[VinceGuad]

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?

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?

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.

[emceenugget]

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.

[VinceGuad]

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....

[emceenugget]

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:

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.

[VinceGuad]

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" ...

[emceenugget]

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.

[VinceGuad]

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?

[emceenugget]

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.

[VinceGuad]

   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"

[emceenugget]

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

[VinceGuad]

   

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?

[emceenugget]

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.

[VinceGuad]

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

[VinceGuad]

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?

[VinceGuad]

Maybe....

 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?