Getting Started with C++: Linked Lists I

Author: Ronald S. Holland
at
Total Application Works






To visit my site

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



To contact us

© 2002 - 2015 All Rights Reserved Total Application Works


  • Tell a friend about this site (copy and paste the following HTML page into a file (e.g., using Notepad).)

  • <html>
    <head>
    <title>Example of a link </title>
    </head>
    <body>
    <a href="http://www.sumtotalz.com/TotalAppsWorks/CPP/LINKED_LIST/CPPLL_I.zip">How to Create a Basic Linked List I Application </a>
    </table>
    </body>
    </html>
    Source
    Screenshot


Learning to Program in C++

  • Intro to C++ The basics of C++
  • If statements
  • Loops in C++ All you want to know about loops
  • Functions Functions...all about them, making and using the critters
  • Switch case About the switch case structure
  • Pointers Using pointers to access memory locations
  • Structures Structures, all about 'em, and how to use 'em
  • Arrays All about arrays
  • Strings About character arrays (strings)
  • File I/O About file i/o
  • Typecasting Typecasting: making variables look like another data-type
  • Classes Introduction to Object Oriented Programming (OOP)
  • < Inline functions More information about functions
  • Command line arguments How to accept command line arguments (AND checking file existence)
  • Linked Lists The basics of singly linked lists
  • Recursion Recursion--a function calling itself
  • Variable argument lists Functions accepting a variable number of arguments
  • Binary Trees Introduction to an important abstract data type
  • Inheritance Inheritance - An Overview
  • Inheritance continued Inheritance - Syntax and examples
  • Initialization Lists and Inheritance lists are necessary for most classes that use inheritance or include objects
  • C++ Class Design More tips and tricks for class design
  • Enumerated types Learn to use enumerated types for type-safety and clarity
  • Formatted Output in C++ using iomanip Learn how to create nicely formatted output in C++
  • Generating random Numbers Tutorial by RoD on generating random numbers.
  • Using Modulus Tutorial by Ron Holland on the modulus operator
  • Templates in C++ Learn how to use templated classes in C++
  • Templated functions Templates can be used to write generic functions as well as generic classes
  • Template specialization and partial specialization Learn how to optimize templates by creating specialized instances for certain types
  • Understanding the C Preprocessor -- Constants, Macros, and other Tricks Learn how to use the C preprocessor

Introduction

This tutorial assumes that you have previous experience with C++ programming. it is not intended to be a tutorials on C++ programming. A linked list is a means for allowing data to be stored in memory or on a storage device.

Consider the following example where we declare a variable of type int.

  
type of variable
    |    +------------- name of variable
    |    |   +----- value stored
    V    V   V
   int   a = 5 ;
  
In the above example, the name indicates the location in memory where the value 5 is stored. An array allows for multiple values to be stored in contiguous memory locations. A linked list is similar to an array because both allow for data to be stored in multiple locations and both are referenced with a single name. Where an array's memory is contiguous, usually a linked list is not stored in contiguous memory. A description of a linked list follows in the next section.

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. Where we live is a container that is used to hold our stuff.
  • To designate where mail is to be sent. Mail is sent to a mailbox container.
  • To designate our email address. Email is sent to an online mailbox container.
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: Basic Linked list Template


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 |
|location 10|--+   |location 50|   |   |location 99|
+-----------+      +-----+-----+   |   +-----+-----+
                         |         |
      +------------------+         |
      |                            |
      V                            |
+-----+------+      +------------+ |
|   data     |  +-->|   data     | |
+------------+  |   +------------+ |
| reference  |  |   | reference  | |
|location 999|--+   |location 456|-+
+------------+      +------------+
Figure 2: Depiction of a Linked List


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 ;
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 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. In Figure 2 above, the reference/memory location indicates where the data is stored.

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 a Remove method to delete/remove nodes from the linked list
  5. Create an DisplayLL method to show the contents of the nodes
  6. Modify the add method so that elements are added in ascending sorted order.
  7. Create an addLast method to add new elements to the tail/end of the list.
  8. Create an addFirst method to add new elements to the head of the list.
  9. Create an Remove method to delete an element from the Linked List.
  10. Create an isEmpty method to determine if the Linked List has any entries.
  11. Create a contains method that finds out if a particular value is in the Linked List.
  12. Use Holland's OOP Programming Design Model to build this program.

What is the Holland's OOP Programming Design Model?

In object-oriented programming, programming revolves around the data. So in this style, at the top is the data. It might be depicted as follows:

  
          +--------------+
          |      Data    |<----+  
          +-------+------+     | 
                  ^            |
                  |----------->+
                  V            ^
          +-------+------+     |
          |   Top-down   |     | 
          |  Structured  |<----+
          |  programming |     |
          |  on Classes  |     | (step-wise)
          |  and methods |     | (refinement)
          +--------------+     | (as needed) 
                  |            |
                  +------------+ 
 
  
Figure 3: Holland's OOP Programming Design Model


Experience has taught me that structured programming simplifies design and program maintenance.

What is Structured Programming?

Structured Programming is a technique that assigns a module to a task. This style of programming also refers to techniques for creating consistent, modular application code, which is also called modular application development. When you consider the purpose of this style of development, you will quickly determine that it is task oriented and from this perspective it is different from OOP programming, which is data oriented. The purpose of both structured programming and OOP programming is to accomplish a task. Composition is used to handle complex tasks. Composition occurs when several objects are combined to build a more complex object. A car is an example of a complex object because it is composed of the following objects/classes:

  • Wheel
  • Clock
  • Radiator
  • Chair_Seat
  • Window
  • Brakes
  • Engine
  • etc.
A simple example of composition is:

class Wheel {
} 

class Clock {
} 

class Radiator {
} 

class Chair_Seat {
} 

class Window {
} 

class Mirror {
} 

Class Brakes {
} 

Class Engine {
} 

/** ***********************************
 *
 * An example of composition follows.
 *
 ***************************************/
Class Automobile {
   Wheel      wheel() ;
   Clock      clock() ;
   Radiator   radiator() ;
   Chair_Seat bucketSeat() ;
   Chair_Seat benchSeatRear() ;
   Window     windshield() ;
   Mirror     rearView();
   Mirror     driverSide();
   Mirror     passengerSide();
   Brakes     brakes() ;
   Engine     engine() ;     
     ...
} 
 
Figure 4: Composition Example


You will note that some of the classes above are themselves a composite of other objects.

In Figure 5 below, I show math functions used in 'C' subroutines and the same functions used in a 'C++' class.

Some Math Functions
'C' Math Functions My 'C++' Math Librariy
  

int main()
{
}
float abs(float m) {
  ...
}
float acos(float m) {
  ...
}
float asin(float m) {
  ...
}
float atan(float m) {
  ...
}
float atof(float m) {
  ...
}
float cosh(float m) {
  ...
}
float log(float m) {
  ...
}
float log10(float m) {
  ...
}
float __max(float m) {
  ...
}
float __min(float m) {
  ...
}
float scanf(float m) {
  ...
}
float sin(float m) {
  ...
}
float sinh(float m) {
  ...
}
float sqrt(float m) {
  ...
}
float tan(float m) {
  ...
}
float tanh(float m) {
  ...
}
  
   
class MyMathLib  {

   public:
      MyMathLib(void)   ; 
        
     ~MyMathLib();    
     float abs(float m) ;
     float acos(float m) ;
     float asin(float m) ;
     float atan(float m) ;
     float atof(float m) ;
     float cosh(float m) ;
     float log(float m)  ;
     float log10(float m) ;
     float __max(float m) ;
     float __min(float m) ;
     float scanf(float m) ;
     float sin(float m) ;
     float sinh(float m) ;
     float sqrt(float m) ;
     float tan(float m) ;
     float tanh(float m) ;     
};


float MyMathLib::abs(float m) {
  ...
}
float MyMathLib::acos(float m) {
  ...
}
float MyMathLib::asin(float m) {
  ...
}
float MyMathLib::atan(float m) {
  ...
}
float MyMathLib::atof(float m) {
  ...
}
float MyMathLib::cosh(float m) {
  ...
}
float MyMathLib::log(float m) {
  ...
}
float MyMathLib::log10(float m) {
  ...
}
float MyMathLib::__max(float m) {
  ...
}
float MyMathLib::__min(float m) {
  ...
}
float MyMathLib::scanf(float m) {
  ...
}
float MyMathLib::sin(float m) {
  ...
}
float MyMathLib::sinh(float m) {
  ...
}
float MyMathLib::sqrt(float m) {
  ...
}
float MyMathLib::tan(float m) {
  ...
}
float MyMathLib::tanh(float m) {
  ...
}
  
Figure 5: Math Functions in 'C' and 'C++'


I used top-down structured programming (TDSP) to develop the "C" math functions. I then took the same math functions and embedded them in a class and used these functions/methods in my 'C++" programming. I have converted a great deal of 'C' code to 'C++' using this method (no pun intended). The point is that top=down structured programming can be applied to Object Oriented Programming, as depicted in Figure 3 or using the mathematical associative law, af(x) = f(x)a. In this case, f(x) equals the math functions and a equals the top=down structured programming. I have successfully used this technique (TDSP) on new 'C++' design. In Figure 6 below, two data records were developed and then the methods to manipulate these records were developed, using top-down structured programming and the requirements for building the program.

Data
Inventory Record Address Record
  
int recID ;
int quantity ;
String toolType = "" ;
String brandName = ""  ;
String toolDesc  = "" ;
String partNum = ""  ;
String cost = ""  ;
String recordTokens[] ;
boolean myDebug = false ;
long filePos ;
long fileLen ;
  
  
class AddressBook    {                 
    
   protected:
      int  recordID;
      char firstName[30];
      char lastName[30];
      char address[30];
      char city[30];
      char state[15];
      char zip[15];
      char telephone[20];
      char fax[30];
      char email[30];  

   public:
      AddressBook() ;
      ~AddressBook() ;
      void DisplayData( int n )  ;  
      void AddRec( int n )  ;  
      void DeleteRec( int n )  ; 
      void UpdateRec( int ) ;  
      void UpdateData( long n) ; 
      void InitData() ;  
      void ReadData(int);   
      void WriteData(); 
      static int RecordCount();  
                                   
};

  
Figure 6: Top-down based on Data


Many designers struggle to develop efficient overall class structure. I propose using TDSP in developing classes. You might find that you have fewer warts in your class design.

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 LinkedList(int n, LinkedList ln) {
      ...
   }

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

   void addLast( int num) {
      ...
   }

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

   public void DisplayLL() {
      ...
   }

   void Remove(int num) {
      ...   
   }

   public boolean isEmpty() {
      ...
   }

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

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

}
   
Figure 7: Template for an application


Logic for addFirst Method

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 8: Logic for addFirst Method


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.

Logic for add Method

The logic for the add Method is as follows:

  1. Create a new node.
  2. Check to see if the Linked list has entries.
    • If the Linked list is empty, then head will contain the reference to the new node.
  3. Else iterate through the linked list until the value to be added is less than a value already in the list.
    • At the first value in the list that is greater than the new value:
      • Insert the new value before this existing value.

Logic for addLast Method

In the addLast Method:

  1. Create a new node.
  2. Iterate through the list until the end is reached and then add the new node at the tail of the list.

Logic for DisplayLL Method

In the DisplayLL Method:

  1. Iterate through the list and display each element to the screen.

Logic for isEmpty Method

In the isEmpty Method:

  1. If the head is null, this means that the list is empty; therefore, return false.
  2. If the head is not null, this means that the list is not empty; therefore, return true.

Logic for contains Method

In the contains Method:

  1. A parameter is passed to the contains Method.
  2. Iterate through the list and find out if the passed parameter exists in the list.
  3. Return true if the value exists.
  4. Return false if the value does not exists.

Putting It All Together

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

  
/**************************************************************
 * File: LinkedList.java
 *
 * Methods:
 *    -  public LinkedList()
 *    -  public LinkedList(int n, LinkedList ln)
 *    -  public void add( int num )
 *    -  void addLast( int num)
 *    -  public void addFirst( int num )
 *    -  public void DisplayLL()
 *    -  void Remove(int num)
 *    -  public boolean isEmpty()
 *    -  public boolean contains( int num )
 *    -  public static void main(String args[])
 *
 *
 *
 *************************************************************/

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

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

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

   /** **********************************************
    *  Method: add( int num )
    *
    *  Purpose:  Adds a value to the list in sorted
    *  order.
    *
    ************************************************ */
   public void add( int num ) {
      LinkedList NewNode, NodeRef, PreviousNode = null ;

      /** ***********************************************
       *  Allocate a new node & store Num
       *********************************************** */
      NewNode = new LinkedList();
      NewNode.value = num;

      /** ***********************************************
       * If there are no nodes in the list
       * make NewNode the first node
       *********************************************** */

      if (head == null )  {
         head = NewNode;
         NewNode.next = null ;
      }
      else	{  /** Otherwise, insert NewNode at end */
         /** *********************************************
          * Initialize NodeRef to head of list
          ********************************************* */

         NodeRef = head;

           // Skip all nodes whose Value member is less
           // than Num.
         while (NodeRef != null && NodeRef.value < num)  {
            PreviousNode = NodeRef ;
            NodeRef = NodeRef.next;
         }

 	 /** **********************************************
          * Insert the node after the one pointed to
	  * by PreviousNode and before the one pointed to
	  * by NodePtr.
          ********************************************  */

         PreviousNode.next = NewNode;
         NewNode.next = NodeRef ;
      }
   }

   /** **********************************************
    *  Method: addLast( int num )
    *
    *  Purpose:  Adds a node containing the value passed
    *  in num, to the end of the list.
    *
    ************************************************ */
   void addLast( int num) {
      LinkedList NodeRef, NewNode ;
      NodeRef = head;

      /** **********************************************
       * Allocate a new node & store Num
       *
       ************************************************ */
      NewNode = new LinkedList();
      NewNode.value = num;
      NewNode.next = null ;

      /** **********************************************
       * If there are no nodes in the list
       * make NewNode the first node
       ********************************************** */
      if ( head == null )
         head = NewNode;
      else	{  // Otherwise, insert NewNode at end
           // Initialize NodePtr to head of list
         NodeRef = head;

           // Find the last node in the list
         while ( NodeRef.next != null )
            NodeRef = NodeRef.next;

              // Insert NewNode as the last node
         NodeRef.next = NewNode;
      }
   }

   /** **********************************************
    *  Method: addFirst( int num )
    *
    *  Purpose:  Adds a value to the beginning of the
    *  list.
    *
    ********************************************** */
   public void addFirst( int num ) {

      head = new LinkedList(num, head);
   }

   /** **********************************************
    * Method: DisplayLL()
    *
    * Purpose: Iterate through a non-empty linked list
    *          until all of the entries are displayed on
    *          the screen.
    *
    ************************************************ */
   public void DisplayLL() {
      LinkedList NodeRef ;
      NodeRef = head;

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

   /** **********************************************
    * Method: Remove(int num)
    *
    * 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") ;

                  /** quit while loop - node found   */
                  break ;

               } /** End of inner if-then-else   */
            }  /** End of while loop   */
         }  /** End of outer if-then-else   */
      }  /** End of outer if   */
   }

   /** **********************************************
    * Method: isEmpty()
    *
    * Purpose: Determine if the linked list is empty.
    *          Return:
    *              - true if linked list is not empty
    *              - false if linked list is empty
    *
    ************************************************ */
   public boolean isEmpty() {
      boolean ret ;

      if ( head == null ) {
         ret = false ;
      }
      else {
         ret = true ;
      }

      return ret ;
   }

   /** **********************************************
    * Method: contains( int num )
    *
    * Purpose: Determine if the linked list contains
    *          the passed parameter.
    *          Return:
    *              - true if linked list is not empty
    *              - false if linked list is empty
    *
    ************************************************ */
   public boolean contains( int num ) {
      LinkedList NodeRef, PreviousNode = null;
      boolean ret = false ;
      int a ;

      /** If the list is empty, do nothing.  */
      if ( !(head == null) ) {
         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.
                 **************************************** */

                ret = true ;
                System.out.println("\nThe number " + num +
                            " sought has been found.\n") ;

                /** quit while loop - node found   */
                break ;

            } /** End of inner if-then-else   */
         }  /** End of while loop   */
      }  /** End of outer if   */

      return ret ;
   }

   public static void main(String args[]) {
      boolean ret ;
      int a , b = 0 , arr[] = new int[ 100 ];

      LinkedList pp = new LinkedList() ;

      /** **************************************
       *  Determine if the linked list is empty.
       *****************************************/
      ret = pp.isEmpty() ;

      if ( ret ) {
         System.out.println("\nThe linked list is not empty.\n") ;
      }
      else {
         System.out.println("\nThe linked list is empty.\n") ;
      }

      /** **************************************
       *  Add some entries to list.
       *****************************************/
      System.out.println("\nAdding some entries to list.\n") ;
      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);

      System.out.println("\nThe last number in the linked list is " + pp.getLast() + ".\n") ;

      /** **************************************
       *  Display the linked list.
       *****************************************/
      pp.DisplayLL() ;

      /** **************************************
       *  Determine if the linked list contains
       *  the value 15. If it does remove 15.
       *****************************************/
      a = 15 ;
      ret = pp.contains( a ) ;
      if ( ret ) {
         System.out.println("\nThe linked list contains the number "
                  + a + ".\n") ;
         System.out.println("\nRemoving the number " + a + ".\n") ;
         pp.Remove( a ) ;
      }
      else {
         System.out.println("\nThe linked list does not contain the number "
                  + a + ".\n")  ;
      }

      /** **************************************
       *  Display the linked list.
       *****************************************/
      System.out.println("\nDisplaying the entries in the linked list.\n") ;
      pp.DisplayLL() ;

      /** **************************************
       *  Determine if the linked list contains
       *  the value 15. If it does remove 100.
       *****************************************/
      a = 100 ;
      ret = pp.contains( a ) ;
      if ( ret ) {
         System.out.println("\nThe linked list contains the number "
                  + a + ".\n") ;
         pp.Remove( a ) ;
      }
      else {
         System.out.println("\nThe linked list does not contain the number "
                  + a + ".\n")  ;
      }


      /** **************************************
       *  Determine the size of the linked list.
       *****************************************/
      a = pp.size() ;
      System.out.println("\nThe number of entries in the linked list is " + 
           a + ".\n") ;

      System.out.println("\nThe last number in the linked list is " + pp.getLast() + ".\n") ;

      /** **************************************
       *  Use the linked list to create an array.
       *****************************************/
      pp.toArray( arr )  ;

      /** *******************************************
       *  Print to screen the elements in the array.
       **********************************************/
      b = pp.size() ;
      System.out.println("\nThe elements in array arr are.\n") ;
      for( a = 0 ; a < b ; a++ ) {
         System.out.print(" " + arr[ a ] ) ;
      }
   }
}

  
Figure 9: Linked List Code


Our Linked List API

Methods: Description
public LinkedList() Constructs an empty list.
public LinkedList(int n, LinkedList ln) This Constructor is longer used
public void add( int num ) Inserts the specified element to this list in ascending sorted order.
void addLast( int num) Appends the given element to the end of this list.
public void addFirst( int num ) Inserts the given element at the beginning of this list.
public void DisplayLL() Displays the elements in the list to the screen
void Remove(int num) Deletes the specified element from the list.
public boolean isEmpty() Determines if the list is empty.
  • Returns true if not empty
  • Returns false if empty
public boolean contains( int num ) Determines if the specified value is in the list.
  • Returns true if the value is in the list
  • Returns false if the value is not in the list
public static void main(String args[]) This is the entry point of the application.

DBMS

inheritance

Modular programming

Object

Object Oriented Programming

requirement

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

structured program

Template

top-down





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

© 2002 - 2015 All Rights Reserved Total Application Works