Question:
How can I implement a linked list using Java, since there are no pointers? Can you provide sample code that uses a linked list?

Thanks!

Answer:
You need pointers to implement linked lists and other recursive structures, but the pointers don’t need to be explicit. Like LISP lists, Java objects areimplicit pointers into the heap, and therefore, like LISP, its quite easyto construct recursive structures.

Below is a simple declaration of LISP-like dynamic lists. Note that thedefinition is recursive:

class Dynamic List {      private Object first;      private DynamicList rest;      // etc.   }

This is possible because Java doesn’t need to know how big a DynamicListobject is in order to allocate space for rest; it only needs to know howbig a pointer to a DynamicList object is.

One problem is how to represent the empty list. I chose to use Java’sbuilt-in null pointer. This seemed economical and LISP-like, butit forced me to declare all of the list functions static because invocations like null.isEmpty() wouldn’t make any sense, butDynamicList.isNull(null) is fine. (I should have done the same with tail()and head(), but I was experimenting.)

An alternative would be to rename DynamicList “Cell”, then declareDynamicLists as:

class DynamicList {      private Cell first;      public boolean isNull() {         return first == null;      }      // etc.   }

Of course the data stored in a dynamic list is of type Object. This allowsme to store anything into a DyanmicList. Of course each call to head() needsto cast the returned object into a particular type.

As an application, I give an embarrassingly inefficient pallindrome detector.An input string is coerced into a dynamic list of Character objects, thelist is reversed, coerced back into a string, then compared with the originalstring. At least this offers a test of many of the classic recursivedefinitions of the list methods.

I should point out that we are reinventing the wheel, because Java already provides a dynamic list type: java.utils.Enumeration.class*/class DynamicList { private Object first; private DynamicList rest; public DynamicList(Object f, DynamicList r) { first = f; rest = r; } public DynamicList(Object f) { first = f; rest = null; } // these could throw nullPointerExceptions public Object head() { return first; } public DynamicList tail() { return rest; } // some standard static methods public static boolean isNull(DynamicList obs) { return (obs == null); } public static DynamicList putFirst(Object f, DynamicList obs) { return new DynamicList(f, obs); } public static int length(DynamicList obs) { if (isNull(obs)) return 0; else return 1 + length(obs.tail()); } public static DynamicList append(DynamicList obs1, DynamicList obs2) { if (obs1 == null) return obs2; else { DynamicList temp = append(obs1.tail(), obs2); return putFirst(obs1.head(), temp); } } public static DynamicList putLast(Object l, DynamicList obs) { if (obs == null) return new DynamicList(l); else return putFirst(obs.head(), putLast(l, obs.tail())); } public static DynamicList reverse(DynamicList obs) { if (obs == null) return null; else return putLast(obs.head(), reverse(obs.tail())); }}public class PalDemo { private static DynamicList stringToList(String s) { DynamicList chars = null; int size = s.length(); for(int i = 0; i < size; i++) chars = DynamicList.putLast(new Character(s.charAt(i)), chars); return chars; } private static String listToString(DynamicList chars) { int size = DynamicList.length(chars); StringBuffer sb = new StringBuffer(size); for(int i = 0; i < size; i++) { sb.insert(i, ((Character)chars.head()).charValue()); chars = chars.tail(); } return new String(sb); } public static void main(String[] args) { DynamicList chars, chars2; String s; chars = stringToList(args[0]); chars2 = DynamicList.reverse(chars); s = listToString(chars2); System.out.println(args[0] + " reversed = " + s); if (args[0].equals(s)) System.out.println("pallindrome detected"); else System.out.println("not a pallindrome"); }}