1，本程序实现了线性表的链式存储结构。实现的链表带有两个指针，一个始终指向链表中的第一个结点，另一个指针始终指向链表中的最后一个结点。
之所以设置尾指针，是因为，在插入元素到链表中的末尾时，可以通过尾指针直接找到链表的最后一个元素，从而不需要遍历链表就可以完成插入操作。
2，具体实现链表的类名为LList2.java，它首先实现了线性表的接口ListInterface，该接口的定义见：http://www.cnblogs.com/hapjin/p/4549492.html
LList2.java的代码 如下：
public class LList2<T> implements ListInterface<T>{ private Node firstNode;//指向第一个结点的指针，该链表是不带头结点的单链表 private Node lastNode;//尾指针，指向链表中的最后一个结点 private int length;//表示单链表的长度 //Node类中不需要定义访问属性的get方法以及set方法，因为Node是内部类，内部类的属性可以直接在外部类中被访问 class Node{ //Node是内部类，其外部类中已经定义了T，故可以在这里使用通配符T private T data;//结点的数据部分 private Node next;//结点的指针部分，指向下一个结点 //Node类中不需要默认构造器 public Node(T dataPortion){ data = dataPortion; } public Node(T dataPortion, Node nextNode){ data = dataPortion; next = nextNode; } } public LList2(){ clear(); } //获取链表中指定位置处的结点 private Node getNodeAt(int givenPosition){ assert (!isEmpty() && ((1 <= givenPosition) && (givenPosition <= length))); Node currentNode = firstNode; for(int counter = 1; counter < givenPosition; counter++){ currentNode = currentNode.next; } assert currentNode != null; return currentNode; } @Override public boolean add(T newEntry) { Node newNode = new Node(newEntry); if(isEmpty()){//插入第一个结点 firstNode = newNode; } else{//在其它位置插入结点 lastNode.next = newNode; } lastNode = newNode; length++; return true; } @Override public boolean add(int givenPosition, T newEntry){//在指定位置处插入结点 boolean isSuccessful = true; if(givenPosition >= 1 && givenPosition <= length + 1){ Node newNode = new Node(newEntry); if(isEmpty()){//表空为，插入某个元素 firstNode = newNode; lastNode = newNode; } else if(givenPosition == 1){//表不空时，在第一个位置处插入元素 newNode.next = firstNode; firstNode = newNode; } else if(givenPosition == length + 1){//表不空时，在最后一个位置处插入元素 lastNode.next = newNode; lastNode = newNode; } else{//在其它位置插入结点 Node nodeBefore = getNodeAt(givenPosition - 1); Node nodeAfter = nodeBefore.next; nodeBefore.next = newNode; newNode.next = nodeAfter; } length++; } else isSuccessful = false; return isSuccessful; } @Override public final void clear() {//clear()在构造器中被调用了，所以此外用final修饰符 firstNode = null; lastNode = null; length = 0; } @Override public T remove(int givenPosition) {//删除指定位置处的结点 T result = null; if((!isEmpty()) && ((givenPosition >= 1) && (givenPosition <= length))){ if(givenPosition == 1){//删除第一个位置处的结点 result = firstNode.data; firstNode = firstNode.next; if(length == 1)//链表中只有一个元素时，删除之后，尾指针为空 lastNode = null; } else//删除表中其它位置结点 { Node nodeBefore = getNodeAt(givenPosition - 1); Node nodeToRemove = nodeBefore.next; Node nodeAfter = nodeToRemove.next; nodeBefore.next = nodeAfter; result = nodeToRemove.data; if(givenPosition == length)//当删除最后一个元素后，尾指针应指向其前一个元素 lastNode = nodeBefore; } length--; } return result; } @Override public boolean replace(int givenPosition, T newEntry) {//替换指定位置处结点的值 boolean isSuccessful = true; if((!isEmpty()) && ((givenPosition >= 1) && (givenPosition <= length))){ Node desireNode = getNodeAt(givenPosition); desireNode.data = newEntry; } else isSuccessful = false; return isSuccessful; } @Override public T getEntry(int givenPosition) {//获取指定位置的结点的值 T result = null; if((!isEmpty()) && ((givenPosition >= 1) && (givenPosition <= length))){ result = getNodeAt(givenPosition).data; } return result; } @Override public boolean contains(T anEntry) {//判断链表中的结点是否包含某个值 boolean found = false; Node currentNode = firstNode; while(!found && currentNode != null){ if(currentNode.data.equals(anEntry)){ found = true; break; } currentNode = currentNode.next; } return found; } @Override public int getLength() {//获取链表的长度 return length; } @Override public boolean isEmpty() {//判断链表是否为空 boolean result; if(length == 0){ assert firstNode == null; result = true; } else{ assert firstNode != null; result = false; } return result; } @Override public void display() {//遍历链表，显示链表中的每个结点的值 Node currentNode = firstNode; while(currentNode != null){ System.out.println(currentNode.data); currentNode = currentNode.next; } } }