Tutorial: Linked Lists


Authored by
Ronald S. Holland
Total Application Works
RonHolland@sumtotalz.com






To visit my site

HOME] Consulting Design Maintenance Project Testing Training Turnkey Java C++ SQL HTML JavaScript ]


To contact us

© 2002 - 2011 All Rights Reserved Total Application Works


  • Tell a friend about this site (copy and paste the following link or send this page to a friend.)
  • <html>
    <title>Example of a link </title>
    <body>
    <table border>
    <a href="http://sumtotalz.com/TotalAppsWorks/Linkedlist_Tut/LL_Tutorial.html">An Introduction to Linked Lists </a>
    </table>
    </body>
    </html>
    Download Source
    and display a Screenshot
  • On-site classes can be arranged in Java and C++. Send all inquiries to:
  • RonHolland@sumtotalz.com
  1. Java Table of contents
  2. 2nd Java Cup
  3. Pie Chart I
  4. Pie/Bar Chart IB
  5. Pie/Bar Chart II
  6. Pie/Bar Chart III
  7. A Basic Calculator
  8. Linked list Introduction
  9. Linked Lists I
  10. Linked Lists
  11. Linked List II
  12. Linked List III
  13. Linked List IV
  14. Hardware Store I
  15. Hardware Store II
  16. Hardware Store III
  17. Client/Server
  18. Client/Server II
  19. Client/Server III
  20. Client/Server IV
  21. Multithreaded Client/Server
  22. Multithreaded Client/Server II
  23. Multithreaded Client/Server III
  24. Basic Calculator II
  25. Basic Calculator III

Introduction

This tutorial is intended for Java programmers with some experience coding in Java. My experience has been that those persons, who have not taken at least one semester of Java, really struggle with the concepts presented in this set of tutorials. Those who are familiar with the 'C' language and who are familiar with structures and how to create them should find this tutorial contains familiar concepts.

This tutorial is the first of a set of tutorials. It shows how to build a Java Linked List application. This exercise is similar to the one I teach to second semester college Java students. Some of you have already looked at the Java API and have noticed that there is a LinkedList class and are wondering why we are creating another LinkedList class. This is an exercise for those who are interested in seeing how it is done. For Java programmers with some of experience, this should an interesting exercise. I am a proponent of designing before coding, so you should expect to see quite a bit of pseudocode in this tutorial.

This set of tutorials will take you through the steps of building a Linked List application as a driver for a database. Much of the code and logic that we will develop is logically similar to that which is provided in today's database management systems. However, for those who are not familiar with some of the logic used in file I/O, this will provide some very basic insights relative to how a DBMS works. This particular tutorial will show you how to build an elementary linked list.

When you look at the following program requirements, it is obvious that the program is all about the data, how it is viewed and how it is manipulated. So let's proceed with the requirements before I give up the ending. No mystery gives up the ending in the first paragraph. So get out your pipes, violins, and magnifying glasses, as we prepare to "sleuth out" the solution. The clues for this mystery are presented in the section titled, "Requirements for an Application." A famous "sleuther" used to say, "Dr. Watson, the game's afoot." We will start by defining a linked list.

What is a Linked List?

What is a Linked List? It is a self-referential class that contains a reference member and that member contains the address to a class object of the same class type. In real life, there are many instances where we use addresses. For example, we use addresses

  • To designate where we live.
  • To designate where mail is to be sent.
  • To designate our email address.
A Linked List is like a chain where each link in the chain contains the address to the next link in the chain. A class of this type might look like:
  
class node {
   private int data;
   private next refA;

   public node() {}
   void setData( int ) {}
   int getData(  int ) {}
   void setNextRef( node ref ) {}
   node getNextRef( ) {} 
   void init(  ) {}
   void AppendNode( int ) {}
   void InsertNode( int ) {}
   void DeleteNode( int ) {}
   void DisplayList( int ) {}
}
  
Figure 1: Linked list class Node


After the above class is run and data is inserted into the linked list, the chain might look something like the following:

  
    HEAD
+-----------+
| reference | <-- contains the address to the start
+-----+-----+     of the linked list
      | 
      V   
+-----+-----+      +-----------+      +-----------+
|   data    |  +-->|   data    |  +-->|   data    |
+-----------+  |   +-----------+  |   +-----------+
| reference |--+   | reference |  |   | reference |
+-----------+      +-----+-----+  |   +-----+-----+
                         |        |
      +------------------+        |
      |                           |
      V                           |
+-----+-----+      +-----------+  |
|   data    |  +-->|   data    |  |
+-----------+  |   +-----------+  | 
| reference |--+   | reference |--+
+-----------+      +-----------+
Figure 2: Chain of nodes


In an array, data is stored in contiguous memory and can be accessed by using a reference and an index. For example,

  
int ar[] = new int[ 12] ;
 
for ( int i = 0 ; i < ar.length ; i++ )
   ar[ i ] = i ;
Figure 4: Declaring, allocating and filling an array


The above code segment loads the value of i in each succeeding location of the array named ar.

An array is different than a linked list in many ways. In an array,

  • The data is stored in contiguous physical memory.
  • The contiguous memory is addressed using a reference to the first location.
  • By using the name of the array and an index, the data is accessed. For example,
      
    ar[ 1 ] = 5 ;
    
  • The location of the array is resolved at compile time.
  • The array's size cannot be changed at run time.

The organization of data in an array is physical. A linked list

  • Stores data based on the logical order of the data and not the physical order.
    • In other words, a linked list gives the appearance that the data in the list is stored in contiguous memory.
  • Instead of an index, all stored data records are assigned a physical address in memory that the link list algorithm/logic uses to locate the information.
  • A linked list logically organizes the data, rather than by physical address.
  • The memory for each node in the linked list is dynamically allocated at run time.
  • The linked list's size can be changed at run time.
    • This is good if the size required is not known at compile time.

Requirements for a Linked List

This program is intended to be an introduction to linked lists. As such, the requirements are:

  1. Write this program as an application.
  2. The linked list node should be added to the linked list in a LIFO manner
    • All new nodes should be added at the head of the linked list
  3. Create an Add method to add new nodes to the linked list
  4. Create an Remove method to delete/remove nodes from the linked list
  5. Create an DisplayLL method to show the contents of the nodes
  6. These functions should be displayed using a JOptionPane menu.

      
           Linked List Options
    
      1 - Add an integer
      2 - Delete an integer from the of list
      3 - Display the list
    
      4 - Exit
    
     Select one of the options from above     
    
    Figure 5: Linked List Options screen

A Possible Approach to Building an Application

When we look at the requirements (clues), a few items jump out at us.

  1. application - a program with a main() method
  2. Create an Insert method
    • All new nodes should be added at the head of the linked list
      • This means that items will be added as though they were being pushed on a stack
  3. Create an Remove method
  4. Create an DisplayLL method
    • Start at the head of the linked list and walk the list until all of the node data has been displayed

Over the years, I have seen various approaches to building an application. I will use the following simple top-down approach of using templates. Templates allow us to solve this problem from a top down view.

   
/** this is a template for an application */

public Linkedlist {
   class level variables

   public Linkedlist() {
      ...
   }
 
   public static void main( String args[] ) {
      ...
   }

}
   
Figure 6: Simple top-down approach of using templates


Logic for adding nodes

We will use dynamic allocation to get the space for each node at run time. To accomplish this, we will use the Java new operator to allocate space for the linked list object. This is called creating an instance of the object. An example looks like:

  
LinkedList head = null ;
head = LinkedList(num, head);
                   ^     ^
                   |     |
The number to be ->+     +--- The current beginning of the 
added                         linked list
  
Figure 6: Logic for adding nodes


We will update our template so that it looks like:

  
/** this is a template for an application */

public Linkedlist {
   class level variables
     
   // constructor
   public Linkedlist() {
      ...
   }
     
   // constructor
   public LinkedList(int n, LinkedList ln) {
      ...
   }

   public void Add( int num ) { 
      ...
   }
 
   public static void main( String args[] ) {
      ...
   }

}
  
Figure 6: Updated template


Logic for removing nodes

To remove a node from the Linked List, we will do the following:

  1. Check to see if the Linked list has entries.
    • If the Linked list is empty, then there is no further processing required.
  2. Check if the value we are seeking is in the first node in the Linked list.
    • Delete that node by making the value of next the new head.
  3. Start iterating through the Linked list until the value we are seeking is found.
    • Delete that node by removing its reference from the link.
We will update our template so that it looks like:

  
/** this is a template for an application */

public Linkedlist {
   class level variables
     
   // constructor
   public Linkedlist() {
      ...
   }
     
   // constructor
   public LinkedList(int n, LinkedList ln) {
      ...
   }

   public boolean Remove(int num) {
      ...
   }

   public void Add( int num ) { 
      ...
   }

   public void DisplayLL(  ) {
      ...
   }

   public static void main( String args[] ) {
      ...
   }

}
  
Figure 7: Second Updated template


Logic for creating a JOptionPane menu

To create a JOptionPane menu we need to understand the JOptionPane class. The JOptionPane class makes it easy to pop up a standard dialog box that prompts users for a value or informs them of something. For example, the following code snippet allows the program to request and get a number.

 
// read a number from user as a string
      number =
         JOptionPane.showInputDialog( "Enter an integer:" );
 
The following code allows the program to display a menu.
 
menu  =         "                                          \n" ;
menu  = menu  + "    Linked List Options                   \n" ;
menu  = menu  + "                                          \n" ;
menu  = menu  + "  1 - Add an integer                      \n" ;
menu  = menu  + "  2 - Delete an integer from the of list  \n" ;
menu  = menu  + "  3 - Display the list                    \n" ;
menu  = menu  + "                                          \n" ;
menu  = menu  + "  4 - Exit                                \n" ;
menu  = menu  + "                                          \n" ;
menu  = menu  + " Select one of the options from above     \n" ;


ret = JOptionPane.showInputDialog( null ,
                   menu ,
                   "Linked List Menu" ,
                   JOptionPane.PLAIN_MESSAGE ) ;
 
Figure 8: JOptionPane menu


ret contains the option the user entered.

We will update our template so that it looks like:

  
/** this is a template for an application */

public Linkedlist {
   class level variables
     
   // constructor
   public Linkedlist() {
      ...
   }
     
   // constructor
   public LinkedList(int n, LinkedList ln) {
      ...
   }

   public boolean Remove(int num) {
      ...
   }

   public void Add( int num ) { 
      ...
   }

   public void DisplayLL(  ) {
      ...
   }

   public boolean  checkDigit( String strVal ) {
      ...
   }

   public String showIn( String mess , String title ) {
      ...
   }

   public void menu()  {
      ...
   }

   public static void main( String args[] ) {
      ...
   }

}
  
Figure 9: Updated template


Putting It All Together

When we put it all together we get code that looks like:

  
/**************************************************************
 * File: LinkedList.java
 *
 *
 ***********************************************************************/

public class LinkedList {
   public int value;              // value of element
   public LinkedList next;        // reference to next
   private LinkedList head ;

   /** constructor   */
   public LinkedList() {
      /** initialize list head  */
      head = null;

   }

   /** constructor   */
   public LinkedList(int n, LinkedList ln) {
      value = n;
      next = ln;
   }

   public void Add( int num ) {

      head = new LinkedList(num, head);
   }

   public void DisplayLL(  ) {
      LinkedList NodeRef ;
      NodeRef = head;

      /** list all entries  */
      while (NodeRef != null) {
         System.out.println(NodeRef.value);
         NodeRef = NodeRef.next;
      }
   }

      /** **********************************************
       * The Remove function searches for a node
       * with Num as its value. The node, if found, is
       * deleted from the list and from memory.
       * 1. Check to see if the Linked list has entries.
       *    - If the Linked list is empty, then there is no 
       *      further processing required.
       * 2. Check if the value we are seeking is in the first 
       *    node in the Linked list.
       *    - Delete that node by making the value of next the 
       *      new head.
       * 3. Start iterating through the Linked list until the 
       *    value we are seeking is found.
       *    - Delete that node by removing its reference from 
       *      the link.
       *
       ************************************************ */

   void Remove(int num) {
      LinkedList NodeRef, PreviousNode = null;

	/** If the list is empty, do nothing.  */
      if ( !(head == null) ) {
         NodeRef = head ;

	 /** Determine if the first node is the one. */
         if (NodeRef.value == num) {
            head = NodeRef.next;
         }
         else {
            /** Initialize NodeRef to head of list */
            NodeRef = head;

            /** *************************************
             * Skip all nodes whose value member is
             * not equal to num.
             * *************************************** */

            while (NodeRef != null  ) {
               if ( NodeRef.value != num ) {
                  PreviousNode = NodeRef;
                  NodeRef = NodeRef.next;
               }
               else {

                  /** *********************************************
                   * Link the previous node to the node after
                   * NodeRef, then delete NodeRef.
                   *********************************************** */

                  PreviousNode.next = NodeRef.next;
                  System.out.println("\nThe number " + num +
                            " sought has been found.\n") ;
                  break ;
               }
            }
         }  /** End of if-then-else   */
      }
   }


   public static void main(String args[]) {

      LinkedList pp = new LinkedList() ;

      // add some entries to list
      pp.Add(0);
      pp.Add(9);
      pp.Add(2);
      pp.Add(7);
      pp.Add(1);
      pp.Add(10);
      pp.Add(15);
      pp.Add(3);
      pp.Add(8);
      pp.Add(4);
      pp.Add(5);
      pp.Add(6);
      pp.Add(11);

      pp.DisplayLL() ;

      pp.Remove( 15 ) ;
      pp.DisplayLL() ;
   }
}
  
Figure 10: Linked List application


DBMS - DataBase Management System.

inheritance - when a class is defined, any subclass that is defined can inherit the definitions (public and/or protected) of the parent/base classes.

Java API: Linked List - The following are the methods in the Java Linked List.

requirement - In this instance, a specification that documents the functions, performance, design constraints and attributes of a program to be delivered.

Template - is a unique class or pattern that can be used to build other software code.

Java API
Method Summary
 void add(int index, Object element)
          Inserts the specified element at the specified position in this list.
 boolean add(Object o)
          Appends the specified element to the end of this list.
 boolean addAll(Collection c)
          Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
 boolean addAll(int index, Collection c)
          Inserts all of the elements in the specified collection into this list, starting at the specified position.
 void addFirst(Object o)
          Inserts the given element at the beginning of this list.
 void addLast(Object o)
          Appends the given element to the end of this list.
 void clear()
          Removes all of the elements from this list.
 Object clone()
          Returns a shallow copy of this LinkedList.
 boolean contains(Object o)
          Returns true if this list contains the specified element.
 Object get(int index)
          Returns the element at the specified position in this list.
 Object getFirst()
          Returns the first element in this list.
 Object getLast()
          Returns the last element in this list.
 int indexOf(Object o)
          Returns the index in this list of the first occurrence of the specified element, or -1 if the List does not contain this element.
 int lastIndexOf(Object o)
          Returns the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.
 ListIterator listIterator(int index)
          Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
 Object remove(int index)
          Removes the element at the specified position in this list.
 boolean remove(Object o)
          Removes the first occurrence of the specified element in this list.
 Object removeFirst()
          Removes and returns the first element from this list.
 Object removeLast()
          Removes and returns the last element from this list.
 Object set(int index, Object element)
          Replaces the element at the specified position in this list with the specified element.
 int size()
          Returns the number of elements in this list.
 Object[] toArray()
          Returns an array containing all of the elements in this list in the correct order.
 Object[] toArray(Object[] a)
          Returns an array containing all of the elements in this list in the correct order.










HOME] Consulting Design Maintenance Project Testing Training Turnkey Java C++ SQL HTML JavaScript ]

© 2002 - 2011 All Rights Reserved Total Application Works