single circular linked list : QUESTION.

Discussion in 'Java' started by HalFas`, Nov 11, 2007.

  1. HalFas`

    HalFas` Guest

    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.
    HalFas`, Nov 11, 2007
    #1
    1. Advertising

  2. HalFas`

    Lew Guest

    HalFas` wrote:
    > 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?

    --
    Lew
    Lew, Nov 11, 2007
    #2
    1. Advertising

  3. HalFas`

    Roedy Green Guest

    On Sun, 11 Nov 2007 01:34:11 -0800, HalFas` <>
    wrote, quoted or indirectly quoted someone who said :

    >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.
    --
    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
    Roedy Green, Nov 11, 2007
    #3
  4. HalFas`

    Daniel Pitts Guest

    HalFas` wrote:
    > 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 :)

    --
    Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
    Daniel Pitts, Nov 11, 2007
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sharp

    Circular linked list

    Sharp, Mar 5, 2005, in forum: Java
    Replies:
    3
    Views:
    1,430
    Thomas G. Marshall
    Mar 5, 2005
  2. Kiuhnm
    Replies:
    16
    Views:
    741
    Jonathan Mcdougall
    Jan 3, 2005
  3. Booser
    Replies:
    1
    Views:
    1,276
    CBFalconer
    Feb 9, 2004
  4. fool
    Replies:
    14
    Views:
    505
    Barry Schwarz
    Jul 3, 2006
  5. joshd
    Replies:
    12
    Views:
    668
    John Carson
    Oct 2, 2006
Loading...

Share This Page