引出

---

1.linkedList的節(jié)點，當前，上一個，下一個的思想；
2.根據(jù)index找node的方法，根據(jù)index確定從頭部還是尾部；
3.linkedlist的增刪改查的實現(xiàn)，本質是改變節(jié)點的信息；
4.遞歸方法實現(xiàn)自定義鏈表的toString方法；

從ArrayList到Linkedlist

手動實現(xiàn)ArrayList

Java進階（3）——手動實現(xiàn)ArrayList & 源碼的初步理解分析 & 數(shù)組插入數(shù)據(jù)和刪除數(shù)據(jù)的問題

從ArrayList到LinkedList

如果發(fā)生對表的一些插入和刪除操作，特別是對表的前端進行，那么數(shù)組就不是一種好的選擇。另一種數(shù)據(jù)結構：鏈表(linked list)。

鏈表由一系列節(jié)點組成，這些節(jié)點不必在內存中相連。每一個節(jié)點均含有表元素和到包含該元素后繼元的節(jié)點的鏈(link)。我們稱之為next鏈。最后一個單元的next鏈引用null。

鏈表的插入

讓每一個節(jié)點持有一個指向它在表中的前驅節(jié)點的鏈，我們稱之為雙鏈表(doubly linked list)。

總體設計

在考慮設計方面，我們將需要提供三個類：
1.MyLinkedList類本身，它包含到兩端的鏈、表的大小以及一些方法。
2.Noe類，它可能是一個私有的嵌套類。一個節(jié)點包含數(shù)據(jù)以及到前一個節(jié)點的鏈和到下一個節(jié)點的鏈，還有一些適當?shù)臉嬙旆椒ā?br /> 3.LinkedListIterator類，該類抽象了位置的概念，是一個私有類，并實現(xiàn)接口Iterator。它提供了方法next、hasNext和remove的實現(xiàn)。

標記節(jié)點：

前端創(chuàng)建一個額外的節(jié)點，邏輯上代表開始的標記。這些額外的節(jié)點有時候就叫作標記節(jié)點(sentinel node)；特別地，在前端的節(jié)點有時候也叫作頭節(jié)點(header node),而在末端的節(jié)點有時候也叫作尾節(jié)點(tail node)

Node類

私有的內部類

• 當前節(jié)點，前置節(jié)點，后續(xù)節(jié)點；
• 表示鏈表中的一個基本元素；

/*** 內部類，節(jié)點；屬性，當前節(jié)點，前置節(jié)點，后續(xù)節(jié)點* @param <T>*/private static class Node<T> {T item; // 當前的節(jié)點Node<T> next; // 下一個節(jié)點Node<T> prev; // 前置節(jié)點Node(Node<T> prev,T element,Node<T> next) {this.item = element;this.prev = prev;this.next = next;}@Overridepublic String toString() {String nextStr = null;if (next!=null){nextStr = next.item.toString();}String prevStr = null;if (prev!=null){prevStr = prev.item.toString();}return "Node{" +" prev=" + prevStr +"，item=" + item +", next=" + nextStr +'}';}}

Node的方法：根據(jù)index找node

思路：從頭部開始找，進行循環(huán)

    public Node<T> NodeByIndex(int index){Node<T> x = first; // 從頭部開始找for (int i = 0; i<index;i++){x = x.next;}return x;}

源碼采用如下策略

• 1.根據(jù)index和list的size確定從頭部還是尾部找；
• 2.根據(jù)index找node節(jié)點；

分析：

降低了復雜度：

如果都從頭部找，時間復雜度就是O(i)，在最極端的情況下，根據(jù)index找最后一個，時間復雜度是O(N)；

如果是先確定從頭部找，還是從尾部找，則時間復雜度最大是O(N/2)；

增刪改查的實現(xiàn)

增加元素

最簡單的情況，都是從尾部新增元素

• 1.新的節(jié)點的上一個節(jié)點為之前的尾部節(jié)點；
• 2.新的尾部節(jié)點為當前新增的節(jié)點；
• 3.如果是第一個節(jié)點，則需要把first設置為當前的節(jié)點
• 4.鏈表的size+1；

    @Overridepublic void add(T e) {Node<T> l = last;Node<T> newNode = new Node<>(l, e, null); // 新增的節(jié)點，尾部添加last = newNode;if (l==null){// 是第一個節(jié)點first = newNode;System.out.println("FirstNode --->"+first);}else {l.next = newNode;System.out.println("Add {"+e+"} ---->"+l);}size++;}

更一般的情況如下，插入一個元素

刪除元素

刪除頭部？尾部？中間

• 1.如果刪除的是頭部節(jié)點，則讓被刪除的節(jié)點的下一個節(jié)點為first節(jié)點；
• 2.如果刪除的尾部節(jié)點，則讓被刪除的節(jié)點的上一個節(jié)點的下一個節(jié)點為null；
• 3.如果刪除的是中間的節(jié)點，讓該節(jié)點的前置節(jié)點的下一個節(jié)點指向該節(jié)點的下一個節(jié)點；

    @Overridepublic void remove(int index) {// 找到要刪除的節(jié)點，前置節(jié)點，后續(xù)節(jié)點// 1.如果刪除的是頭部節(jié)點if (index==0){first = NodeByIndex(index+1);return;}// 2.如果不是頭部節(jié)點Node<T> tNode = NodeByIndex(index); // 當前節(jié)點Node<T> prev = tNode.prev; // 當前節(jié)點的上一個節(jié)點Node<T> next = tNode.next; // 當前節(jié)點的下一個節(jié)點if (next==null){// 刪除的是尾部節(jié)點prev.next = null;return;}// 刪除的是中間的某個節(jié)點// 讓該節(jié)點的前置節(jié)點的下一個節(jié)點指向該節(jié)點的下一個節(jié)點prev.next = next;next.prev = prev;size--;}

修改元素

被修改的節(jié)點的節(jié)點關系不變，只需要把當前節(jié)點的元素變?yōu)樽钚碌脑丶纯?/p>

代碼實現(xiàn)

查詢元素

調用node方法即可

    @Overridepublic T get(int index) {// 索引不能大于等于sizeif (index<0 || index>=size){throw new IndexOutOfBoundsException("LinkedList的索引越界");}return NodeByIndex(index).item;}

toString方法

完整代碼

List接口類

package com.tianju.book.jpa.mlist;/*** 手工打造ArrayList*/
public interface MyList<T> {/*** 增加一個元素，涉及到容量的變化*/void add(T t);/*** 根據(jù)索引刪除元素* @param index 要刪除元素的索引，超過索引？索引不存在？*/void remove(int index);/*** 根據(jù)索引修改一個元素* @param index 要修改的索引* @param t 修改的值*/void set(int index,T t);/*** 根據(jù)索引獲取元素* @param index 索引* @return 獲取的元素*/T get(int index);int size();String toString();}

LinkedList的實現(xiàn)

package com.tianju.book.jpa.myLinkList;import com.tianju.book.jpa.mlist.MyList;public class MyLinkedList<T> implements MyList<T> {int size = 0;Node<T> first; // 頭部節(jié)點Node<T> last; // 尾部節(jié)點/*** 內部類，節(jié)點；屬性，當前節(jié)點，前置節(jié)點，后續(xù)節(jié)點* @param <T>*/private static class Node<T> {T item; // 當前的節(jié)點Node<T> next; // 下一個節(jié)點Node<T> prev; // 前置節(jié)點Node(Node<T> prev,T element,Node<T> next) {this.item = element;this.prev = prev;this.next = next;}@Overridepublic String toString() {String nextStr = null;if (next!=null){nextStr = next.item.toString();}String prevStr = null;if (prev!=null){prevStr = prev.item.toString();}return "Node{" +" prev=" + prevStr +"，item=" + item +", next=" + nextStr +'}';}}@Overridepublic void add(T e) {Node<T> l = last;Node<T> newNode = new Node<>(l, e, null); // 新增的節(jié)點，尾部添加last = newNode;if (l==null){// 是第一個節(jié)點first = newNode;System.out.println("FirstNode --->"+first);}else {l.next = newNode;System.out.println("Add {"+e+"} ---->"+l);}size++;}public Node<T> NodeByIndex(int index){Node<T> x = first; // 從頭部開始找for (int i = 0; i<index;i++){x = x.next;}return x;}@Overridepublic void remove(int index) {// 找到要刪除的節(jié)點，前置節(jié)點，后續(xù)節(jié)點// 1.如果刪除的是頭部節(jié)點if (index==0){first = NodeByIndex(index+1);return;}// 2.如果不是頭部節(jié)點Node<T> tNode = NodeByIndex(index); // 當前節(jié)點Node<T> prev = tNode.prev; // 當前節(jié)點的上一個節(jié)點Node<T> next = tNode.next; // 當前節(jié)點的下一個節(jié)點if (next==null){// 刪除的是尾部節(jié)點prev.next = null;return;}// 刪除的是中間的某個節(jié)點// 讓該節(jié)點的前置節(jié)點的下一個節(jié)點指向該節(jié)點的下一個節(jié)點prev.next = next;next.prev = prev;size--;}@Overridepublic void set(int index, T element) {// 索引不能大于等于sizeif (index<0 || index>=size){throw new IndexOutOfBoundsException("LinkedList的索引越界");}Node<T> tNode = NodeByIndex(index); // 當前節(jié)點T oldVal = tNode.item; // 獲取舊的元素tNode.item = element; // 把當前節(jié)點的元素設置成新的
//        System.out.println(oldVal);}@Overridepublic T get(int index) {// 索引不能大于等于sizeif (index<0 || index>=size){throw new IndexOutOfBoundsException("LinkedList的索引越界");}return NodeByIndex(index).item;}@Overridepublic int size() {return size;}/*** 為了實現(xiàn)toString方法*/String str = "null-->";// 通過第一個節(jié)點遞歸調用，獲得LinkedList的鏈private String recursion(Node<T> first){if (!str.contains(first.item.toString())){str = str + first.item;}if (first.next==null){return str + "-->null";}str = str + "-->" +  first.next.item.toString();first = first.next;return recursion(first);}// 在每次調用后把str歸位；private void backStr(){str = "null-->";}@Overridepublic String toString() {String recursion = recursion(first);backStr();return "MyLinkedList{ " + recursion +" }";}
}

測試類

package com.tianju.book.jpa.myLinkList;import org.hibernate.event.spi.SaveOrUpdateEvent;import java.util.List;public class MyLinkedListTest1 {public static void main(String[] args) {MyLinkedList<String> list = new MyLinkedList<>();list.add("PET1");list.add("PET2");list.add("PET3");System.out.println("**********");System.out.println(list);list.add("PET4");System.out.println(list);System.out.println(list.size());//        System.out.println(list.get(4));
//        list.remove(0);
//        System.out.println("刪除頭部節(jié)點");
//        System.out.println(list);
//
//        System.out.println("刪除尾部節(jié)點");
//        list.remove(3-1);
//        System.out.println(list);System.out.println("刪除中間的節(jié)點");list.remove(2);System.out.println(list);System.out.println("進行set");list.set(0, "SHI1");System.out.println(list);}
}

---

總結

1.linkedList的節(jié)點，當前，上一個，下一個的思想；
2.根據(jù)index找node的方法，根據(jù)index確定從頭部還是尾部；
3.linkedlist的增刪改查的實現(xiàn)，本質是改變節(jié)點的信息；
4.遞歸方法實現(xiàn)自定義鏈表的toString方法；