初识链表

向右看齐 2022-10-23 08:13 283阅读 0赞

### 链表 ###

*  链表的原理
 *   *  链表
     *  实现
 *  用引用和对象的知识理解
 *  链表具体实现
 *   *  结点的定义
     *  链表的创建
     *  链表的遍历
     *   *  遍历每个元素和计算链表中元素个数
         *  找到最后一个结点
         *  找到倒数第二个结点
         *  找到第n个结点
         *  找到链表中是否包含某个元素
 *  链表的插入和删除
 *   *   *  给定前驱结点后的插入
         *  给定前驱结点后的删除
         *  头插
         *  头删
         *  尾插
         *  尾删
     *  总结：

# 链表的原理 #

## 链表 ##

链表——属于线性表，元素与元素之间有相对的顺序，有头部\\尾部，还有当前结点cur，前驱结点prev，后继结点next。  
每个结点是为了组织链表而引入的一个结构，出来保存的元素外，还会保存指向下一个结点的引用。  
head是一个链表的头结点，通过head我们可以找到所有的结点，目前我们可以用头结点来代表一整条链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]

## 实现 ##

1、结点的定义：

class Node { 
        int val;//保存元素
        Node next;//指向下一个节点的引用，尾结点的next==null
    }

2、头结点：

Node head=...；
    //当链表的头结点为null，表示头结点不存在。还可以理解为，没有头结点的链表，即一个空链表。
    Node head = null;

# 用引用和对象的知识理解 #

（结点中有许多.next…看来看去就绕晕了，我们可以借助引用和对象来理解，更好接受）

1 Node P = ...; //p是一条链表中的某个结点
    2 Node q = ...; //q是一条链表中的某个结点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]  
在上面的情况下，画图表现变化：  
1、p = q；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]  
2、p = q.next;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]  
3、p.next = q;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]  
4、p.next = q.next;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 5]  
总结：  
我们会发现，左边和右边都存在.next,绕着绕着就把人绕晕了，对于这种情况，我们可以把等号左边去找引用，等号右边去找对象。  
简单说就是 **左引用，右对象**，这样理解。

# 链表具体实现 #

## 结点的定义 ##

class Node { 
        int val;//保存元素
        Node next;//指向下一个节点的引用，尾结点的next==null
    
        @Override
        public String toString() { 
            return "Node{" + "val=" + val + '}';
        }
    }

## 链表的创建 ##

Node n1 = new Node();
            Node n2 = new Node();
            Node n3 = new Node();
            Node n4 = new Node();
    
            n1.val = 1;
            n2.val = 2;
            n3.val = 3;
            n4.val = 4;
    
            n1.next = n2;
            n2.next = n3;
            n3.next = n4;
            n4.next = null;
    
            Node head = n1;

## 链表的遍历 ##

### 遍历每个元素和计算链表中元素个数 ###

Node head = n1;
            int count = 0;
            Node cur = head;
            while (cur != null) { 
    
                System.out.println(cur.val);
                cur = cur.next;
                count++;
            }
            System.out.println(count);

### 找到最后一个结点 ###

Node cur = head;
            while (cur.next != null) { 
                cur = cur.next;
            }
            System.out.println(cur.val);
        }

### 找到倒数第二个结点 ###

//找到倒数第二个结点
            Node cur = head;
            while (cur.next.next != null) { 
                cur = cur.next;
            }
            System.out.println(cur.val);
        }

### 找到第n个结点 ###

//找到第n个结点
    
            int n = 2;
            Node ncur = head;
            for (int i = 1; i < n; i++) { 
                ncur = ncur.next;
            }
            System.out.println(ncur.val);

### 找到链表中是否包含某个元素 ###

Node cur = head;
            while (cur != null) { 
                if (cur.val == target) { 
                    //找到了
                    System.out.println("找到了");
                }
                cur = cur.next;
            }
            System.out.println("没找到");

# 链表的插入和删除 #

### 给定前驱结点后的插入 ###

Node prev = n2;
            Node node = new Node();
            node.val = 6;
    
            node.next = prev.next;
            prev.next = node;

### 给定前驱结点后的删除 ###

Node prev = n2;
            prev.next = prev.next.next;

### 头插 ###

Node node=new Node();
            node.val=12;
            
            node.next=head;
            head=node;

### 头删 ###

//头删
            if (head == null) { 
                throw new RuntimeException("链表为空");
            }
            head = head.next;

### 尾插 ###

//链表为空，直接插入
            if (head == null) { 
                Node node = new Node();
                node.val = 1;
            }
            //链表不为空
            Node last = head;
            while (last.next != null) { 
                last = last.next;
            }
            Node node = new Node();
            node.val = 12;
            last.next = node;

### 尾删 ###

//尾删
            if (head == null) { 
                throw new RuntimeException("链表为空");
            }
            //链表不为空只有一个节点
            if (head.next == null) { 
                head.next=null;
            }
            Node last = head;
            while (last.next.next != null) { 
                last = last.next;
            }
            last.next = null;

## 总结： ##

我们发现链表里面有许多的 （.next），左边有，右边也有，有的代表着引用，有的代表着对象。  
我们可以把等号左边去找引用，等号右边去找对象。  
简单说就是 **左引用，右对象**，这样理解。

对于数据结构的问题，我们真的需要多多的去理解，并且多画图，借助图像理解数据结构的具体逻辑。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221023/9599d092b9aa422c8b1458bc1f1bb7cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221023/21bd1e655f234a4bace4650df3ed614a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: /images/20221023/80ad2914d93e4c71b559084018408251.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: /images/20221023/28fe6991a16446348d1d6ba58a721e05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]: /images/20221023/4bc08cf5cab3450ab08817d24ce92183.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 5]: /images/20221023/d8895c80c2ec475994d03d07863096dc.png