Login | Register   
RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX

Tip of the Day
Language: Java Language
Expertise: Beginner
May 13, 1997

How to implement a linked list

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


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 are implicit pointers into the heap, and therefore, like LISP, its quite easy to construct recursive structures.

Below is a simple declaration of LISP-like dynamic lists. Note that the definition 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 DynamicList object is in order to allocate space for rest; it only needs to know how big a pointer to a DynamicList object is.

One problem is how to represent the empty list. I chose to use Java's built-in null pointer. This seemed economical and LISP-like, but it forced me to declare all of the list functions static because invocations like null.isEmpty() wouldn't make any sense, but DynamicList.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 declare DynamicLists 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 allows me to store anything into a DyanmicList. Of course each call to head() needs to 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, the list is reversed, coerced back into a string, then compared with the original string. At least this offers a test of many of the classic recursive definitions 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"); } }

DevX Pro
Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



Thanks for your registration, follow us on our social networks to keep up-to-date