1、顺序表和链表中的属性和方法
| 属性 | 顺序表 | 单向链表 | 双向链表 | ||
| 数组(elem) | 节点(ListNode)， 头(head) |
节点(ListNode)， 头(head)， 尾巴(tail) |
|||
| 方法 | 顺序表 | 单向链表 | 双向链表 | ||
| 打印 | O(n) | O(n) | O(n) | ||
| 增 | 头插 | 要从0下标开始往后移数据 O(n) |
O(1) | O(1) | |
| 尾插 | O(1) | 要找尾巴节点 O(n) |
O(1) | ||
| index位置插 | 要从index下标开始往后移数据 O(n) |
要找index-1位置的节点 O(n) |
要找index位置的节点 O(n) |
||
| 查 | 给下标，返回该下标的值 | O(1) | O(n) | O(n) | |
| 是否包含某个值 | O(n) | O(n) | O(n) | ||
| 删 | 删除第一次出现的某值 | O(n) | 要定义个前驱 O(n) |
O(n) |
|
| 删除所有出现的某值 | O(n) | 要定义个前驱 O(n) |
O(n) | ||
| 清空 | O(1) | O(1) | O(n) | ||
2、方法之删除
顺序表：
需要移动数据
链表：
单向链表：
双向链表：
- 当删除的是第一个节点时，这个节点没有前一个节点，只要修改一个指向，head也要往后走一步
- 当删除的是最后一个节点时，这个节点没有后一个节点，只要修改一个执行，tail也要往前走一步
- 当删除的节点是链表中唯一一个节点时，既没有前一个节点，也没有后一个节点，不需要修改指向，但我们需要把head和tail都置空。
代码如下：
删除第一次出现的值为key的节点 和 删除所有值为key节点
单向链表：
删除第一次出现的值为key的节点：
public void remove(int data){
if(head.val == data){
head = head.next;
return;
}
//直接定义一个前驱prev
ListNode prev = this.head;
ListNode cur = this.head.next;
while(cur != null){
if(cur.val == data){
prev.next = cur.next;
return;
}else {
prev = prev.next;
cur = cur.next;
}
}
}删除所有值为key节点：
public void removeAll(int data){
ListNode prev = this.head;
ListNode cur = this.head.next;
while(cur != null){
if(cur.val == data){
prev.next = cur.next;
cur = cur.next;
}else{
prev = prev.next;
cur = cur.next;
}
}
if(head.val == data){
head = head.next;
}
}双向链表：
删除第一次出现的值为key的节点：
更喜欢第一种方法！！！
cur.prev 为空，说明没有前一个节点
cur.next为空，说明没有后一个节点
cur.prev为空，且cur.next为空，说明既没有前一个节点，也没有后一个节点，即链表中只有这一个节点
刚好就是双向链表删除的几种特殊情况。
public void remove(int data){
ListNode cur = this.head;
while(cur != null){
if(cur.val == data){
if(cur.prev == null){
head = head.next;
}else{
cur.prev.next = cur.next;
}
if(cur.next == null){
tail = tail.next;
}else{
cur.next.prev = cur.prev;
}
return;
}
cur = cur.next;
}
} public void remove(int data){
//链表为空
if(this.head == null){
return;
}
//链表只有一个节点
if(this.head.next == null){
if(this.head.val == data){
this.head = null;
this.tail = null;
}
return;
}
//删除第一个节点
if(head.val == data){
head = head.next;
head.prev = null;
return;
}
ListNode cur = this.head;
while(cur != null){
if(cur.val == data){
cur.prev.next = cur.next;
if(cur.next == null){
//删除的是最后一个节点
tail = tail.prev;
}else{
cur.next.prev = cur.prev;
}
return;
}
cur = cur.next;
}
}删除所有值为key节点：
public void removeAll(int data){
ListNode cur = this.head;
while(cur != null){
if(cur.val == data){
if(cur.prev == null){
//删除的是第一个节点
head = head.next;
}else{
cur.prev.next = cur.next;
}
if(cur.next == null){
//删除的是最后一个节点
tail = tail.prev;
}else{
cur.next.prev = cur.prev;
}
}
cur = cur.next;
}
}public void removeAll2(int data){
ListNode cur = this.head;
while(cur != null){
if(cur.val == data){
//删除的是第一个节点
if(cur.prev == null){
head = head.next;
//如果链表只有一个节点
if(head == null){
tail = null;
}else {
head.prev = null;
}
}else {
cur.prev.next = cur.next;
if (cur.next == null) {
//删除的是最后一个节点
tail = tail.prev;
} else {
cur.next.prev = cur.prev;
}
}
}
cur = cur.next;
}
}3、面试题：顺序表和链表的区别是什么？
遇到问区别的题，我们要从共性出发！！！
1、顺序表和链表都有增删查改。顺序表支持随机访问，适合给定下标查找或存储元素，时间复杂度可以达到O(1)。链表适合插入和删除比较频繁的情况。对于插入，顺序表需要移动元素，特别是头插时，时间复杂度可以达到O(N)，而链表不需要移动元素，只需要修改指向。头插的时间复杂度为O(1)。单向链表增加一个尾巴节点，尾插的时间复杂度也可以达到O(1)。对于删除，链表也不需要移动元素，只需要修改指向。
2、顺序表和链表都是一种数据结构，顺序表底层是数组，是一块连续的内存，空间不够时需要扩容，扩容时可能会浪费空间。而链表是链式存储的，没有容量的概念，随用随取，不会浪费空间。
4、链表面试题（后面会每天做一题给补上）
（1）删除链表中等于给定值 val 的所有节点。(如上)
（2）反转一个单链表。
（3）给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
（4）输入一个链表，输出该链表中倒数第k个结点。
（5）将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
（6）编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。
（7）链表的回文结构。
（8）输入两个链表，找出它们的第一个公共结点。
（9）给定一个链表，判断链表中是否有环。
（10）给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL。
