[6042] in java-interest
Re: Linked List in Java
daemon@ATHENA.MIT.EDU (Stefano Cazzella)
Sun Mar 17 16:45:52 1996
Date: Sun, 17 Mar 1996 22:37:02 +0200
Reply-To: Java Interest <JAVA-INTEREST@JAVASOFT.COM>
From: Stefano Cazzella <cazzella@MIX.IT>
To: Multiple recipients of list JAVA-INTEREST
<JAVA-INTEREST@JAVASOFT.COM>
At 10.46 17/03/96 +0100, you wrote:
>Hi from Germany!
>
>How can I create a linked list in Java?
>Where can I find a simple example?
I'm not an expert java-programmer (I'm still learning the language), so
probably someone else has a better solution.
A (simple) linked list is a dynamic data structure made of records and
links: any record has some fields, one of them is the link to the next
record. Every list has a start and an end; from the first record you can
access (through its link) only the second record, from the second the third
and so on. (This is only to verify we are talking about the same thing).
In java there aren't arithmetic pointers, like in C or pascal, to realize
links but, there are references to objects, and you can use references to
realize links. I did not find any examples so I write one for you (I hope
there are no bugs, anyway I tried the code). In the example I implement a
very simple queue: a FIFO (first in, first out) list. Every record has two
fields: a key to identify the record and the link to the next record.
public class Queue
{
private Record first;
private Record last;
public Queue()
/* Constructs an empty queue */
{
first=null;
last=null;
}
public void in(int i)
/* Inserts a new record with key i at the end of the queue */
{
if(first==null)
{
first=new Record(i);
last=first;
}
else
{
last.next=new Record(i);
last=last.next;
}
}
public int head() throws EmptyException
/* Returns the key of the first record in the queue, if the queue
isn't empty; else throws an exception */
{
if(first==null)
{
throw new EmptyException();
}
else
{
return first.key;
}
}
public void out()
/* Deletes the first record of the queue */
{
if(first!=null)
{
first=first.next;
if(first==null) last=null;
}
}
public boolean empty()
/* Returns true if the queue is empty, false otherwise */
{
return first==null;
}
public static void main(String[] argv)
/* Example */
{
Queue q=new Queue();
q.in(2);
q.in(3);
q.in(5);
for(;;)
{
try
{
System.out.println(q.head());
q.out();
}
catch(EmptyException e)
{
System.out.println("The queue is empty.");
break;
}
}
}
}
class Record
{
public int key;
public Record next;
public Record(int i)
/* Constructs a new record with key i and no successor */
{
key=i;
next=null;
}
}
class EmptyException extends Exception
{
}
In the out method I don't deallocate the first record because in Java the
memory is freed by a garbage collector that periodically scans the memory
and frees the object that are not used (that are not referenced).
Bye!
Stefano Cazzella
from: Roma, Italy
e-Mail: cazzella@mix.it
