单链表

sz475 2020-12-30 原文

定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

数据结构

public class ListNode {
　　int val;
　　ListNode next;
　　ListNode() {}
　　ListNode(int val) { this.val = val; }
　　ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

了解链表从以下常规操作入手

插入操作

　　A链表插入：before

　　　　A链表插入：after

　　　　分析（个人理解）：不管插入在链表的头、中间、尾，它的复杂度都是O(1)，只需要改变指针的指向。找到插入前的节点，接着next（指针指向）到插入的node节点，然后插入的node节点的next指向下一个node节点。如下伪代码：　　　

// 插入前
ListNode head;// node1就是head节点
ListNode node2;
ListNode node3 = head.next;

// 插入后
head.next = node2; // 指针head(node1)指向node2
node2.next = node3;// 指针node2指向node3

查找操作

　　B链表查找：

　　　分析（个人理解）：链表的查找需要循环，它的复杂度是O(n)。比如查找元素的val值，如下伪代码：

ListNode head;
while(head != null){
　　int data= head.val;// 获取node中的元素；
　　head = head.next;// 下一个node节点
}

删除操作

　　 操作前：给大家引入dummy节点（哨兵节点），可以理解dummy节点就是一个虚拟的节点，放在链表的前面，指针指向头节点。

ListNode dummy = new ListNode(-1);// 创建dummy节点
dummy.next = head; // dummy节点指针 指向头节点
.......
return dummy.next; // dummy.next返回还是链表m

　　 C链表删除：

　　　 1、删除头节点　

　　　　分析（个人理解）：链表删除头节点只需要操作一次就可以，它的复杂度是O(1)，如下伪代码：

// 删除前
ListNode head;(头节点我们是知道的)
ListNode dummy = new ListNode(-1);// 创建dummy节点
dummy.next = head; // dummy的指向头节点
ListNode next = head.next;// head的下一个node节点

// 删除后
head.next = null；// 头节点不再指向其他node节点
dummy.next = next;// dummy节点指向head节点的下一个节点，此时已完成删除了head节点
return dummy.next;

　　 2、删除任意节点

　　　　分析（个人理解）：删除任意的节点，它的复杂度是O(n)，如下伪代码：

// 假如链表的长度是n，删除第 m 的node节点，m < n;
ListNode head;//(头节点我们是知道的)
ListNode dummy = new ListNode(-1);// 创建dummy节点
dummy.next = head; // dummy的指向头节点
head = dummy; // 将dummy定义头节点

for(int i = 1; i < m; i++){
    head = head.next;// 为了得到m的前节点；
}
ListNode nodem = head.next;// 得到第 m 的node节点
ListNode lastm = nodem.next;// 得到 m 的下一个node节点
nodem.next = null; // m 的node节点指针指向null
head.next = lastm; // m 的前节点指向 m 的下一个节点
return dummy.next; // 返回链表

总结

1、以上是我自己对链表的理解，写的可能比较啰嗦，如有不解或者错误希望指正。

2、数组的结构以及插入、删除、查找都比较简单我就不写了。

2、大家也多去了解下数据结构，多去leetCode去刷题。