Home | JSP | EJB | JDBC | Java Servlets | WAP  | Free JSP Hosting  | Spring Framework | Web Services | BioInformatics | Java Server Faces | Jboss 3.0 tutorial | Hibernate 3.0 | XML

Tutorial Categories: Ajax | Articles | JSP | Bioinformatics | Database | Free Books | Hibernate | J2EE | J2ME | Java | JavaScript | JDBC | JMS | Linux | MS Technology | PHP | RMI | Web-Services | Servlets | Struts | UML


 

Java Tutorials


 

 

Struts Tutorials

Struts Resources

Visit Forum! Post Questions!
Jobs At RoseIndia.net!

Java Notes: Simple Linked Lists

This shows three programs.

  • A simple singly-linked list. This shows the basics.
  • A doubly-linked list. This is almost as simple as the singly-linked list, but makes some operations easier.
  • Use of the java.util.LinkedList class, which is easy to use because it hides the details.

Simple singly-linked list done "by hand"

The following program is an example of a very simple implementation of a singly-linked list. You should become very comfortable with this. Altho you should always prefer the predefined java.util.LinkedList class when working with linked lists, understanding linking objects is essential to building other structures for which there is no predefined library class.

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
// Purpose: Demonstrates a really simple singly-linked list.
//          Main builds list of words, prints it using two styles.
// Author : Fred Swartz, 21 Feb 2006, placed in the public domain.

import java.util.Scanner;

public class SimpleSinglyLinkedList {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        Elem front = null;    // First element of list.
        Elem back  = null;    // Last element of list.
        
        //... Read a list of words.
        while (in.hasNext()) {
            String word = in.next();
            
            Elem e = new Elem();     // Create a new list element.
            e.data = word;           // Set the data field.
            
            //... Two cases must be handled differently
            if (front == null) {
                //... When the list is empty, we have to set the front pointer.
                front = e;            // Back element will be set below.
            } else {
                //... When we already have elements, we need to link to it.
                back.next = e;       // Link last elem to new element.
            }
            back = e;                // Update back to link to new element.
        }
        
        //... While loop to print list in forward order.
        System.out.println("*** Print words in order of entry");
        Elem curr = front;
        while (curr != null) {
            System.out.println(curr.data);
            curr = curr.next;
        }
        
        System.out.println("*** Print words in order of entry");
        for (Elem e = front; e != null; e = e.next) {
            System.out.println(e.data);
        }
        
        //... Printing list in backward order is an interesting exercise.
        //    But too much for here.
    }
}

////////////////////////////////////////////////////////////////////////// Elem
// Simple class to hold data are sometimes defined with public fields.
// This practice isn't good, but was done here for simplicity.
class Elem {
    public Elem next;    // Link to next element in the list.
    public String data;  // Reference to the data.
}

A simple doubly-linked list

This makes only minor changes so that elements are linked in both forward and backward directions.

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
// Purpose: Shows a simple doubly-linked list.  Very few changes
//          from singly-linked, but allows backwards traversal and
//          easier insertion and deletion.
//          Main builds list of words, prints it forward and backward.
// Author : Fred Swartz, 21 Feb 2006, placed in the public domain.

package linkedlistexamples;

import java.util.Scanner;

public class SimpleDoublyLinkedList {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        Elem2 front = null;    // First element of list.
        Elem2 back  = null;    // Last element of list.
        
        //... Read a list of words.
        while (in.hasNext()) {
            String word = in.next();
            
            Elem2 e = new Elem2();     // Create a new list element.
            e.data = word;           // Set the data field.
            
            //... Two cases must be handled differently
            if (front == null) {
                //... When the list is empty, we have to set the front pointer.
                front = e;            // Back element will be set below.
            } else {
                //... When we already have elements, we need to link to it.
                back.next = e;       // Link last elem to new element.
            }
            e.prev = back;
            back = e;                // Update back to link to new element.
        }
        
        System.out.println("*** Print words in order of entry");
        for (Elem2 e = front; e != null; e = e.next) {
            System.out.println(e.data);
        }
        
        System.out.println("*** Print words in reverse order of entry");
        for (Elem2 e = back; e != null; e = e.prev) {
            System.out.println(e.data);
        }
    }
}

////////////////////////////////////////////////////////////////////////// Elem2
// Simple classes to hold data are sometimes defined with public fields.
// This practice isn't good, but was done here for simplicity.
class Elem2 {
    public Elem2 next;   // Link to next element in the list.
    public Elem2 prev;   // Link to the previous element.
    public String data;  // Reference to the data.
}

Same program using java.util.LinkedList class

This program does the same thing as above using java.util.LinkedList, which hides the linking infrastructure and extra class. It is a doubly-linked list so moving in both directions is possible.

  1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
// Purpose: Contrast library LinkedList with the manual solutions.
//          The link management infrastructure is completely hidden.
// Author : Fred Swartz, 21 Feb 2006, placed in the public domain.

package linkedlistexamples;

import java.util.*;

public class LibraryLinkedList {
    public static void main(String[] args) { 
        Scanner in = new Scanner(System.in);
        
        LinkedList<String> lst = new LinkedList<String>();
        
        //... Read and build list of words.
        while (in.hasNext()) {
            String word = in.next();
            lst.add(word);
        }
        
        //... Enhanced for loop to print list forward.
        //    Could also use an Iterator (forward only) or
        //    ListIterator (forward or backward).
        System.out.println("*** Print words in order of entry");
        for (String s : lst) {
            System.out.println(s);
        }
        
        //... Use ListIterator go to backward.  Start at end.
        System.out.println("*** Print words in reverse order of entry");
        for (ListIterator<String> lit = lst.listIterator(lst.size()); lit.hasPrevious();) {
            System.out.println(lit.previous());
        }
    }
}
Ask programming questions?

 

 

Add This Tutorial To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 

Current Comments

0 comments so far (post your own) View All Comments Latest 10 Comments:
  JDO Tutorials
  EAI Articles
  Struts Tutorials
  Java Tutorials
  Java Certification

Tell A Friend
Your Friend Name

 

 
Browse all Java Tutorials
Java JSP Struts Servlets Hibernate XML
Ajax JDBC EJB MySQL JavaScript JSF
Maven2 Tutorial JEE5 Tutorial Java Threading Tutorial Photoshop Tutorials Linux Technology
Technology Revolutions Eclipse Spring Tutorial Bioinformatics Tutorials Tools SQL
 

Home | JSP | EJB | JDBC | Java Servlets | WAP  | Free JSP Hosting  | Search Engine | News Archive | Jboss 3.0 tutorial | Free Linux CD's | Forum | Blogs

About Us | Advertising On RoseIndia.net  | Site Map

India News

Send your comments, Suggestions or Queries regarding this site at roseindia_net@yahoo.com.

Copyright 2007. All rights reserved.

[an error occurred while processing this directive]