Java进阶（7）——手动实现LinkedList & 内部node类的实现 & 增删改查的实现 & toString方法 & 源码的初步理解

怼烎@ 2023-10-15 09:16 18阅读 0赞

#### 目录 ####

*  引出
 *  从ArrayList到Linkedlist
 *   *  手动实现ArrayList
     *  从ArrayList到LinkedList
 *  总体设计
 *   *  Node类
     *  Node的方法：根据index找node
 *  增删改查的实现
 *   *  增加元素
     *  删除元素
     *  修改元素
     *  查询元素
 *  toString方法
 *  完整代码
 *   *  List接口类
     *  LinkedList的实现
     *  测试类
 *  总结

## 引出 ##

--------------------

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

## 从ArrayList到Linkedlist ##

![在这里插入图片描述][248493d253a24ace86d098f64a6d2071.png]

### 手动实现ArrayList ###

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

![在这里插入图片描述][4052061514704a7ebe2054f68813cfec.png]

### 从ArrayList到LinkedList ###

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

![在这里插入图片描述][f5d551e24fb64302a7b8d199cfb72e0a.png]

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

![在这里插入图片描述][675cd46e82ce4e308e66c734dfea76ab.png]

> 链表的插入

![在这里插入图片描述][261582a408c04df3aef00a8c1861f4ba.png]

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

![在这里插入图片描述][2aa53545205e4d9a91bd5bf6a957524d.png]

## 总体设计 ##

![在这里插入图片描述][67fe93a701724f08ac00aee9169ed636.png]

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

标记节点：

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

![在这里插入图片描述][2f76b074c338420fb5fcb2fd96a11689.png]

### Node类 ###

私有的内部类

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

![在这里插入图片描述][5d5c88c93d2f497eb2bdf7db1741e1d5.png]

/**
         * 内部类，节点；属性，当前节点，前置节点，后续节点
         * @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;
            }
    
            @Override
            public 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 +
                        '}';
            }
        }

![在这里插入图片描述][62a4dc49d2ac4a7087c48b0bc667dc47.png]

### 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节点；

![在这里插入图片描述][8ad736f978d84303b2faa2faedfd6921.png]

分析：

降低了复杂度：

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

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

## 增删改查的实现 ##

### 增加元素 ###

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

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

![在这里插入图片描述][2014fc8d6ecc4eb8a95c1e5a97325d88.png]

@Override
        public 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++;
        }

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

![在这里插入图片描述][c312a9f21f3640949a431d46a50ab715.png]

### 删除元素 ###

> 删除头部？尾部？中间

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

![在这里插入图片描述][715960fd1e4f4282850d1540661cb6b1.png]

@Override
        public 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--;
        }

### 修改元素 ###

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

![在这里插入图片描述][afd678961dc543bdbb5674ab4fbc6e46.png]

> 代码实现

![在这里插入图片描述][2db13ca394584168aef3ac349b4007f1.png]

### 查询元素 ###

> 调用node方法即可

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

## toString方法 ##

![在这里插入图片描述][70283b4b3ee94961965f001a8da6b619.png]

## 完整代码 ##

### 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;
            }
    
            @Override
            public 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 +
                        '}';
            }
        }
    
    
        @Override
        public 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;
        }
    
        @Override
        public 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--;
        }
    
        @Override
        public void set(int index, T element) {
        
            // 索引不能大于等于size
            if (index<0 || index>=size){
        
                throw new IndexOutOfBoundsException("LinkedList的索引越界");
            }
            Node<T> tNode = NodeByIndex(index); // 当前节点
            T oldVal = tNode.item; // 获取旧的元素
            tNode.item = element; // 把当前节点的元素设置成新的
    //        System.out.println(oldVal);
        }
    
        @Override
        public T get(int index) {
        
            // 索引不能大于等于size
            if (index<0 || index>=size){
        
                throw new IndexOutOfBoundsException("LinkedList的索引越界");
            }
            return NodeByIndex(index).item;
        }
    
        @Override
        public 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-->";
        }
    
        @Override
        public 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);
    
        }
    }

![在这里插入图片描述][a4b276843aed415299157b45313726b2.png]

--------------------

## 总结 ##

[248493d253a24ace86d098f64a6d2071.png]: https://img-blog.csdnimg.cn/248493d253a24ace86d098f64a6d2071.png
[Java_3_ArrayList _ _ _]: https://blog.csdn.net/Pireley/article/details/132326323
[4052061514704a7ebe2054f68813cfec.png]: https://img-blog.csdnimg.cn/4052061514704a7ebe2054f68813cfec.png
[f5d551e24fb64302a7b8d199cfb72e0a.png]: https://img-blog.csdnimg.cn/f5d551e24fb64302a7b8d199cfb72e0a.png
[675cd46e82ce4e308e66c734dfea76ab.png]: https://img-blog.csdnimg.cn/675cd46e82ce4e308e66c734dfea76ab.png
[261582a408c04df3aef00a8c1861f4ba.png]: https://img-blog.csdnimg.cn/261582a408c04df3aef00a8c1861f4ba.png
[2aa53545205e4d9a91bd5bf6a957524d.png]: https://img-blog.csdnimg.cn/2aa53545205e4d9a91bd5bf6a957524d.png
[67fe93a701724f08ac00aee9169ed636.png]: https://img-blog.csdnimg.cn/67fe93a701724f08ac00aee9169ed636.png
[2f76b074c338420fb5fcb2fd96a11689.png]: https://img-blog.csdnimg.cn/2f76b074c338420fb5fcb2fd96a11689.png
[5d5c88c93d2f497eb2bdf7db1741e1d5.png]: https://img-blog.csdnimg.cn/5d5c88c93d2f497eb2bdf7db1741e1d5.png
[62a4dc49d2ac4a7087c48b0bc667dc47.png]: https://img-blog.csdnimg.cn/62a4dc49d2ac4a7087c48b0bc667dc47.png
[8ad736f978d84303b2faa2faedfd6921.png]: https://img-blog.csdnimg.cn/8ad736f978d84303b2faa2faedfd6921.png
[2014fc8d6ecc4eb8a95c1e5a97325d88.png]: https://img-blog.csdnimg.cn/2014fc8d6ecc4eb8a95c1e5a97325d88.png
[c312a9f21f3640949a431d46a50ab715.png]: https://img-blog.csdnimg.cn/c312a9f21f3640949a431d46a50ab715.png
[715960fd1e4f4282850d1540661cb6b1.png]: https://img-blog.csdnimg.cn/715960fd1e4f4282850d1540661cb6b1.png
[afd678961dc543bdbb5674ab4fbc6e46.png]: https://img-blog.csdnimg.cn/afd678961dc543bdbb5674ab4fbc6e46.png
[2db13ca394584168aef3ac349b4007f1.png]: https://img-blog.csdnimg.cn/2db13ca394584168aef3ac349b4007f1.png
[70283b4b3ee94961965f001a8da6b619.png]: https://img-blog.csdnimg.cn/70283b4b3ee94961965f001a8da6b619.png
[a4b276843aed415299157b45313726b2.png]: https://img-blog.csdnimg.cn/a4b276843aed415299157b45313726b2.png