Java基础-链表

偏执的太偏执、 2022-12-05 00:49 128阅读 0赞

## 1.概述 ##

**链式存储**：  
用一组任意类型的存储单元存储线性表，在逻辑上面相邻的结点在物理位置上面不一定相邻  
**链表（Linked list）**：  
采用链式存储方法的线性表叫做链表  
链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（“links”）  
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)  
**性质**：

*  其节点的存储单元可以不连续，每个节点中除存储原表结点中的数据外，还须存储上一个/下一个节点的地址，以反映节点之间的逻辑关系
 *  获取数据麻烦，需要遍历查找，比数组慢
 *  方便插入、删除

## 2.实现原理 ##

**①** 创建一个节点类，其中节点类包含两个部分，第一个是数据域（你到时候要往节点里面储存的信息），第二个是引用域（相当于指针，单向链表有一个指针，指向下一个节点；双向链表有两个指针，分别指向下一个和上一个节点）  
**②** 创建一个链表类，其中链表类包含三个属性：头结点、尾节点和大小，方法包含添加、删除、插入等等方法

## 3.分类 ##

*  单向链表  
    单向链表只有一个指针域，在整个节点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的节点  
    ![在这里插入图片描述][20200908161502231.png_pic_center]

//单向链表的节点类
    public class Node { 
         public Object data;
         public Node next;
         
         public Node(Object e){ 
            this.data = e;
         }
     }

*  双向链表

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

//双向链表的节点类
    public class Node { 
          public Object e;//每个节点中间位置用来存放你存储的东西
          public Node next;//每个节点的后一个指向
          public Node pre;//每个节点的前一个指向
          public Node(){ 
      
          }
          public Node(Object e){ 
              this.e = e;
             next = null;
             pre = null;
         }
     }

*  环形链表
 *  双向环形链表

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

## 4.单向链表 ##

package com.security.controller;
    
    /** * 单向链表 */
    public class MyLink { 
        //头节点
        Node head = null;
    
        /** * 链表中的节点 */
        class Node{ 
            //节点的引用，指向下一个节点
            Node next = null;
            //节点的对象，即内容
            int data;
    
            public Node(int data){ 
                this.data = data;
            }
        }
    
        /** * 向链表中插入数据 * @param d */
        public void addNode(int d){ 
            //实例化一个节点
            Node newNode = new Node(d);
            if (head == null) { 
                head = newNode;
                return;
            }
            Node tmp = head;
            while (tmp.next != null){ 
                tmp = tmp.next;
            }
            tmp.next = newNode;
        }
    
        /** * 除第index个节点 * @param index * @return */
        public boolean deleteNode(int index){ 
            if (index < 1 || index > length()){ 
                return false;
            }
            if (index == 1){ 
                head = head.next;
                return true;
            }
            int i = 1;
            Node preNode = head;
            Node curNode = preNode.next;
            while (curNode != null){ 
                if (i == index){ 
                    preNode.next = curNode.next;
                    return true;
                }
                preNode = curNode;
                curNode = curNode.next;
                i++;
            }
            return false;
        }
    
        /** * 返回节点长度 * @return */
        public int length(){ 
            int length = 0;
            Node tmp = head;
            while (tmp != null){ 
                length++;
                tmp = tmp.next;
            }
            return length;
        }
    
        /** * 在不知道头指针的情况下删除指定节点 * @param n * @return */
        public boolean deleteNode11(Node n){ 
            if (n == null || n.next == null){ 
                return false;
            }
            int tmp = n.data;
            n.data = n.next.data;
            n.next.data = tmp;
            n.next = n.next.next;
            System.out.println("删除成功！");
            return true;
        }
    
        public void printList(){ 
            Node tmp = head;
            while (tmp != null){ 
                System.out.println(tmp.data);
                tmp = tmp.next;
            }
        }
    
        public static void main(String[] args) { 
            MyLink list = new MyLink();
            list.addNode(88);
            list.addNode(66);
            list.addNode(77);
            list.addNode(2);
            list.addNode(55);
            list.addNode(36);
            System.out.println("linkLength:" + list.length());
            System.out.println("head.data:" + list.head.data);
            list.printList();
            list.deleteNode(4);
            System.out.println("After deleteNode(4):");
            list.printList();
        }
    
    }

## 5.判断单链表是否有环 ##

单链表成环一般有三种情况：

1.  从头节点指向下个，一直指下去，最后一个结点的next指向null
2.  从头节点指向下个，一直指下去，最后一个结点的next指向头节点，形成一个首尾相连的环链表
3.  从头节点指向下个，一直指下去，最后一个结点的next指向局部节点，形成一个局部尾部有环的链表

解法：

1.  先定义1个结点，先让他等于头节点，然后向后遍历，遍历一次，和头节点对比一次，如果出现相同，说明链表有环，如果没有出现相等情况，则说明没有环

这种算法只能处理，前两种情况，因此缺乏普遍性，不适用

1.  遍历链表，每遍历一个，把他们的hashcode值，先和数组里面的比较，如果没有再存储到一个数组里，如果找到有重复的，就说明有环
2.  定义两个指针，一个跑得快，一个跑得慢，有一天他两相遇了，说明有环

[20200908161502231.png_pic_center]: /images/20221123/e9f67f2053f34fb58ad1f658cbf4eb7e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/8d0aef848b414f46a91860b7b3cd5253.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3h1ZWd1Y2hlbg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/e0e7fefe6888483890de5e4200410fd2.png