目标：
1） 描述数据的链式组织方式
2） 描述如何在链式节点链的开头添加新节点
3） 描述如何删除链式节点链的首节点
4） 描述如何在链式节点链中找到某个数据
5） 使用链式节点链实现ADT包
6） 描述基于数组实现和链式实现的ADT包的不同
3. 使用链式数据实现包
3.1链式数据
添加到开头形成一个链
3.2 ADT包的链式实现
3.2.1 私有类Node
节点（node），data域：数据部分（data portion），next域：链接部分（link portion）
Node是ADT包的实现细节，应该对包的客户隐藏。一种方法是定义在包中，且含在实现包的类中。
private class Node{
private T data; // Entry in bag
private Node next; // Link to next node
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor
private Node(T dataPortion, Node nextNode) {
data = dataPortion;
next = nextNode;
} // end constructor
} // end Node
3.2.2 类LinkedBag的框架
头引用（head reference）的数据域来保存指向第一个节点的引用，第二个数据域可以记录包中项的个数，即链中节点的个数。
/**
* A class of bags whose entries are stored in a chain of linked nodes.
* The bag is never full
* @author Administrator
*
* @param <T>
*/
public class LinkedBag<T> implements BagInterface<T> {
private Node firstNode; // Reference to first node
private int numberOfEntries; public LinkedBag() {
firstNode = null;
numberOfEntries = 0;
} // end default constructor @Override
public int getCurrentSize() {
// TODO Auto-generated method stub
return 0;
} @Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
} @Override
public boolean add(Object newEntry) {
// TODO Auto-generated method stub
return false;
} @Override
public Object remove() {
// TODO Auto-generated method stub
return null;
} @Override
public boolean remove(Object anEntry) {
// TODO Auto-generated method stub
return false;
} @Override
public void clear() {
// TODO Auto-generated method stub
} @Override
public int getFrequencyOf(Object anEntry) {
// TODO Auto-generated method stub
return 0;
} @Override
public boolean contains(Object anEntry) {
// TODO Auto-generated method stub
return false;
} @Override
public Object[] toArray() {
// TODO Auto-generated method stub
return null;
} private class Node{
private T data; // Entry in bag
private Node next; // Link to next node
private Node(T dataPortion) {
this(dataPortion, null);
} // end constructor private Node(T dataPortion, Node nextNode) {
data = dataPortion;
next = nextNode;
} // end constructor
} // end Node
}
注意：没有定义initialized变量表示初始化状态。
3.2.3 定义一些核心方法
方法add：
/**
* Adds a new entry to this bag.
* @param newEntry: The object to be added as a new entry.
* @return: True if the addition is successful, or false if not.
*/
@Override
public boolean add(T newEntry) { // OutOfMemoryError posiible
Node newNode = new Node(newEntry);
newNode.next = firstNode; // Make new node reference test of chain
// (firstNode is null if chain is empty)
firstNode = newNode; // New node is at beginning of chain
numberOfEntries++;
return true;
} // end add
安全说明：内层类Node应该执行安全检查吗？
因为Node是私有内层类，所以将它看做外层类LinkedBag的实现细节。因此，让LinkedBag负责所有的安全检查。另外，注意Node的构造方法只做了简单的赋值，并没有抛出异常，即使不是这种情况，Node抛出了异常，LinkedBag也应该能处理它。
安全说明：类LinkedBag应该执行安全检查吗？
默认构造方法只进行了两个简单的赋值。实际上，所赋的值与省略构造方法时使用默认的赋值是一样的值。这些赋值不会失败。add分配新的节点，如果没有足够的内存空间，这个分配可能会失败，OutOfMemoryError，链完好无损且保持不变。或者是空的或者含有之前的节点。若客户捕获这个异常并处理，这样操作属于恰当。因为任何LinkedBag对象的完整性已经得到维护，所以不需要为类ArrayBag添加的那些安全检查。
方法toArray:
/**
* Retrieves all entries that are in this bag.
* @return: A newly allocated array of all the entries in the bag.
* Note: If the bag is empty, the returned array is empty.
*/
@Override
public T[] toArray() {
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[])new Object[numberOfEntries]; // Unchecked cast
int index = 0;
Node currentNode = firstNode;
while((index < numberOfEntries) && (currentNode != null)) {
result[index] = currentNode.data;
index++;
currentNode = currentNode.next;
} // end while
return result;
} // end toArray
3.2.4 测试核心方法
/**
* A test of the methods add, toArray, isEmpty, and getCurrentSize,
* as defined in the first draft of the class LinkedBag
* @author Administrator
*
*/
public class LinkedBagDemo1 { public static void main(String[] args) {
System.out.println("Creating an empty bag:");
BagInterface<String> aBag = new LinkedBag<>();
testIsEmpty(aBag, true);
displayBag(aBag); String[] contentOfBag = {"A", "D", "B", "A", "C", "A", "D"};
testAdd(aBag, contentOfBag);
testIsEmpty(aBag, false);
} public static void testAdd(BagInterface<String> bag, String[] content) {
System.out.println("Testing the add method:");
for (int index = 0; index < content.length; index++) {
if(bag.add(content[index])) {
System.out.print(content[index] + " ");
} // end if
} // end for
System.out.println();
displayBag(bag);
} // end testAdd private static void displayBag(BagInterface<String> bag) {
System.out.println("the bag contains " + bag.getCurrentSize() +
" string(s), as follows:");
Object[] bagArray = bag.toArray();
for (int index = 0; index < bagArray.length; index++) {
System.out.print(bagArray[index] + " ");
} // end for
System.out.println();
} // end displayBag private static void testIsEmpty(BagInterface<String> aBag, boolean correctResult) {
System.out.println("Testing isEmpty with ");
if(correctResult) {
System.out.println("an empty bag:");
}
else {
System.out.println("a bag that is not empty:");
} // end if System.out.print("isEmpty finds the bag ");
if(correctResult && aBag.isEmpty()) {
System.out.println("empty: OK.");
}
else if(correctResult) {
System.out.println("not empty, but it is empty: ERROR.");
}
else if(!correctResult && aBag.isEmpty()) {
System.out.println("empty, but it is not empty: ERROR.");
}
else {
System.out.println("not empty: OK.");
} // if else System.out.println();
} // end testIsEmpty
}
3.2.5 方法getFrequencyOf
/**
* Counts the number of times a given entry appears in this bag.
* @param anEntry: The entry to counted.
* @return: The number of times anEntry appears in the bag.
*/
@Override
public int getFrequencyOf(T anEntry) {
Node currentNode = firstNode;
int counter = 0;
int loopCounter = 0;
while((loopCounter < numberOfEntries) && (currentNode != null)) {
if(currentNode.data.equals(anEntry)) {
counter++;
} // end if
loopCounter++;
currentNode = currentNode.next;
} // end while
return counter;
} // end getFrequencyOf
3.2.6 方法contains
/**
* Tests whether this bag contains a given entry.
* @param anEntry: The entry to locate.
* @return: True if the bag contains anEntry, or false if not.
*/
@Override
public boolean contains(T anEntry) {
Node currentNode = firstNode;
boolean found = false;
while(!found && (currentNode != null)) {
if(currentNode.data.equals(anEntry)) {
found = true;
break;
}
else {
currentNode = currentNode.next;
} // end if
} // end while
return false;
} // end contains
3.3 从链中删除一项
删除未指定项：remove()
/**
* Removes one unspecified entry from this bag, if possible.
* @return: Either the removed entry, if the removel was successful, or null.
*/
@Override
public T remove() {
T result = null;
if(firstNode != null) {
result = firstNode.data;
firstNode = firstNode.next;
numberOfEntries--;
} // end if
return result;
} // end remove
删除指定项：remove(T)
删除思想与Array相同，用首节点的值将其替换，然后firstNode=firstNode.next。
/**
* Removes one occurrence of a given entry from this bag, if possible.
* @param anEntry: The entry to be removed.
* @return: True if the removal was successful, or false if not.
*/
@Override
public boolean remove(T anEntry) {
boolean result = false;
Node nodeN = getReferenceTo(anEntry);
if(nodeN != null) {
nodeN.data = firstNode.data;
firstNode = firstNode.next;
numberOfEntries--;
result = true;
} // end if
return result;
} // end remove // Locates a given entry within this bag.
// Returns a reference to the node containing the entry, if located,
// or null otherwise.
private Node getReferenceTo(T anEntry) {
Node currentNode = firstNode;
while(currentNode != null) {
if(currentNode.data.equals(anEntry)) {
break;
} // end if
currentNode = currentNode.next;
} // end while
return currentNode;
} // end getReferenceTo
方法clear：
/**
* Removes all entries from this bag.
*/
@Override
public void clear() {
while(!isEmpty()) {
remove();
} // end while
} // end clear
设计决策：LinkedBag应该限制包的容量吗？
LinkedBag每次增加一个节点，如果添加失败，则现有的链保持不变。若希望在有限的内存状态下使用LinkedBag，仍可以限制LinkedBag的容量。
3.4 使用链实现ADT包的优缺点
最大的优点是链可以按需求来改变大小，所以包也是如此。只要内存可用，可以在链中添加想要的任意多的节点。可以删除并回收不再需要的节点。（数组需要更大的数组且需要复制）。添加新项到数组尾货链头都简单（除过数组调大小），删除一项也都简单，指定项都需要查找。对于相同的长度，链比数组需要更大的内存。但是数组常比所需大，也有内存浪费，链按需使用。