Single Linked Circular List in Java

[amatech]

Hi guys,

I am new to java and I need to create a a singly linked circular list in java with the following methods:
insert new node, delete node, get next node, get first node and create empty list.

Here is what I have so far and I am not sure if I am on the right track or not? Your help will be much appreciated. Thank you in advance!

public class SingleLinkedCircularL
{
public class Link
{
int item=0;
Link next;

public Link()
{
//this.item = 0;
Link next = null;
}
public Link(int i, Link n)
{
item = i;
next = n;
}
}
Link head;

public void insert(int item)
{
if(head == null)
{
head = new Link(item,null);
head.next = head;
}
else
{
head.next = new Link(item,head.next);
}
}

public void remove(int key)
{
Link current = head;
do
{
if(current.next.item == key )
{
Link temp = current.next;
current = temp.next;
if(temp == head)
{
head = head.next;
}
temp = null;
break;
}
current = current.next;
} while(current != head);
}

public static void step(Link current)
{
current= current.next;
}
public static void main(String args[]) {

}
}

[Taywin]

Please post your code using 'code' tag.

OK, here you go.

1)Are you creating 'Link' class as the inner class of your SingleLinkedCircular class? I don't think it is a good idea to put the 'Link' class inside your linked list. Take it out to be its own class.

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

3)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
  ^                            |
  |                            |
  +----------------------------+
*/

4)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)Your step() is almost correct. You need to check whether the 'current' is null too. If it is null, return null.

6)The getFirstNode() simply returns the 'head'.

[amatech]

Hi Taywin,

Thank you for the feedback, I have added the suggestions you have mentioned above. Attached is the updated code. Please review it and let me know. Also would please check my getLast() method. Thank you very much again for your help.

public class SingleLinkedCircular{ 
	 


public class Link 
{ 
int item=0; 
Link next;


 
public Link() 
{ 
//this.item = 0; 
Link next = null; 
head = null;
} 
public Link(int i, Link n) 
{ 
item = i; 
next = n; 
} 
} 
Link head;

 
public void insert(int item) 
{ 
if(head == null) 
{ 
head = new Link(item,null); 
head.next = head; 
} 
else 
{ 
head.next = new Link(item,head.next); 
} 
} 
 
public void remove(int key) 
{ 
Link current = head; 
do 
{ 
if(current.next.item == key ) 
{  
Link temp = current.next; 
current = temp.next; 
if(temp == head) 
{ 
head = head.next; 
} 
temp = null; 
break; 
} 
current = current.next; 
} while(current != head); 
} 

public void getFirst()
{
	Link current = head; 
		
}
public void getNext()
{
	Link current = head.next;
}

public static void main(String args[]) {
} 
}

[Taywin]

Hmm... I don't really see what I suggested in your implementation... The getFirst() needs to return the 'Link' class, not void. Also, you don't need to create a new 'current' object inside it. The getNext() was half correct before... Please reread my suggestion and work on each bulletin...

[amatech]

Taywin,

Did you mean, change public void getFirst() to public Link getFirst? Also, I did not have the getNext() before. I am really new to java, Please help with some code. Thanks in advance.

[Taywin]

@amatech,
The getFirst() is for your get first node mentioning from your first post. And yes, you need to change it to public Link getFirst(), but you need to 'return head;' inside the method. By the way, your Link class is still inside your SingleLinkedCircular class. Please read my explanation again.

Also, this is not only about new to Java. It seems that you still have not had a clear idea about circular linked list. What I posted was about algorithm to work with a circular linked list more or less. Please read the linked list as well.

[amatech]

Thanks for the input. I made the changes. Please, review my code.
I appreciate your input. Is my code correct? Is my getNext() correct?

Thanks again

public class SingleLinkedCircular {

	Link head;

	public void insert(int item) {
		if (head == null) {
			head = new Link(item, null);
			head.next = head;
		} else {
			head.next = new Link(item, head.next);
		}
	}

	public void remove(int key) {
		Link current = head;
		do {
			if (current.next.item == key) {
				Link temp = current.next;
				current = temp.next;
				{
					head = head.next;
				}
				temp = null;
				break;
			}
			current = current.next;
		} while (current != head);
	}

	public Link getFirst() {
		return head;

	}

	public void getNext() {
		Link current = head.next;
	}

	public static void main(String args[]) {
	}
}

THE LINK CLASS:

public class Link {
	int item = 0;
	Link next;

	public Link() {
		// this.item = 0;
		Link next = null;
		// head = null;
	}

	public Link(int i, Link n) {
		item = i;
		next = n;
	}
}