public class LList
1: /**
2: A class that implements the ADT list by using a chain of
3: linked nodes that has a head reference.
4:
5: @author Frank M. Carrano
6: @author Timothy M. Henry
7: @version 4.0
8: */
9: public class LList<T> implements ListInterface<T>
10: {
11: private Node firstNode; // Reference to first node of chain
12: private int numberOfEntries;
13:
14: public LList()
15: {
16: initializeDataFields();
17: } // end default constructor
18:
19: public void clear()
20: {
21: initializeDataFields();
22: } // end clear
23:
24: /* < Implementations of the public methods add, remove, replace, getEntry, contains,
25: getLength, isEmpty, and toArray go here. >
26: . . . */
27:
28: // Initializes the class's data fields to indicate an empty list.
29: private void initializeDataFields()
30: {
31: firstNode = null;
32: numberOfEntries = 0;
33: } // end initializeDataFields
34: // Returns a reference to the node at a given position.
35: // Precondition: The chain is not empty;
36: // 1 <= givenPosition <= numberOfEntries.
37: private Node getNodeAt(int givenPosition)
38: {
39: assert !isEmpty() && (1 <= givenPosition) && (givenPosition <= numberOfEntries);
40: Node currentNode = firstNode;
41:
42: // Traverse the chain to locate the desired node
43: // (skipped if givenPosition is 1)
44: for (int counter = 1; counter < givenPosition; counter++)
45: currentNode = currentNode.getNextNode();
46: assert currentNode != null;
47: return currentNode;
48: } // end getNodeAt
49:
50: private class Node
51: {
52: private T data; // Entry in list
53: private Node next; // Link to next node
54:
55: private Node(T dataPortion)
56: {
57: data = dataPortion;
58: next = null;
59: } // end constructor
60:
61: private Node(T dataPortion, Node nextNode)
62: {
63: data = dataPortion;
64: next = nextNode;
65: } // end constructor
66:
67: private T getData()
68: {
69: return data;
70: } // end getData
71:
72: private void setData(T newData)
73: {
74: data = newData;
75: } // end setData
76:
77: private Node getNextNode()
78: {
79: return next;
80: } // end getNextNode
81:
82: private void setNextNode(Node nextNode)
83: {
84: next = nextNode;
85: } // end setNextNode
86: } // end Node
87: } // end LList