Results 1 to 15 of 15
- 02-25-2009, 04:22 AM #1
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
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.
- 02-25-2009, 04:42 AM #2
Senior Member
- Join Date
- Sep 2008
- Posts
- 564
- Rep Power
- 13
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.
- 02-25-2009, 04:43 AM #3
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
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 05:40 AM.
- 02-25-2009, 04:46 AM #4
Senior Member
- Join Date
- Sep 2008
- Posts
- 564
- Rep Power
- 13
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; }
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 04:48 AM. Reason: a little more...
- 02-25-2009, 04:51 AM #5
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
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 04:53 AM.
- 02-25-2009, 05:00 AM #6
Senior Member
- Join Date
- Sep 2008
- Posts
- 564
- Rep Power
- 13
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.
- 02-25-2009, 05:06 AM #7
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
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?
- 02-25-2009, 05:25 AM #8
Senior Member
- Join Date
- Sep 2008
- Posts
- 564
- Rep Power
- 13
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.
- 02-25-2009, 05:38 AM #9
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
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; }
- 02-25-2009, 05:50 AM #10
Senior Member
- Join Date
- Sep 2008
- Posts
- 564
- Rep Power
- 13
instead of using the first node for anything, just use the current node as a starting point.
- 02-25-2009, 06:01 AM #11
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
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; }
- 02-25-2009, 06:25 AM #12
Senior Member
- Join Date
- Sep 2008
- Posts
- 564
- Rep Power
- 13
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.
- 02-25-2009, 04:48 PM #13
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
so within each method then just create an int current; is what you are saying?
- 02-25-2009, 04:53 PM #14
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
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; }
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 05:35 PM.
- 02-25-2009, 05:38 PM #15
Member
- Join Date
- Jan 2008
- Posts
- 36
- Rep Power
- 0
Similar Threads
-
Basic Circular Linked List - addFirst() method works improperly
By carlodelmundo in forum New To JavaReplies: 9Last Post: 11-04-2011, 04:09 AM -
Circular Double Linked List
By theonly in forum Advanced JavaReplies: 3Last Post: 12-06-2009, 06:10 PM -
Linked list
By rosh72851 in forum New To JavaReplies: 1Last Post: 02-05-2009, 08:21 AM -
Linked List integer list
By igniteflow in forum Advanced JavaReplies: 1Last Post: 12-10-2008, 09:53 PM -
Linked List help
By neobie in forum New To JavaReplies: 8Last Post: 12-22-2007, 04:15 AM
Bookmarks