链表简介
链表,是存储空间不连续的线性表。在做题或者一些底层结构挺常见的,但是在开发中好像用得很少(可能我比较菜0-0...)。一个简单的带头结点的单链表可以表示成这样:
class SingleLinkedList{
// 只有一个头结点
private Node head;
// ...
class Node{
Object data;
Node next;
// ...
}
}
简单地说,它的存储结构是一个一个地结点,每个结点中有你想存储的信息,同时还有指向下一个结点(next)的引用。
如果想要在此查找元素的话,就通过next结点进行遍历,直到为空。
链表有很多分类,比如是否带头尾结点,是否是双向链表,是否是循环链表等等,每种分类都对应着不同的特点,有特定的应用场景。
它最大的特点是,寻找元素需要结点中的next指针,一个一个地往下找。即使使用双向链表,它也需要遍历N/2个元素,因此查询的时间复杂度在O(N)。
但是,如果你定位到某个元素,要进行删除的话,只要O(1)的时间复杂度,不需要像数组一样把后面的元素全部移动一位,因为它的数据组成只依靠额外的引用指针。
注意事项
理解指针/引用
这让我想到一些值传递/引用传递相关知识, 就是理解一下Node next
的含义。
比如,p.next = newNode
,它表示让p这个Node结点的next指针指向newNode这个结点,也就是指向了newNode所在的内存地址。这样操作之后,p就能通过next成员变量找到下一个结点的位置,也就是这个newNode。
需要好好理解这个指针的引用,举个例子,我想要在a、b结点中插入一个新结点newNode,其中a.next=b。
如果写成这样
a.next = newNode;
newNode.next = a.next;
这样做会整出一个循环。。
在改变a的next指针指向newNode时,你就会丢失了对b结点的指向,也就是说,对于一条单链表,在进行如上操作后,已经没有结点能够指向b了,也就丢失了b的结点。
正确的指向应该是解决b相关的引用,然后再断开链表。(要这么想,一旦修改了引用,如果没有保存,那就再也找不到了)
newNode.next = a.next;
a.next = newNode;
哨兵
这个分为两层概念,一层是指头、尾结点,另一层指在算法中一些比较上的优化?
对于一个单链表,它分为有头结点的和有头指针的。
头结点,是指一个空的结点,从数值上,它没有任何意义,仅仅充当着第一个真正存储数据的前一个结点。
而头指针的,只是一个指向第一个元素的指针,不是真正的结点。
头结点有什么好处呢?它可以方便边界条件的处理,在增/删操作中,如果只有头指针的话,会对第一个结点的操作进行特殊判断,但是有了头结点就不同,因为固定有一个结点在,我对头结点的next进行操作,因为总是有头结点在,因此,第一个结点也不会显得很特殊。
带头结点时,对于插入操作,可以统一地用这两行实现
newNode.next = p.next;
p.next = newNode;
这个p则是指向要删除结点的前一个结点。对于第一个结点,它的前一个结点是头结点;对于第k个结点,它的前一个结点是k-1个结点。它们之前没什么不同嘛。而如果没有头结点,就要做一些特殊处理了,比如head = newNode;
我在文章中发现哨兵还有这种用法,展示一下。
下面是普通的查找元素。
// 在数组 a 中,查找 key,返回 key 所在的位置
// 其中,n 表示数组 a 的长度
int find(char* a, int n, char key) {
// 边界条件处理,如果 a 为空,或者 n<=0,说明数组中没有数据,就不用 while 循环比较了
if(a == null || n <= 0) {
return -1;
}
int i = 0;
// 这里有两个比较操作:i<n 和 a[i]==key.
while (i < n) {
if (a[i] == key) {
return i;
}
++i;
}
return -1;
}
下面是加了哨兵的查找元素。
// 在数组 a 中,查找 key,返回 key 所在的位置
// 其中,n 表示数组 a 的长度
// 我举 2 个例子,你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
int find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}
// 这里因为要将 a[n-1] 的值替换成 key,所以要特殊处理这个值
if (a[n-1] == key) {
return n-1;
}
// 把 a[n-1] 的值临时保存在变量 tmp 中,以便之后恢复。tmp=6。
// 之所以这样做的目的是:希望 find() 代码不要改变 a 数组中的内容
char tmp = a[n-1];
// 把 key 的值放到 a[n-1] 中,此时 a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;
int i = 0;
// while 循环比起代码一,少了 i<n 这个比较操作
while (a[i] != key) {
++i;
}
// 恢复 a[n-1] 原来的值, 此时 a= {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;
if (i == n-1) {
// 如果 i == n-1 说明,在 0...n-2 之间都没有 key,所以返回 -1
return -1;
} else {
// 否则,返回 i,就是等于 key 值的元素的下标
return i;
}
}
这个哨兵有什么好处呢?这段代码只是拿最后一个元素替换成要查找的元素,拿最后一个位置当“哨兵”,但和之前的i<n的循环比,也还是要比较到最后呀,好像没差。
它优化的是while循环的判断语句,第一段代码是在while中先判断下标是否在范围内,然后再判断该下标的值是否为我所想要的值;而第二段代码则直接判断值,然后循环+1下标。这就是它优化的点。
不过,这也让它可读性很差。。
多画图
对的,多画图!
对于链表的操作,如果在草稿纸中画出结点的状态、变化的顺序等,那你将很清晰地看到它是如何变化的,也就很容易理解它这做法。
markdown中不容易画图,这里只是简要记录一下。我在做链表的题目时,都是画画图就知道怎么做了。
LinkedList源码
我错了!我一直以为LinkedList里面是带头尾结点的双向链表,其实它是头尾指针的双向链表,两个指针分别指向的是第一个元素和最后一个元素,并且在增、删的时候进行特殊操作。这也能理解,毕竟是JDK,要效率,我之前是怎么自以为是头尾结点。。。
成员变量如下
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
发现它真的是挺多操作方法的,链表的两端都可以操作,看看它的UML图,知道它实现了Deque
接口。
可以看看它的头尾指针的增删是怎么做的,只有指针,它的操作肯定是繁琐的,不过空间上省了两个结点,对于JDK这样的常用集合类来说,还是值得的?
addFirst()与addLast()
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
public void addLast(E e) {
linkLast(e);
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
可以看到,在头、尾添加元素,只需改变头、尾指针的指向即可,操作非常方便。
我学习到了构造函数里面也能设置prev和next指针,之前没想到,还以为少了一些操作。
还有就是,不要忘了这是带头、尾指针的双向链表,在没有元素的时候,第一次插入元素要让两个指针都指向第一个元素。要是我写的话可能会忘了……
removeFirst()与removeLast()
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
同理了,就不粘了。
不过它代码写得确实精妙啊,我写不出来这么妙的代码,真是简洁又明了。
leetcode刷题
练习题LeetCode对应编号:206,141,21,19,876。
把它们都能做出来,链表的基本操作也就搞定了。
我确实也会做了,这算掌握得怎样啊?。。。依然感觉自己菜菜
206. 反转链表
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
141. 环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
return true;
}
}
return false;
}
}
21. 合并两个有序链表
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode sentinel = new ListNode(0);
ListNode cur = sentinel;
while(list1 != null && list2 != null){
if(list1.val <= list2.val){
cur.next = list1;
cur = list1;
list1 = list1.next;
}else{
cur.next = list2;
cur = list2;
list2 = list2.next;
}
}
if(list1 != null){
cur.next = list1;
}else{
cur.next = list2;
}
return sentinel.next;
}
}
19. 删除链表的倒数第 N 个结点
public ListNode removeNthFromEnd(ListNode head, int n) {
// 保证删除时不报空
if (head == null){
return null;
}
// 哨兵
ListNode sentinel = new ListNode(0);
sentinel.next = head;
ListNode slow = sentinel, fast = head;
// 先让快指针走n步
for(int i = 0;i < n;i++){
fast = fast.next;
}
// 与慢指针一同向前
// 当快指针走到结尾时,慢指针指向要删除元素的前一个
while(fast != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return sentinel.next;
}
876. 链表的中间结点
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.next;
}