链表简介

链表,是存储空间不连续的线性表。在做题或者一些底层结构挺常见的,但是在开发中好像用得很少(可能我比较菜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;
}