03-java實現循環鏈表

• 2020 年 8 月 8 日
• 筆記
• 數據結構

03java實現循環鏈表

本人git //github.com/bigeyes-debug/Algorithm

一丶單向循環鏈表

• 就是為尾節點指向頭結點

二丶單向循環鏈表的介面設計

• 比較單向鏈表,單向循環鏈表只需要修改添加節點,刪除節點兩個方法,也就是add和remove方法

三丶單向循環鏈表的實現

3.1添加節點

• 相比於單向鏈表,單向循環鏈表只需要特別關注插入頭結點的情況即可
• 需要考慮的特殊情況是當鏈表的長度為0的時候的插入的情況
  

public void add(int index, E element) {
    rangeCheckForAdd(index);
		
    if (index == 0) {
        Node<E> newFirst = new Node<>(element, first);
        // 拿到最後一個節點
        Node<E> last = (size == 0) ? newFirst : node(size - 1);
        last.next = newFirst;
        first = newFirst;
    } else {
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}

3.2刪除節點

• 如果刪除的是頭節點，刪除後需讓last指向新的頭節點。
• 當只有一個節點並刪除時, first指向null。

public E remove(int index) {
    rangeCheck(index);
		
    Node<E> node = first;
        //刪除頭節點
        if (index == 0) {
            // 只有一個節點
            if (size == 1) {
                first = null;
            } else {
                Node<E> last = node(size - 1);
                first = first.next;
                last.next = first;
            }
        } else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }

四、雙向循環鏈表

五、雙向循環鏈表介面設計

• 相較於雙向鏈表，雙向循環鏈表需要重寫插入節點、刪除節點兩個方法。

六丶雙向循環鏈表接的實現

6.1插入節點

• 需特殊處理添加第一個元素和添加到尾節點兩種特殊情況。

public void add(int index, E element) {
    rangeCheckForAdd(index);
    // 如果 index == size, 說明添加的索引是最後位置
    if (index == size) {
    	// 創建新節點, prev指向原鏈表的尾節點, next指向首節點
    	Node<E> node = new Node<>(last, element, first);
    	// 當原鏈表沒有任何節點
    	if (size == 0) {
            first = node;
            last = node;
            node.prev = node;
            node.next = node;
        }else {
            // 原鏈表尾節點next指向node
            last.next = node;
            // 原鏈表頭結點prev指向node
            first.prev = node;
            // last指向新的尾節點
            last = node;
        }
    }else {
        // 添加新節點後的下一個節點
        Node<E> next = node(index);
        // 添加新節點後的上一個節點
        Node<E> prev = next.prev;
        // 創建新節點, 新節點的上一個節點時prev, 新節點的下一個節點是next
        Node<E> node = new Node<>(prev, element, next);
        // next的上一個節點是新節點
        next.prev = node;
        // prev的下一個節點是新節點
        prev.next = node;
        // 當next == first時, 說明新添加節點的索引是0
        if (next == first) { 
        	first = node;
        }
    }
    size++;
}

6.2刪除節點

• 刪除節點，就是在環上去掉某一個節點，然後根據刪除的節點是首節點或者尾節點來處理first和last。
• 需要特殊處理只有一個節點的刪除操作。

public E remove(int index) {
    // 需要刪除的節點
    Node<E> node = node(index);	
    if (size == 1) {
        first = null;
        last = null;
    }else {
        // 刪除節點的前一個節點
        Node<E> prev = node.prev;
        // 刪除節點的後一個節點
        Node<E> next = node.next;
        next.prev = prev;
        prev.next = next;
        // 如果node == first, 說明刪除的是第一個節點
        if (node == first) {
            first = next;
        }
        // 如果next == last, 說明刪除的是最後一個節點
        if (next == last) {
            last = prev;
        }	
    }
    size--;
    return node.element;
}