引出

---

1.linkedList的节点，当前，上一个，下一个的思想；
2.根据index找node的方法，根据index确定从头部还是尾部；
3.linkedlist的增删改查的实现，本质是改变节点的信息；
4.递归方法实现自定义链表的toString方法；

从ArrayList到Linkedlist

手动实现ArrayList

Java进阶（3）——手动实现ArrayList & 源码的初步理解分析 & 数组插入数据和删除数据的问题

从ArrayList到LinkedList

如果发生对表的一些插入和删除操作，特别是对表的前端进行，那么数组就不是一种好的选择。另一种数据结构：链表(linked list)。

链表由一系列节点组成，这些节点不必在内存中相连。每一个节点均含有表元素和到包含该元素后继元的节点的链(link)。我们称之为next链。最后一个单元的next链引用null。

链表的插入

让每一个节点持有一个指向它在表中的前驱节点的链，我们称之为双链表(doubly linked list)。

总体设计

在考虑设计方面，我们将需要提供三个类：
1.MyLinkedList类本身，它包含到两端的链、表的大小以及一些方法。
2.Noe类，它可能是一个私有的嵌套类。一个节点包含数据以及到前一个节点的链和到下一个节点的链，还有一些适当的构造方法。
3.LinkedListIterator类，该类抽象了位置的概念，是一个私有类，并实现接口Iterator。它提供了方法next、hasNext和remove的实现。

标记节点：

前端创建一个额外的节点，逻辑上代表开始的标记。这些额外的节点有时候就叫作标记节点(sentinel node)；特别地，在前端的节点有时候也叫作头节点(header node),而在末端的节点有时候也叫作尾节点(tail node)

Node类

私有的内部类

• 当前节点，前置节点，后续节点；
• 表示链表中的一个基本元素；

/*** 内部类，节点；属性，当前节点，前置节点，后续节点* @param <T>*/private static class Node<T> {T item; // 当前的节点Node<T> next; // 下一个节点Node<T> prev; // 前置节点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的方法：根据index找node

思路：从头部开始找，进行循环

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

源码采用如下策略

• 1.根据index和list的size确定从头部还是尾部找；
• 2.根据index找node节点；

分析：

降低了复杂度：

如果都从头部找，时间复杂度就是O(i)，在最极端的情况下，根据index找最后一个，时间复杂度是O(N)；

如果是先确定从头部找，还是从尾部找，则时间复杂度最大是O(N/2)；

增删改查的实现

增加元素

最简单的情况，都是从尾部新增元素

• 1.新的节点的上一个节点为之前的尾部节点；
• 2.新的尾部节点为当前新增的节点；
• 3.如果是第一个节点，则需要把first设置为当前的节点
• 4.链表的size+1；

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

更一般的情况如下，插入一个元素

删除元素

删除头部？尾部？中间

• 1.如果删除的是头部节点，则让被删除的节点的下一个节点为first节点；
• 2.如果删除的尾部节点，则让被删除的节点的上一个节点的下一个节点为null；
• 3.如果删除的是中间的节点，让该节点的前置节点的下一个节点指向该节点的下一个节点；

    @Overridepublic void remove(int index) {// 找到要删除的节点，前置节点，后续节点// 1.如果删除的是头部节点if (index==0){first = NodeByIndex(index+1);return;}// 2.如果不是头部节点Node<T> tNode = NodeByIndex(index); // 当前节点Node<T> prev = tNode.prev; // 当前节点的上一个节点Node<T> next = tNode.next; // 当前节点的下一个节点if (next==null){// 删除的是尾部节点prev.next = null;return;}// 删除的是中间的某个节点// 让该节点的前置节点的下一个节点指向该节点的下一个节点prev.next = next;next.prev = prev;size--;}

修改元素

被修改的节点的节点关系不变，只需要把当前节点的元素变为最新的元素即可

代码实现

查询元素

调用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);/*** 根据索引删除元素* @param index 要删除元素的索引，超过索引？索引不存在？*/void remove(int index);/*** 根据索引修改一个元素* @param index 要修改的索引* @param t 修改的值*/void set(int index,T t);/*** 根据索引获取元素* @param index 索引* @return 获取的元素*/T get(int index);int size();String toString();}

LinkedList的实现

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; // 头部节点Node<T> last; // 尾部节点/*** 内部类，节点；属性，当前节点，前置节点，后续节点* @param <T>*/private static class Node<T> {T item; // 当前的节点Node<T> next; // 下一个节点Node<T> prev; // 前置节点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); // 新增的节点，尾部添加last = newNode;if (l==null){// 是第一个节点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) {// 找到要删除的节点，前置节点，后续节点// 1.如果删除的是头部节点if (index==0){first = NodeByIndex(index+1);return;}// 2.如果不是头部节点Node<T> tNode = NodeByIndex(index); // 当前节点Node<T> prev = tNode.prev; // 当前节点的上一个节点Node<T> next = tNode.next; // 当前节点的下一个节点if (next==null){// 删除的是尾部节点prev.next = null;return;}// 删除的是中间的某个节点// 让该节点的前置节点的下一个节点指向该节点的下一个节点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); // 当前节点T oldVal = tNode.item; // 获取旧的元素tNode.item = element; // 把当前节点的元素设置成新的
//        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;}/*** 为了实现toString方法*/String str = "null-->";// 通过第一个节点递归调用，获得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("删除头部节点");
//        System.out.println(list);
//
//        System.out.println("删除尾部节点");
//        list.remove(3-1);
//        System.out.println(list);System.out.println("删除中间的节点");list.remove(2);System.out.println(list);System.out.println("进行set");list.set(0, "SHI1");System.out.println(list);}
}

---

总结

1.linkedList的节点，当前，上一个，下一个的思想；
2.根据index找node的方法，根据index确定从头部还是尾部；
3.linkedlist的增删改查的实现，本质是改变节点的信息；
4.递归方法实现自定义链表的toString方法；