JAVA單連結清單的實作-不帶頭結點但帶有尾指針

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;
        }
    }
}