single circular linked list : QUESTION.

[HalFas`]

Hi, I have this single circular linked list structure:

public class ListItem {
int n;
ListItem next;

public ListItem() {
this.n = 0;
this.next = null;
}

public ListItem(int n, ListItem e) {
this.n = n;
this.next = e;
}

public int getValue() { return this.n; }
public ListItem getNext() { return this.next; }
public void setValue(int n) { this.n = n; }
public void setNext(ListItem nextItem) { this.next =
nextItem; }
}


public class List {
ListItem head;

public List() {
this.head = null;
}

public ListItem getHead() { return this.head; }

public void Insert(int n) {
if (this.head == null) {
this.head = new ListItem(n, null);
this.head.next = head;
} else if (this.head.getNext() == null) {
this.head = new ListItem(n, this.head);
head.setNext(head);
} else {
this.head.next = new ListItem(n, this.head.next);
}

}

public void Remove(int Key) {
ListItem curr = this.head;

do {
if ( curr.next.getValue() == Key ) {
ListItem temp = curr.getNext();
curr.setNext(temp.getNext());
} curr = curr.getNext();

if (curr.getNext() == this.head && curr.getValue()
== Key) {
this.head.setNext(null);
curr.setNext(null);
}

} while ( curr != this.head );
}
}


My question is, how to optimize Remove(int Key) method.
Maybe anyone have some docs, about SINGLE circular linked list's.


Thanks, for any help.

 

[Lew]

Hi, I have this single circular linked list structure:

public class ListItem {
int n;
ListItem next;

public ListItem() {
this.n = 0;
this.next = null;
}

public ListItem(int n, ListItem e) {
this.n = n;
this.next = e;
}

public int getValue() { return this.n; }
public ListItem getNext() { return this.next; }
public void setValue(int n) { this.n = n; }
public void setNext(ListItem nextItem) { this.next =
nextItem; }
}


public class List {
ListItem head;

public List() {
this.head = null;

(Unnecessary re-initialization to null.)

}

public ListItem getHead() { return this.head; }

public void Insert(int n) {
if (this.head == null) {
this.head = new ListItem(n, null);
this.head.next = head;

Since 'head' was already pointed to the new item, 'head.next' now points to
'head' itself.

} else if (this.head.getNext() == null) {
this.head = new ListItem(n, this.head);

'head.next' now points to the former 'head' instance.

head.setNext(head);

'head.next' will now point to the new item, instead of to the now-lost former
'head' instance.

Why did you use setNext() here and head.next = ... in the other places?

} else {
this.head.next = new ListItem(n, this.head.next);

This call points 'head.next' of the new item at the old 'head.next' but keeps
the old 'head', pointing its 'next' to the new item. This might be what you
want, or perhaps you intended the new item to be the new head?

}

}

public void Remove(int Key) {

It is conventional to name variables with an initial lower-case letter to
distinguish them from class names.

ListItem curr = this.head;

do {
if ( curr.next.getValue() == Key ) {
ListItem temp = curr.getNext();
curr.setNext(temp.getNext());
} curr = curr.getNext();

Watch your indentation.

if (curr.getNext() == this.head && curr.getValue()
== Key) {
this.head.setNext(null);
curr.setNext(null);

Since 'head' and 'curr' point to the same instance, these two statements do
the same thing.

}

} while ( curr != this.head );
}
}


My question is, how to optimize Remove(int Key) method.

First, make it right. Then, make it fast.

Maybe anyone have some docs, about SINGLE circular linked list's.

What does your favorite search engine have for you?

 

[Roedy Green]

My question is, how to optimize Remove(int Key) method.
Maybe anyone have some docs, about SINGLE circular linked list's.

The whole point of a doubly linked list is fast remove. Given the
node to remove, you link forward and back to find the successor and
predecessor. You can then patch the links to bypass the node. There is
no loop needed. See my LinkedList implementation, written before Sun
issued theirs at http://mindprod.com/products2.html#LINKEDLIST

I did a linked list years ago in assembler where each node had a
single pointer, the xor of the forward and back pointers. You could
then rapidly traverse the list in either order. You can't do that in
Java since you can't do mathematical operations on references.

A single linked list usually has only back pointers. You can traverse
the list in reverse order only LIFO. You can also do one where you
can only traverse in forward order FIFO. In the root you track the
current end of the chain.

 

[Daniel Pitts]

Hi, I have this single circular linked list structure: [snip]
My question is, how to optimize Remove(int Key) method.
Maybe anyone have some docs, about SINGLE circular linked list's.


Thanks, for any help.

Unless you are writing this for an exercise, I recommend using the built
in List implementations.

If you are doing it as an exercise, then good luck