Figure 1
|
| 1. Introduction | |
| 2. Example |
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.
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.
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