I need help - singly circular linked list

[amatech]

Hi,

Can someone tell me If my code is right? It compiles ok, but I am not sure if the implementation is right.
I am trying to write a singly circular linked list class with insert, getfirst, getNext, delete and empty methods. Can someone help me with this? Thank you in advance on your help?

1.	public class SingleLinkedCircular {
2.	 
3.		Link head;
4.	 
5.		public void insert(int item) {
6.			if (head == null) {
7.				head = new Link(item, null);
8.				head.next = head;
9.			} else {
10.				head.next = new Link(item, head.next);
11.			}
12.		}
13.	 
14.		public void remove(int key) {
15.			Link current = head;
16.			do {
17.				if (current.next.item == key) {
18.					Link temp = current.next;
19.					current = temp.next;
20.					{
21.						head = head.next;
22.					}
23.					temp = null;
24.					break;
25.				}
26.				current = current.next;
27.			} while (current != head);
28.		}
29.	 
30.		public Link getFirst() {
31.			return head;
32.	 
33.		}
34.	 
35.		public void getNext() {
36.			Link current = head.next;
37.		}
38.	 
39.		public static void main(String args[]) {

The Link Class:

1.	public class Link {
2.		int item = 0;
3.		Link next;
4.	 
5.		public Link() {
6.			// this.item = 0;
7.			Link next = null;
8.			// head = null;
9.		}
10.	 
11.		public Link(int i, Link n) {
12.			item = i;
13.			next = n;
14.		}
15.	}

[Taywin]

It looks much better than your last version. Good to see that you took the 'Link' class out of your linked list class.

Anyway I will help you to complete your 'Link' class. It is almost done and you are almost correct. Line 7, you need to change from "Link next = null;" to "next = null;" and it is done for the class.

Now, referring back to my post in your previous post, there are still things to be done.

1)You need to assign the value 'null' to your 'head' when you first create it. The reason is that Java won't automatically initiate 'null' value to an object accept primitive (int, long, double, float). You have not initiate it but then attempt to check for 'null' in your insert(). You should get an error when compile.

2)In your insert(), you must search (traverse) for the last node whose 'next' is 'head' before you assign 'next' node value. Also, you need to reconnect the circular system.

// assume that the last node is found and may or may not be the same as 'head'
// assume that theNode is the new node to be insert.
Link theNode = new Link(item, null);
lastNode.next = theNode;  // break the circle
theNode.next = head;      // connect the circle back

/*
 before
 head--->...--->lastNode-+
  ^                      |
  |                      |
  +----------------------+

 execute Link theNode = new Link(item, null);
 head--->...--->lastNode-+      theNode---->null
  ^                      |
  |                      |
  +----------------------+

 execute lastNode.next = theNode;
 head--->...--->lastNode---->theNode---->null  // break the circle

 execute theNode.next = head;
 head--->...--->lastNode---->theNode  // connect back
  ^                            |
  |                            |
  +----------------------------+
*/

3)In your remove(), you don't really need to keep the 'target' node which is the node to be removed. However, you must check whether the removed node is the 'head' node. The reason is that removing 'head' node is more difficult that removing any other node along the list.

if (head.item == key) {
  // then you need to check if the list contains 1 item.
  // if so, let head = null
  // otherwise, just reconnect the link of the last node to the node next to 'head'
  // and assign the node to be 'head'

/*
 when head is not null

 start
 head(target)--->nextNode--->...--->lastNode--+
  ^                                           |
  |                                           |
  +-------------------------------------------+

 redirect the next
 head(target)--->nextNode--->...--->lastNode--+
                   ^                          |
                   |                          |
                   +--------------------------+

 chance the nextNode to be the head and ignore the previous head object
 because it will eventually be gotten rid of by garbage collector
 head(target)--->head(node)--->...--->lastNode--+
                   ^                            |
                   |                            |
                   +----------------------------+
*/
}
else {
  // because the first node is not being remove,
  // traverse through the list to find the target node
  // then remove it by assigning the next value of 'before' node of the target node to
  // the 'next' node which is the immediate node after the target node
/*
 start
 head(target)--->beforeNode--->targetNode--->nextNode--->...--+
  ^                                                           |
  |                                                           |
  +-----------------------------------------------------------+

 change the beforeNode.next to the next Node and done
 the targetNode will eventually be gotten rid of by garbage collector
                            +---------------+
                            |               |
                            |               V
 head(target)--->beforeNode-+ targetNode--->nextNode--->...--+
  ^                                                          |
  |                                                          |
  +----------------------------------------------------------+
*/
}

5)You may not need getNext() method at all...

[amatech]

Taywin,

Thanks very much for the help. I have one last question: are the following two methods correct?

public Link getNext() 
         {
	        return head.next;
	}

	public void empty()

	{

		head = null;

	}

Thanks again!