oldskool linked list

[f. nikita thomas]

import java.io.*;
 
public class ListT
{
   public class Node
   {
       public String data = "";
       public Node link;
 
       public Node()
       {
       }
 
       public Node(String data)
       {
           this.data = data;
       }
   }
 
   public static Node first,last,current,previous,newLink;
   public static String key;
 
   public ListT()
   {
       first = null;
   }
 
   public void insert(BufferedReader infile) throws IOException
   {
       while ((key = infile.readLine()) != null)
       {
           previous = null;
           current = first;
           Node newLink = new Node(key);
           while((current != null) && (key.compareTo(current.data) > 0))
           {
               previous = current;
               current = current.link;
               System.out.println("Here");
           }
           if (previous == null)
           {
               System.out.println("I go");
               first = newLink;
           }
           else
           {
               System.out.println("Again");
               previous.link = newLink;
       printList();
           }
           newLink.link = current;
        }
//return first;
   }
 
   public static void printList()
   {
       newLink = first;
       while(newLink != null)
       {
           System.out.println(newLink.data + " " + newLink.link);
           newLink = newLink.link;
       }
   }
}   

and

import java.io.*;
 
public class run0
{
    private static BufferedReader infile;
    private static PrintWriter outfile;
    private static String s0;
    public static ListT l = new ListT();
 
    public static void main(String[] args) throws IOException
    {
        infile = new BufferedReader(new FileReader(args[0]));
                                    //outfile = new PrintWriter(args[1]);
        l.insert(infile);
        l.printList();
        infile.close();
                                    //outfile.close(); this is for later
    }
}

the above code compiles... however i'm getting an infinite loop on the second while in the class file. please comment out the System.out's in the class file; they are for my debugging. my data file is the australian scrabble sowpods 4 letter list with each word on a single line. also i'm getting repeats in the list, which i added to the file but "i think" i shouldn't have in the outfile. i know it's a logic error on my part. any help at all will be greatly appreciated. thanks.
[ March 23, 2008: Message edited by: f. nikita thomas ]

[Stevi Deter]

Nikita,

You are seeing the duplicates because the code currently doesn't check for them; it will still merrily add them to the linked list. You should add a check to avoid adding the link to the list when you discover there's already a similar item.

[Campbell Ritchie]

Are you trying to create a LinkedList implementation? If so, why have you declared the nodes as static?

[f. nikita thomas]

what i'm attempting to do is a sorted linked list. i declared the Node variables as static because i thought that this would ensure only one instance of them per class creation ... or am i mistaken?

n.

[Campbell Ritchie]

A linked list works like this:
node0--->node1--->node2--->node3--->etc

So each node has a link to the node following it. A lot of linked lists also have a link to the preceding node (called a doubly-linked list). Each of these links is different for each node, so they can't be static. A static field would be the same for each node.

[f. nikita thomas]

geez, i'll get rid of the static !!! btw do you see where i put myself on the merry-go-round? i've been at it since this morning and i just don't see it.

n.

[Henry Wong]

Originally posted by f. nikita thomas:
geez, i'll get rid of the static !!! btw do you see where i put myself on the merry-go-round? i've been at it since this morning and i just don't see it.

n.

Your Merry-Go-Round was created here (well, one of them anyway)....

{
    System.out.println("Again");
    previous.link = newLink;
    printList();
}
newLink.link = current;   

Basically, you printList() method changed the value of newLink, to point to the last member of the list. So, the next line, chained it to a member within the list -- creating a circle.

Henry
[ March 23, 2008: Message edited by: Henry Wong ]

[f. nikita thomas]

hey henry,
i put the printList() method in the loop to see if new Nodes were being created. the loop existed before i added it; taking it out will make no difference. the while "is" sorting the data - although it won't stop:

<snip>

Here
Here
Here
Here
Again
ABBS ListT$Node@1386000
ACHY ListT$Node@30e280
ACRE ListT$Node@a0dcd9
AEON ListT$Node@ecd7e
AGHA ListT$Node@6e1408
AIRY ListT$Node@a1807c
ANNA ListT$Node@147c5fc
ANOA ListT$Node@1d8957f
AREG ListT$Node@16a9d42
ASKS ListT$Node@cdedfd
BACK ListT$Node@c5c3ac
BACS ListT$Node@1ef9f1d
BAMS ListT$Node@12558d6
BAST ListT$Node@1c39a2d
BATE ListT$Node@1abab88
BATS ListT$Node@15a3d6b
BAWN ListT$Node@18a7efd
BEAD ListT$Node@b1c260
BEER ListT$Node@e7b241
BEYS ListT$Node@7c6768
BIOS ListT$Node@cf2c80
BISE ListT$Node@186db54
BLED ListT$Node@116471f
BOLT ListT$Node@167d940

ad infinitum ...


n.
[ March 23, 2008: Message edited by: f. nikita thomas ]

[S Keith]

I tried it with the file: foo, bar, baz

You have a

printList();

call in

insert

making it appear that you have duplicates.

The call to

printList

will also stop you properly linking the list because the

newLink

reference is tampered with, before the link field in

newLink

is set.

if you move

newLink.link = current;

above the call, then that would fix the problem, and you will see that the whole list is printed twice.

 
newLink.link = current;
if (previous == null)
{
  first = newLink;
}
else
{
  previous.link = newLink;
  printList();
}

if you take out:

else
{
  previous.link = newLink;
  printList(); <-- this
}

then you will get your list printed ok

[ March 23, 2008: Message edited by: S Keith ]
[ March 23, 2008: Message edited by: S Keith ]

[f. nikita thomas]

 
newLink.link = current;
if (previous == null)
{
  first = newLink;
}
else
{
  previous.link = newLink;
}   

i took out the printList() method as well as placing the assignment to newlink.link to where you specified. no dice ...

[Campbell Ritchie]

. . . and welcome to the Ranch, S Keith

[S Keith]

howdy.

Can you give me your input file?

If you test it with

foo
bar
baz

there is no problem.


This is exactly what i have in the file run0.java

import java.io.*;
 
class ListT
{
public class Node
{
public String data = "";
public Node link;
 
public Node()
{
}
 
public Node(String data)
{
this.data = data;
}
}
 
public static Node first,last,current,previous,newLink;
public static String key;
 
public ListT()
{
first = null;
}
 
public void insert(BufferedReader infile) throws IOException
{
while ((key = infile.readLine()) != null)
{
previous = null;
current = first;
Node newLink = new Node(key);

while((current != null) && (key.compareTo(current.data) > 0))
{
previous = current;
current = current.link;
}

if (previous == null)
{
first = newLink;
}
else
{
previous.link = newLink;
//printList();
}
newLink.link = current;
}
//return first;
}
 
public static void printList()
{
newLink = first;

while(newLink != null)
{
System.out.println(newLink.data + " " + newLink.link);
newLink = newLink.link;
}
}
} 
 
public class run0
{
private static BufferedReader infile;
private static PrintWriter outfile;
private static String s0;
public static ListT l = new ListT();
 
public static void main(String[] args) throws IOException
{
infile = new BufferedReader(new FileReader(args[0]));
//outfile = new PrintWriter(args[1]);
l.insert(infile);
l.printList();
infile.close();
//outfile.close(); this is for later
}
}

and i get the output:

 
C:\Users\Steven\Desktop>java run0 testfile.txt
bar ListT$Node@addbf1
baz ListT$Node@42e816
foo null
 
C:\Users\Steven\Desktop>

[ March 24, 2008: Message edited by: S Keith ]

[f. nikita thomas]

problem solved thanks to S Keith. apparently:

           while((current != null) && (key.compareTo(current.data) > 0))
           {
               previous = current;
               current = current.link;
               System.out.println("Here"); // <-- drunken sailor. 
           }

the System.out.() statement is the culprit! the other System.out.()'s can remain for testing. why it's causing the loop is still a subject for my investigation. like Henry explained the printList() call will cause a loop, (hence his cryptic comment ...). there are still duplicates with the data but i introduced them and now that i'm not so dizzy, i can handle that issue. thanks to all for your assistance. i'm trying to be a "reaL" programmer, so i need the feedback. take care.

n.
[ March 24, 2008: Message edited by: f. nikita thomas ]