第一章單向鏈表介紹
第二章單向鏈表實作
- 2.01、定義鏈表的結點類
- 2.02、定義鏈表的屬性值
- 2.03、初始化各個屬性值
- 2.04、獲取鏈表當前大小
- 2.05、判斷鏈表是否為空
- 2.06、檢查下標是否合法
- 2.07、連接鏈表兩個結點
- 2.08、釋放鏈表指定結點
- 2.09、回傳鏈表最后結點
- 2.10、回傳鏈表首個結點
- 2.11、獲取指定位置結點
- 2.12、獲取位置之前結點
- 2.13、鏈表尾后添加資料
- 2.14、鏈表頭后添加資料
- 2.15、指定位置添加資料
- 2.16、洗掉指定位置結點
- 2.17、洗掉鏈表首個結點
- 2.18、洗掉鏈表最后結點
- 2.19、輸出鏈表所有結點
- 2.20、反轉鏈表所有結點
- 2.21、清空鏈表所有結點
- 2.22、順序查找資料首次出現位置
- 2.23、逆序查找資料首次出現位置
第三章雙向鏈表介紹
第四章雙向鏈表實作
- 4.01、且看代碼如此多嬌
- 4.02、獲取位置之前結點
- 4.03、洗掉鏈表最后結點
- 4.04、逆序查找資料首次出現位置

專案地址：https://gitee.com/caochenlei/data-structures

第一章單向鏈表介紹

鏈表是一種物理存盤單元上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標連接次序實作的，鏈表由一系列結點組成，結點可以在運行時動態生成，每個結點包括兩個部分：一個是存盤資料元素的資料域，另一個是存盤下一個結點地址的指標域，

單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的連接方向是單向的，對鏈表的訪問要從頭部開始順序讀取，head指標指向第一個結點又稱為頭結點，而終止于最后一個指向null的結點，鏈表的頭結點的資料域不存盤資料，而頭結點的指標域指向第一個真正存盤資料的結點，這里為了方便操作，我又增加了一個last結點，這個結點就是為了指向最后一個結點，節約操作時間，提升查詢性能，

第二章單向鏈表實作

2.01、定義鏈表的結點類

/**
 * 單向鏈表實作代碼
 */
public class SinglyLinkedList<E> {
    //定義結點類
    public class Node {
        E data;     //代表結點資料
        Node next;  //指向下個結點

        public Node(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return "Node{data=" + data + "}";
        }
    }

    //下節內容寫這...
}

2.02、定義鏈表的屬性值

/**
 * 單向鏈表實作代碼
 */
public class SinglyLinkedList<E> {
    //省略以上代碼...

    private Node head;  //代表鏈表頭部
    private Node last;  //代表鏈表尾部
    private int size;   //代表鏈表長度

    //下節內容寫這...
}

2.03、初始化各個屬性值

/**
 * 單向鏈表實作代碼
 */
public class SinglyLinkedList<E> {
    //省略以上代碼...

    public SinglyLinkedList() {
        //頭結點用于其他結點的連接，頭結點的下標我們定義為-1
        this.head = new Node(null);
        //尾結點初始默認指向頭結點，這樣我們在添加的時候方便
        this.last = head;
        this.size = 0;
    }

    //下節內容寫這...
}

2.04、獲取鏈表當前大小

//獲取鏈表當前大小
public int size() {
    return size;
}

2.05、判斷鏈表是否為空

//判斷鏈表是否為空
public boolean isEmpty() {
    return size == 0;
}

2.06、檢查下標是否合法

//檢查下標是否合法
public void checkIndex(int index) {
    if (index < 0 || (size - 1) < index) {
        throw new IndexOutOfBoundsException("鏈表下標越界例外，請檢查鏈表的下標！");
    }
}

2.07、連接鏈表兩個結點

//連接鏈表兩個結點
public void connectNode(Node prevNode, Node nextNode) {
    if (prevNode != null) {
        prevNode.next = nextNode;
    }
}

2.08、釋放鏈表指定結點

//釋放鏈表指定結點
public void releaseNode(Node node) {
    if (node != null) {
        node.data = null;
        node.next = null;
    }
}

2.09、回傳鏈表最后結點

//回傳鏈表最后結點
public Node getLast() {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return null;
    }
    //回傳鏈表最后結點
    return last;
}

2.10、回傳鏈表首個結點

//回傳鏈表首個結點
public Node getFirst() {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return null;
    }
    //回傳鏈表首個結點
    return head.next;
}

2.11、獲取指定位置結點

//獲取指定位置結點
public Node getIndex(int index) {
    //檢查下標是否合法
    checkIndex(index);
    //獲取指定位置結點
    Node curNode = head;
    for (int i = 0; i < (index + 1); i++) {
        curNode = curNode.next;
    }
    //回傳指定位置結點
    return curNode;
}

2.12、獲取位置之前結點

//獲取位置之前結點
private Node getIndexPre(int index) {
    //檢查下標是否合法
    checkIndex(index);
    //獲取位置之前結點
    Node preNode = head;
    for (int i = 0; i < index; i++) {
        preNode = preNode.next;
    }
    //回傳位置之前結點
    return preNode;
}

2.13、鏈表尾后添加資料

默認為空的時候，頭指標head和尾指標last均指向頭結點，

添加資料的時候，我們直接向last指向結點后追加結點即可，

方法實作：

//鏈表尾后添加資料（需要考慮last指向問題）
public void addLast(E e) {
    //獲取舊的尾結點
    Node oldLast = last;
    //創建新的尾結點
    Node newLast = new Node(e);
    //舊新兩結點連接
    connectNode(oldLast, newLast);
    //修改last指向
    last = newLast;
    //使鏈表長度加一
    size++;
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.getIndex(i));
        }
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：3
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=張三}
Node{data=李四}
Node{data=王五}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=張三}
鏈表的尾結點：Node{data=王五}

2.14、鏈表頭后添加資料

方法實作：

//鏈表頭后添加資料（不用考慮last指向問題）
public void addFirst(E e) {
    //判斷鏈表是否為空
    if (isEmpty()) {
        addLast(e);
    } else {
        //獲取首個結點
        Node firNode = head.next;
        //創建新的結點
        Node newNode = new Node(e);
        //三個結點連接
        connectNode(head, newNode);
        connectNode(newNode, firNode);
        //鏈表長度加一
        size++;
    }
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addFirst("張三");
        linkedList.addFirst("李四");
        linkedList.addFirst("王五");

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.getIndex(i));
        }
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：3
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=王五}
Node{data=李四}
Node{data=張三}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=王五}
鏈表的尾結點：Node{data=張三}

2.15、指定位置添加資料

方法實作：

//指定位置添加資料（不用考慮last指向問題）
public void addIndex(int index, E e) {
    //獲取位置之前結點
    Node preNode = getIndexPre(index);
    //獲取指定位置結點
    Node curNode = preNode.next;
    //創建一個新的結點
    Node newNode = new Node(e);
    //開始三個結點連接
    connectNode(preNode, newNode);
    connectNode(newNode, curNode);
    //當前鏈表長度加一
    size++;
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        linkedList.addIndex(0, "張三長輩");
        linkedList.addIndex(linkedList.size() - 1, "王五長輩");

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.getIndex(i));
        }
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：5
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=張三長輩}
Node{data=張三}
Node{data=李四}
Node{data=王五長輩}
Node{data=王五}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=張三長輩}
鏈表的尾結點：Node{data=王五}

2.16、洗掉指定位置結點

方法實作：

//洗掉指定位置結點（需要考慮last指向問題）
public void removeIndex(int index) {
    //獲取位置之前結點
    Node preNode = getIndexPre(index);
    //獲取指定位置結點
    Node curNode = preNode.next;
    //獲取位置之后結點
    Node nexNode = curNode.next;
    //修改last的指向
    if (curNode == last) {
        last = preNode;
    }
    //洗掉指定位置結點
    connectNode(preNode, nexNode);
    //釋放鏈表指定結點
    releaseNode(curNode);
    //當前鏈表長度減一
    size--;
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        linkedList.removeIndex(0);
        linkedList.removeIndex(linkedList.size() - 1);

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.getIndex(i));
        }
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：1
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=李四}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=李四}
鏈表的尾結點：Node{data=李四}

2.17、洗掉鏈表首個結點

方法實作：

//洗掉鏈表首個結點（不用考慮last指向問題）
public void removeFirst() {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return;
    }
    //洗掉鏈表首個結點
    removeIndex(0);
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        linkedList.removeFirst();

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.getIndex(i));
        }
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：2
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=李四}
Node{data=王五}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=李四}
鏈表的尾結點：Node{data=王五}

2.18、洗掉鏈表最后結點

方法實作：

//洗掉鏈表最后結點（不用考慮last指向問題）
public void removeLast() {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return;
    }
    //洗掉鏈表最后結點
    removeIndex(size - 1);
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        linkedList.removeLast();

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        for (int i = 0; i < linkedList.size(); i++) {
            System.out.println(linkedList.getIndex(i));
        }
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：2
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=張三}
Node{data=李四}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=張三}
鏈表的尾結點：Node{data=李四}

2.19、輸出鏈表所有結點

方法實作：

//輸出鏈表所有結點（不用考慮last指向問題）
public void show() {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return;
    }
    //遍歷鏈表所有結點（除頭結點）
    Node curNode = head.next;
    while (curNode != null) {
        System.out.println(curNode);
        curNode = curNode.next;
    }
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        linkedList.show();
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：3
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=張三}
Node{data=李四}
Node{data=王五}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=張三}
鏈表的尾結點：Node{data=王五}

2.20、反轉鏈表所有結點

方法實作：

//反轉鏈表所有結點（需要考慮last指向問題）
public void reverse() {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return;
    }
    //創建一個新頭結點
    Node newHead = new Node(null);
    //獲取鏈表的首結點
    Node oldFirst = head.next;
    //遍歷鏈表所有結點（除頭結點）
    Node newFirst;
    Node tmpNode;
    Node curNode = oldFirst;
    while (curNode != null) {
        //快取當前結點下個結點
        tmpNode = curNode.next;
        //獲取鏈表新頭首個結點
        newFirst = newHead.next;
        //開始三個結點進行關聯
        connectNode(newHead, curNode);
        connectNode(curNode, newFirst);
        //讓當前的結點往后移動
        curNode = tmpNode;
    }
    //老頭換新頭首結點
    head.next = newHead.next;
    //修改last的指向
    last = oldFirst;
    //釋放臨時新頭結點
    releaseNode(newHead);
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        linkedList.reverse();

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        linkedList.show();
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：3
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=王五}
Node{data=李四}
Node{data=張三}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=王五}
鏈表的尾結點：Node{data=張三}

2.21、清空鏈表所有結點

方法實作：

//清空鏈表所有結點（需要考慮last指向問題）
public void clear() {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return;
    }
    //重置鏈表基本資訊
    head = null;
    last = null;
    size = 0;
    //遍歷鏈表所有結點（含頭結點）
    Node tmpNode;
    Node curNode = head;
    while (curNode != null) {
        //快取下個結點
        tmpNode = curNode.next;
        //釋放當前結點
        releaseNode(curNode);
        //移動下個結點
        curNode = tmpNode;
    }
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        linkedList.clear();

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        linkedList.show();
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

==========列印鏈表基本資訊：
鏈表結點個數：0
鏈表是否為空：true
==========列印鏈表所有結點：
==========列印鏈表首尾結點：
鏈表的頭結點：null
鏈表的尾結點：null

2.22、順序查找資料首次出現位置

方法實作：

//順序查找資料首次出現位置
public int indexOf(E e) {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return -1;
    }
    //判斷物件是否為空
    if (e == null) {
        return -1;
    }
    //獲取指定位置結點
    Node curNode = head;
    for (int i = -1; curNode != null; i++) {
        if (e.equals(curNode.data)) {
            return i;
        }
        curNode = curNode.next;
    }
    //沒有找到回傳負一
    return -1;
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        System.out.println(linkedList.indexOf("張三"));
        System.out.println(linkedList.indexOf("李四"));
        System.out.println(linkedList.indexOf("王五"));

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        linkedList.show();
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

0
1
2
==========列印鏈表基本資訊：
鏈表結點個數：3
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=張三}
Node{data=李四}
Node{data=王五}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=張三}
鏈表的尾結點：Node{data=王五}

2.23、逆序查找資料首次出現位置

方法實作：

//逆序查找資料首次出現位置
public int lastIndexOf(E e) {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return -1;
    }
    //判斷物件是否為空
    if (e == null) {
        return -1;
    }
    //反轉當前鏈表結點
    reverse();
    //獲取指定位置結點
    int index = indexOf(e);
    //反轉當前鏈表結點
    reverse();
    //回傳資料指定位置
    return index;
}

方法測驗：

public class SinglyLinkedListTest {
    public static void main(String[] args) {
        SinglyLinkedList<String> linkedList = new SinglyLinkedList<>();

        linkedList.addLast("張三");
        linkedList.addLast("李四");
        linkedList.addLast("王五");

        System.out.println(linkedList.lastIndexOf("張三"));
        System.out.println(linkedList.lastIndexOf("李四"));
        System.out.println(linkedList.lastIndexOf("王五"));

        System.out.println("==========列印鏈表基本資訊：");
        System.out.println("鏈表結點個數：" + linkedList.size());
        System.out.println("鏈表是否為空：" + linkedList.isEmpty());
        System.out.println("==========列印鏈表所有結點：");
        linkedList.show();
        System.out.println("==========列印鏈表首尾結點：");
        System.out.println("鏈表的頭結點：" + linkedList.getFirst());
        System.out.println("鏈表的尾結點：" + linkedList.getLast());
    }
}

運行結果：

2
1
0
==========列印鏈表基本資訊：
鏈表結點個數：3
鏈表是否為空：false
==========列印鏈表所有結點：
Node{data=張三}
Node{data=李四}
Node{data=王五}
==========列印鏈表首尾結點：
鏈表的頭結點：Node{data=張三}
鏈表的尾結點：Node{data=王五}

第三章雙向鏈表介紹

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個資料結點中都有兩個指標，分別指向直接后繼和直接前驅，所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點，鏈表的頭結點的資料域不存盤資料，指向前驅結點的指標域值為null，指向后繼結點的指標域指向第一個真正存盤資料結點，

第四章雙向鏈表實作

4.01、且看代碼如此多嬌

我們已經學過了單向鏈表的設計和實作了，雙向鏈表只需要在單向鏈表的基礎上添加三行代碼就能實作，你看神奇不神奇，

我們需要直接拷貝SinglyLinkedList為DoublyLinkedList，然后拷貝SinglyLinkedListTest為DoublyLinkedListTest，并修改相對應的構造方法名稱，

第一處：修改節點類，添加prev指標域，

//定義結點類
public class Node {
    Node prev;  //指向上個結點 +
    E data;     //代表結點資料
    Node next;  //指向下個結點

    public Node(E data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{data=" + data + "}";
    }
}

第二處：修改連接處，添加指向上個結點，

//連接鏈表兩個結點
public void connectNode(Node prevNode, Node nextNode) {
    if (prevNode != null) {
        prevNode.next = nextNode;
    }
    if (nextNode != null) {         // +
        nextNode.prev = prevNode;   // +
    }                               // +
}

第三處：修改釋放處，添加釋放prev指標域，

//釋放鏈表指定結點
public void releaseNode(Node node) {
    if (node != null) {
        node.prev = null;   // +
        node.data = null;
        node.next = null;
    }
}

到此，雙向鏈表的設計和實作就學完了，但是既然存在雙向鏈表，那么肯定還有一些方法可以簡化，接下來，我們需要對一些特殊的方法進行優化，

4.02、獲取位置之前結點

//獲取位置之前結點
private Node getIndexPre(int index) {
    return getIndex(index).prev;
}

4.03、洗掉鏈表最后結點

//洗掉鏈表最后結點（需要考慮last指向問題）
public void removeLast() {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return;
    }
    //獲取鏈表最后節點
    Node lastNode = last;
    //洗掉鏈表最后結點
    Node prevNode = lastNode.prev;
    prevNode.next = null;
    //釋放最后節點指向
    releaseNode(lastNode);
    //修改last的指向
    last = prevNode;
    //讓鏈表的長度減一
    size--;
}

4.04、逆序查找資料首次出現位置

//逆序查找資料首次出現位置
public int lastIndexOf(E e) {
    //判斷鏈表是否為空
    if (isEmpty()) {
        return -1;
    }
    //判斷物件是否為空
    if (e == null) {
        return -1;
    }
    //獲取指定位置結點
    Node curNode = last;
    for (int i = 0; curNode != null; i++) {
        if (e.equals(curNode.data)) {
            return i;
        }
        curNode = curNode.prev;
    }
    //沒有找到回傳負一
    return -1;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/267169.html

標籤：其他

上一篇：開發者們看過來，8ms開發工具平臺給大家送福利了！只要你來，肯定有你感興趣的，3.6-3.10日，只要在8ms平臺上創建專案，就有機會白嫖彩屏開發板哦

下一篇：leetcode453. 最小操作次數使陣列元素相等（賊難的簡單題）

線性結構：鏈表

目錄

第一章單向鏈表介紹

第二章單向鏈表實作

2.01、定義鏈表的結點類

2.02、定義鏈表的屬性值

2.03、初始化各個屬性值

2.04、獲取鏈表當前大小

2.05、判斷鏈表是否為空

2.06、檢查下標是否合法

2.07、連接鏈表兩個結點

2.08、釋放鏈表指定結點

2.09、回傳鏈表最后結點

2.10、回傳鏈表首個結點

2.11、獲取指定位置結點

2.12、獲取位置之前結點

2.13、鏈表尾后添加資料

2.14、鏈表頭后添加資料

2.15、指定位置添加資料

2.16、洗掉指定位置結點

2.17、洗掉鏈表首個結點

2.18、洗掉鏈表最后結點

2.19、輸出鏈表所有結點

2.20、反轉鏈表所有結點

2.21、清空鏈表所有結點

2.22、順序查找資料首次出現位置

2.23、逆序查找資料首次出現位置

第三章雙向鏈表介紹

第四章雙向鏈表實作

4.01、且看代碼如此多嬌

4.02、獲取位置之前結點

4.03、洗掉鏈表最后結點

4.04、逆序查找資料首次出現位置

線性結構：鏈表

目錄

第一章 單向鏈表介紹

第二章 單向鏈表實作

2.01、定義鏈表的結點類

2.02、定義鏈表的屬性值

2.03、初始化各個屬性值

2.04、獲取鏈表當前大小

2.05、判斷鏈表是否為空

2.06、檢查下標是否合法

2.07、連接鏈表兩個結點

2.08、釋放鏈表指定結點

2.09、回傳鏈表最后結點

2.10、回傳鏈表首個結點

2.11、獲取指定位置結點

2.12、獲取位置之前結點

2.13、鏈表尾后添加資料

2.14、鏈表頭后添加資料

2.15、指定位置添加資料

2.16、洗掉指定位置結點

2.17、洗掉鏈表首個結點

2.18、洗掉鏈表最后結點

2.19、輸出鏈表所有結點

2.20、反轉鏈表所有結點

2.21、清空鏈表所有結點

2.22、順序查找資料首次出現位置

2.23、逆序查找資料首次出現位置

第三章 雙向鏈表介紹

第四章 雙向鏈表實作

4.01、且看代碼如此多嬌

4.02、獲取位置之前結點

4.03、洗掉鏈表最后結點

4.04、逆序查找資料首次出現位置

第一章單向鏈表介紹

第二章單向鏈表實作

第三章雙向鏈表介紹

第四章雙向鏈表實作