Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / November 2007

Tip: Looking for answers? Try searching our database.

single circular linked list : QUESTION.

Thread view: 
HalFas` - 11 Nov 2007 09:34 GMT
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 - 11 Nov 2007 16:10 GMT
> Hi, I have this single circular linked list structure:
>
[quoted text clipped - 24 lines]
>             public List() {
>                 this.head = null;

(Unnecessary re-initialization to null.)

>             }
>
[quoted text clipped - 4 lines]
>                    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;
>
[quoted text clipped - 3 lines]
>                         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.

>                     }
>
[quoted text clipped - 3 lines]
>
> 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?

Signature

Lew

Roedy Green - 11 Nov 2007 17:17 GMT
>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.
Signature

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

Daniel Pitts - 11 Nov 2007 22:03 GMT
> 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 :-)

Signature

Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>



Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.