【java】【数据结构】链表

水深无声 2024-03-27 14:27 108阅读 0赞

## 什么是链表 ##

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。

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

### 链表的类型 ###

接下来说一下链表的几种类型:

#### 单链表 ####

刚刚说的就是单链表。

#### 双链表 ####

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

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

#### 循环链表 ####

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。  
![在这里插入图片描述][c8c9eb1b70234c55be5c321058d14fc3.png]

### 链表存储方式 ###

了解完链表的类型，再来说一说链表在内存中的存储方式。

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

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

## 定义链表 ##

public class ListNode {
        
        // 结点的值
        int val;
    
        // 下一个结点
        ListNode next;
    
        // 节点的构造函数(无参)
        public ListNode() {
        
        }
    
        // 节点的构造函数(有一个参数)
        public ListNode(int val) {
        
            this.val = val;
        }
    
        // 节点的构造函数(有两个参数)
        public ListNode(int val, ListNode next) {
        
            this.val = val;
            this.next = next;
        }
    }

## 链表操作 ##

### 删除节点 ###

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

//删除节点
            cur.next=cur.next.next;

### 添加节点 ###

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

//添加节点
            LinkNode newNode = new LinkNode(val);
            newNode.next=cur.next;
            cur.next=newNode;

可以看出链表的增添和删除都是O(1)操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

### 遍历 ###

我们以- [203. 移除链表元素 - 力扣（LeetCode）][203. _ - _LeetCode]为例

#### 递归 ####

public ListNode removeElements(ListNode head, int val) {
        
            if(head==null){
        
                return head;
            }
            head.next=removeElements(head.next,val);
            return head.val==val?head.next:head;
        }

#### 迭代 ####

public ListNode removeElements(ListNode head, int val) {
        
            //创建一个虚拟的头节点
            ListNode dummyHead =new ListNode();
            dummyHead.next=head;
            ListNode cur=dummyHead;
            while(cur!=null&&cur.next!=null){
        
                if(cur.next.val==val){
        
                    cur.next=cur.next.next;//删除节点
                }else{
        
                    cur=cur.next;
                }
            }
            return dummyHead.next;
        }

## 和数组比较 ##

再把链表的特性和数组的特性进行一个对比，如图所示：

链表-链表与数据性能对比  
![在这里插入图片描述][d4186ecce3d04f33a6728528eb50c77a.png]

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。

## 参考资料 ##

*  [代码随想录-链表 (programmercarl.com)][-_ _programmercarl.com]

## 相关题目 ##

*  [707. 设计链表 - 力扣（LeetCode）][707. _ - _LeetCode]
 *  [206. 反转链表 - 力扣（LeetCode）][206. _ - _LeetCode]
 *  [24. 两两交换链表中的节点 - 力扣（LeetCode）][24. _ - _LeetCode]
 *  [19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）][19. _ N _ - _LeetCode]
 *  [面试题 02.07. 链表相交 - 力扣（LeetCode）][02.07. _ - _LeetCode]
 *  [142. 环形链表 II - 力扣（LeetCode）][142. _ II - _LeetCode]
 *  [203. 移除链表元素 - 力扣（LeetCode）][203. _ - _LeetCode]

[e1f0709c999f4e049189903f482a766e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2ea4c086328847689b48e13f0d658245.png
[3e7d85869c9747eb826452608efa75df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d5c9f1308a0742ebb1d0eca3273ff766.png
[c8c9eb1b70234c55be5c321058d14fc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/2c4e330e74244ac5abcdf7a6f800566c.png
[21197022b2d5493b816e0b9288c7d7cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e22163acc58c409eb8b79353d1f6845e.png
[0d1ba6ae014a49839109856c2a1642a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1a2d8edc2c3943e2b7bbb6557ca40678.png
[ae07dcb2b84841659451e9097710b59b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/686254608986412f9e9f764d712c7137.png
[203. _ - _LeetCode]: https://leetcode.cn/problems/remove-linked-list-elements/
[d4186ecce3d04f33a6728528eb50c77a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1ec5f13d99234050b6acbc6487530860.png
[-_ _programmercarl.com]: https://www.programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%8D%95%E9%93%BE%E8%A1%A8
[707. _ - _LeetCode]: https://leetcode.cn/problems/design-linked-list/
[206. _ - _LeetCode]: https://leetcode.cn/problems/reverse-linked-list/
[24. _ - _LeetCode]: https://leetcode.cn/problems/swap-nodes-in-pairs/
[19. _ N _ - _LeetCode]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
[02.07. _ - _LeetCode]: https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
[142. _ II - _LeetCode]: https://leetcode.cn/problems/linked-list-cycle-ii/