LINKED LISTS

CONTENTS

1. Introduction
2. Example


1. INTRODUCTION

One of the most useful applications of records is to define organisations of data in which distinct items are linked together using a reference to another record (sometimes called pointers or access values in other languages). The simplest general form of a group of linked records is a linked list (more complex forms include trees of various types). In a linked list each record includes a reference to a following record. The final record has the value null indicating that the last record in the linked list has been reached. Figure 1 shows a linked list of date records of the form described earlier.

A LINKED LIST

Figure 1

The standard mechanism for processing linked lists is to step through the list, using some form of loop construct, until the terminating null reference is reached.



2. EXAMPLE

Table 1 shows a linked list of FamousPerson records. The code includes methods to:

An application program to interact with the code given in Table 1 is given in Table 2; some sample output is given in Table 3.

// FAMOUS PERSONS LINKED LIST EXAMPLE
// Frans Coenen
// Saturday 15 January 2000
// Depaertment of Computer Science, University of Liverpool


class FamousPerson {

/* ------------------------------- */
/*                                 */
/*              FIELDS             */
/*                                 */
/* ------------------------------- */

    private String secondName;
    private String firstName;
    private int yearOfBirth;
    private int yearOfDeath;
    private String occupation;
    private FamousPerson next = null;
    
/* ------------------------------------ */
/*                                      */
/*              CONSTRUCTORS            */
/*                                      */
/* ------------------------------------ */
  
    /* FamousPerson constructor */

    public FamousPerson(String name1, String name2, int year1, int year2,
    						String description)  {
	 secondName = name1;
	 firstName = name2;
	 yearOfBirth = year1;
	 yearOfDeath = year2;
	 occupation = description; 
	 next = null;
	 }

/* -------------------------------- */
/*                                  */
/*              METHODS             */
/*                                  */
/* -------------------------------- */

/* Output famous person linked list */

    public void outputFamousPersonLinkedList() {
	FamousPerson linkRef = this;

	// Loop through linked list till end outputting each record in turn
		
        while (linkRef != null) {
	    System.out.println(linkRef.secondName + ", " + linkRef.firstName + 
		 	" (" + linkRef.yearOfBirth + "-" + linkRef.yearOfDeath + 
			"): " + linkRef.occupation);
	    linkRef = linkRef.next;	
	    }
        }

/* Add a new record to the linked list */

    public FamousPerson addRecordToLinkedList(FamousPerson newRef) {
	FamousPerson tempRef, linkRef;

	// Test if new person is to be added to start of list if so return

        if (newRef.testRecord(this) ) {
	    newRef.next = this;
	    return(newRef);
	    }

	// Loop through remainder of linked list

	tempRef = this;
	linkRef = this.next;
	while (linkRef != null) {
	    if (newRef.testRecord(linkRef)) {
	        tempRef.next = newRef;
		newRef.next = linkRef;
		return(this);
		}
	    tempRef = linkRef;
	    linkRef = linkRef.next;
	    }

        // Add to end

        tempRef.next = newRef;
	return(this);
        }

/* Delete a record from the linked list given the first and last name. Four 
posibilities:
    1) Record to be deleted is at front of list
    2) Record to be deleted is at end of list
    3) Record to be deleted is in middle of list 
    4) Record not found. */

    public FamousPerson deleteRecord(String lName, String fName) {
        FamousPerson tempRef, linkRef;

        // Record at start of list

        if ((this.secondName == lName) & (this.firstName == fName))
 	    return(this.next);

	// Loop through linked list to discover if record is in middle of list.
	
	tempRef = this;
        linkRef = this.next;
        while (linkRef != null) {
	    if ((linkRef.secondName == lName) & (linkRef.firstName == fName)) {
                tempRef.next = linkRef.next;
                return(this);
		}
            tempRef = linkRef;
            linkRef = linkRef.next;
            }

        // Record at end of list, or not found

        if ((linkRef.secondName == lName) & (linkRef.firstName == fName))
            				linkRef = null;
	else System.out.println("Record: " + lName + " " + fName + " not found!");
	return(this);
        }

/* ------------------------------------- */
/*                                       */
/*              TEST METHODS             */
/*                                       */
/* ------------------------------------- */

/* Test whether new record comes before existing record or not. If so return 
true, false otherwise. */

    private boolean testRecord(FamousPerson existingRef) {
    	int testResult = secondName.compareTo(existingRef.secondName);
	
	if (testResult < 0) return(true);
	else {
	    if ((testResult == 0) & (firstName.compareTo(existingRef.firstName) < 0 )) 
	    				return(true);
	    }

	// Return false

	return(false);
	}

Table 1: Linked list example

// FAMOUS PERSON APPLICATION
// Frans Coenen
// Thursday 28 January 2000
// Depaertment of Computer Science, University of Liverpool

import FamousPerson;

class FamousPersonApp {

    // --------------- FIELDS ------------------

    private static FamousPerson startRef = null;
	
    // --------------- METHODS ------------------

    /* MAIN METHOD: */
                         
    public static void main(String[] args) {
	
    // Add first item 

    startRef = new FamousPerson("Monet","Claude",1840,1926,"Painter");

    // Add rest of items

    addToList("Lawrence","D.H.",1885,1930,"Author");	
    addToList("Copernicus","Nicolas",1473,1543,"Astronemer");
    addToList("Shostakovich","Dimitry",1906,1975,"Composer");
    addToList("Hill","Rowland",1795,1879,"Post man");
    addToList("Lawrence","T.E.",1888,1935,"War hero");
    addToList("Crockett","Davey",1786,1836,"Folk hero");
    addToList("Descartes","Rene",1596,1650,"Mathematician");
    
    // Output Linked List
    
    System.out.println("OUTPUT LINKED LIST BEFORE DELETING RECORD");
    startRef.outputFamousPersonLinkedList();

    // Delete element

    startRef = startRef.deleteRecord("Lawrence","T.E.");
    System.out.println("\nOUTPUT LINKED LIST AFTER DELETING RECORD"); 
    startRef.outputFamousPersonLinkedList(); 
    }

    /* ADD TO LIST */

    public static void addToList(String name1, String name2, int year1, int year2, 
    						String description) {

	// Create instance of class Famous Person
	
        FamousPerson newRef = new FamousPerson(name1,name2,year1,year2,
							description);
	
        // Add to linked list;

	startRef = startRef.addRecordToLinkedList(newRef);
        }
    }

Table 2: Linked list application program

$java FamousPersonApp
OUTPUT LINKED LIST BEFORE DELETING RECORD
Copernicus, Nicolas (1473-1543): Astronemer
Crockett, Davey (1786-1836): Folk hero
Descartes, Rene (1596-1650): Mathematician
Hill, Rowland (1795-1879): Post man
Lawrence, D.H. (1885-1930): Author
Lawrence, T.E. (1888-1935): War hero
Monet, Claude (1840-1926): Painter
Shostakovich, Dimitry (1906-1975): Composer

OUTPUT LINKED LIST AFTER DELETING RECORD
Copernicus, Nicolas (1473-1543): Astronemer
Crockett, Davey (1786-1836): Folk hero
Descartes, Rene (1596-1650): Mathematician
Hill, Rowland (1795-1879): Post man
Lawrence, D.H. (1885-1930): Author
Monet, Claude (1840-1926): Painter
Shostakovich, Dimitry (1906-1975): Composer  

Table 3: Sample output generate from the linked list example code presented in Tables 1 and 2




Created and maintained by Frans Coenen. Last updated 01 February 2000