手写链表之LinkedList源码分析

ゝ一世哀愁。 2023-10-04 14:28 30阅读 0赞

### 单链表 ###

单链表，用于存储逻辑关系为 “一对一” 的数据。与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。  
![在这里插入图片描述][20210526234641253.png]

#### 节点 ####

在上图中无法提现出元素之间的逻辑关系，对此，链表的解决方案是，每个数据元素在存储时都配备一个指针，用于指向自己的直接后继元素。表示一个节点如下：

//节点信息
    class Node {
        
        E data;
        Node next;
    
        public Node(E element, Node next) {
        
            this.data = element;
            this.next = next;
        }
    
        public Node(E data) {
        
            this.data = data;
        }
    }

![在这里插入图片描述][20210526234904886.png]  
因此，在链表中，每个数据的存储有以下2部分组成

*  数据本身，其所在的区域叫做**数据域**
 *  指向后继元素的指针，叫**指针域**  
    ![在这里插入图片描述][20210526235221721.png]  
    上图所示的结构在链表中称为节点。也就是说，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70]

#### 单链表—增 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 1]

/**
      * 头部添加节点
      *
      * @param e
      */
     public void add(E e) {
        
         //头结点
         Node cur = new Node(e, list);
         list = cur;
         size++;
     }
    
     /**
       * 指定位置添加节点
       *
       * @param index
       * @param e     0 1 2 3 4
       */
     public void add(int index, E e) {
        
     	  //越界检查
         checkElementIndex(index);
         Node preNode = list;
         for (int i = 0; i < index - 1; i++) {
        
             //找到插入位置的前一个节点
             preNode = preNode.next;
         }
         Node node = new Node(e);
         node.next = preNode.next;
         preNode.next = node;
         size++;
     }

#### 单链表—删 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 2]

/**
     * 删除头部节点
     */
    public void remove() {
        
        if (list != null) {
        
            Node node = list;
            list = node.next;
            //GC
            node.next = null;
            size--;
        }
    }
    
    /**
     * 删除指定位置节点
     * 1 2 3 4 5
     * 0 1 2 3 4
     *
     * @param index
     */
    public void remove(int index) {
        
        checkElementIndex(index);
        Node preNode = list;
        for (int i = 0; i < index - 1; i++) {
        
            //找到指定位置元素的前一个节点
            preNode = preNode.next;
        }
        //指定位置的节点
        Node next = preNode.next;
        preNode.next = next.next;
        //GC
        next = null;
        size--;
    }
    
    /**
     * 删除最后一个节点
     */
    public void removeLast() {
        
        if (list != null) {
        
            //当前节点
            Node cur = list;
            //最后一个节点的前一个节点
            Node preNode = list;
            while (cur.next != null) {
        
                preNode = cur;
                cur = cur.next;
            }
            preNode = null;//此时cur已经为null
            size--;
        }
    }

#### 单链表—改 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 3]

/**
     * 修改指定索引的元素
     *
     * @param index
     * @param e
     */
    public void set(int index, E e) {
        
        checkElementIndex(index);
        Node cur = list;
        for (int i = 0; i < index; i++) {
        
            cur = cur.next;
        }
        cur.data = e;
    }

#### 单链表—查 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 4]

/**
      * 获取头部节点
      */
     public E get() {
        
         if (list != null) {
        
             return list.data;
         } else {
        
             return null;
         }
     }
    
      /**
       * 获取指定位置的元素
       *
       * @param index
       * @return
       */
      public E get(int index) {
        
          checkElementIndex(index);
          Node cur = list;
          for (int i = 0; i < index; i++) {
        
              cur = cur.next;
          }
          return cur.data;
      }

完整代码

/**
     * 单链表
     *
     */
    public class SingleLinkedList<E> {
        
    
        int size = 0;
    
        /**
         * 指向第一个节点的指针
         */
        Node list;
    
        /**
         * 头部添加节点
         *
         * @param e
         */
        public void add(E e) {
        
            //头结点
            Node cur = new Node(e, list);
            list = cur;
            size++;
        }
    
        /**
         * 指定位置添加节点
         *
         * @param index
         * @param e     0 1 2 3 4
         */
        public void add(int index, E e) {
        
            checkElementIndex(index);
            Node preNode = list;
            for (int i = 0; i < index - 1; i++) {
        
                //找到插入位置的前一个节点
                preNode = preNode.next;
            }
            Node node = new Node(e);
            node.next = preNode.next;
            preNode.next = node;
            size++;
        }
    
    
        /**
         * 删除头部节点
         */
        public void remove() {
        
            if (list != null) {
        
                Node node = list;
                list = node.next;
                //GC
                node.next = null;
                size--;
            }
        }
    
        /**
         * 删除指定位置节点
         * 1 2 3 4 5
         * 0 1 2 3 4
         *
         * @param index
         */
        public void remove(int index) {
        
            checkElementIndex(index);
            Node preNode = list;
            for (int i = 0; i < index - 1; i++) {
        
                //找到指定位置元素的前一个节点
                preNode = preNode.next;
            }
            //指定位置的节点
            Node next = preNode.next;
            preNode.next = next.next;
            //GC
            next = null;
            size--;
        }
    
        /**
         * 删除最后一个节点
         */
        public void removeLast() {
        
            if (list != null) {
        
                //当前节点
                Node cur = list;
                //最后一个节点的前一个节点
                Node preNode = list;
                while (cur.next != null) {
        
                    preNode = cur;
                    cur = cur.next;
                }
                preNode = null;//此时cur已经为null
                size--;
            }
        }
    
        /**
         * 修改指定索引的元素
         *
         * @param index
         * @param e
         */
        public void set(int index, E e) {
        
            checkElementIndex(index);
            Node cur = list;
            for (int i = 0; i < index; i++) {
        
                cur = cur.next;
            }
            cur.data = e;
        }
    
        /**
         * 获取头部节点
         */
        public E get() {
        
            if (list != null) {
        
                return list.data;
            } else {
        
                return null;
            }
        }
    
        /**
         * 获取指定位置的元素
         *
         * @param index
         * @return
         */
        public E get(int index) {
        
            checkElementIndex(index);
            Node cur = list;
            for (int i = 0; i < index; i++) {
        
                cur = cur.next;
            }
            return cur.data;
        }
    
    
        class Node {
        
            E data;
            Node next;
    
            public Node(E element, Node next) {
        
                this.data = element;
                this.next = next;
            }
    
            public Node(E data) {
        
                this.data = data;
            }
    
            public Node() {
        
            }
    
            @Override
            public String toString() {
        
                return "Node{" +
                        "data=" + data +
                        ", next=" + next +
                        '}';
            }
        }
    
        /**
         * 判断参数是否为现有元素的索引  即边界
         *
         * @param index
         */
        private void checkElementIndex(int index) {
        
            if (!(index >= 0 && index < size))
                throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    
        @Override
        public String toString() {
        
            Node node = list;
            for (int i = 0; i < size; i++) {
        
                System.out.print(node.data + " ");
                node = node.next;
            }
            return super.toString();
        }
    
        public static void main(String[] args) {
        
            SingleLinkedList<Integer> list = new SingleLinkedList<>();
            list.add(5);
            list.add(4);
            list.add(3);
            list.add(2);
            list.add(1);
            list.toString();
            System.out.println();
            list.add(2, 5);
            list.toString();
            list.removeLast();
            System.out.println();
            list.toString();
            list.set(1, 1);
            System.out.println();
            list.toString();
            System.out.println();
            System.out.println(list.get());
        }
    }

### 双链表LinkedList ###

双链表，指各节点之间的逻辑关系是双向的。

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

#### 节点 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 5]  
因此，在双向链表中各节点包含以下 3 部分信息

*  指针域：用于指向当前节点的直接前驱节点；
 *  数据域：用于存储数据元素。
 *  指针域：用于指向当前节点的直接后继节点；

#### 双链表—增 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 6]

#### 双链表—删 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 7]

[20210526234641253.png]: https://img-blog.csdnimg.cn/20210526234641253.png
[20210526234904886.png]: https://img-blog.csdnimg.cn/20210526234904886.png
[20210526235221721.png]: https://img-blog.csdnimg.cn/20210526235221721.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210526235321418.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210527224344254.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210527225044633.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210527225500803.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20210527225725861.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ==,size_16,color_FFFFFF,t_70
[20210527230103493.png]: https://img-blog.csdnimg.cn/20210527230103493.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20210527230450550.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210528000910397.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20210528001213715.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ3NzUzMQ==,size_16,color_FFFFFF,t_70