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

本程式采用JAVA語言實作了線性表的鍊式實作。首先定義了線性表的接口ListInterface，然後LList類實作了ListInterface完成了連結清單的實作。

本實作中，連結清單是不帶表頭結點的，且有一個指針始終指向連結清單中的第一個元素，并沒有定義尾指針。是以，每次向連結清單中插入新結點時需要周遊連結清單一次。

更詳細的解釋參考《資料結構與算法分析 JAVA語言描述第二版》Frank M. Carrano 著

ListInterface接口的定義如下：

public interface ListInterface<T> {
    public boolean add(T newEntry);
    public boolean add(int givenPosition, T newEntry);
    public void clear();
    public T remove(int givenPosition);
    public boolean replace(int givenPosition, T newEntry);
    public T getEntry(int givenPosition);
    public boolean contains(T anEntry);
    public int getLength();
    public boolean isEmpty();
    public void display();
}      

具體的實作類LList定義如下：

public class LList<T> implements ListInterface<T>{

    private Node firstNode;//指向第一個結點的指針，該連結清單是不帶頭結點的單連結清單
    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 LList(){
        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) {
        // 将每個新結點插入到連結清單的末尾，通過getNodeAt()方法來獲得最後一個元素的位址
        Node newNode = new Node(newEntry);
        if(isEmpty()){//插入第一個結點
            firstNode = newNode;
        }
        else{//在其它位置插入結點
            Node lastNode = getNodeAt(length);//這裡每插入一個元素都需要周遊一次連結清單，代價較大
            lastNode.next = 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() || givenPosition == 1){//在第一個位置處插入結點
                newNode.next = firstNode;
                firstNode = 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;
        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;
            }
            else//删除表中其它位置結點
            {
                Node nodeBefore = getNodeAt(givenPosition - 1);
                Node nodeToRemove = nodeBefore.next;
                Node nodeAfter = nodeToRemove.next;
                nodeBefore.next = nodeAfter;
                result = nodeToRemove.data;
            }
            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;
        }
    }
}