专栏名称: 吴师兄学算法
和程序员小吴一起从初学者的角度学习算法，以动画的形式呈现解题的思路。每周四篇原创文章，期待你的鉴赏！
目录
相关文章推荐
三联生活周刊  ·  分享欲不对等，令我的八年友谊陷入危机 ·  22 小时前  
读者  ·  晚安一句话 ·  2 天前  
三联生活周刊  ·  开年王炸英剧，揭开了顶流女作家的“历史悬案” ·  2 天前  
三联生活周刊  ·  孩子不想上学，我们该怎么办？ ·  2 天前  
新周刊  ·  网文世界里，TA们讲着“脑洞成金”的故事 ·  3 天前  
51好读  ›  专栏  ›  吴师兄学算法

23张图！万字详解「链表」，从小白到大佬！

吴师兄学算法  · 公众号  ·  · 2020-12-26 20:00

正文


链表和数组是数据类型中两个重要又常用的基础数据类型。

数组是连续存储在内存中的数据结构，因此它的优势是可以通过下标迅速的找到元素的位置，而它的缺点则是在插入和删除元素时会导致大量元素的被迫移动，为了解决和平衡此问题于是就有了链表这种数据类型。

链表和数组可以形成有效的互补，这样我们就可以根据不同的业务场景选择对应的数据类型了。
那么，本文我们就来重点介绍学习一下链表，一是因为它非常重要，二是因为面试必考，先来看本文大纲：

看过某些抗日神剧我们都知道，某些秘密组织为了防止组织的成员被“一窝端”，通常会采用上下级单线联系的方式来保护其他成员，而这种“行为”则是链表的主要特征。

简介

链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。

链表是由数据域和指针域两部分组成的 ，它的组成结构如下：

复杂度分析

由于链表无需按顺序存储，因此链表在插入的时可以达到 O(1) 的复杂度，比顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间，而顺序表插入和查询的时间复杂度分别是 O(log n) 和 O(1)。

优缺点分析

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

分类

链表通常会分为以下三类：

  • 单向链表
  • 双向链表
  • 循环链表
    • 单循链表
    • 双循环链表

1.单向链表

链表中最简单的一种是单向链表，或叫单链表，它包含两个域，一个数据域和一个指针域，指针域用于指向下一个节点，而最后一个节点则指向一个空值，如下图所示：

单链表的遍历方向单一，只能从链头一直遍历到链尾。 它的缺点是当要查询某一个节点的前一个节点时，只能再次从头进行遍历查询，因此效率比较低，而双向链表的出现恰好解决了这个问题。

接下来，我们用代码来实现一下单向链表的节点： 

private static class Node<E> {
    E item;
    Node next;

    Node(E element, Node next) {
        this.item = element;
        this.next = next;
    }
}

2.双向链表

双向链表也叫双面链表，它的每个节点由三部分组成：prev 指针指向前置节点，此节点的数据和 next 指针指向后置节点，如下图所示：

接下来，我们用代码来实现一下双向链表的节点： 

private static class Node<E> {
    E item;
    Node next;
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

3.循环链表

循环链表又分为单循环链表和双循环链表，也就是将单向链表或双向链表的首尾节点进行连接，这样就实现了单循环链表或双循环链表了，如下图所示：

Java中的链表

学习了链表的基础知识之后， 我们来思考一个问题：Java 中的链表 LinkedList 是属于哪种类型的链表呢？单向链表还是双向链表？

要回答这个问题，首先我们要来看 JDK 中的源码，如下所示： 

package java.util;

import java.util.function.Consumer;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
 // 链表大小
    transient int size = 0;

    // 链表头部
    transient Node first;

    // 链表尾部
    transient Node last;

    public LinkedList() {
    }

    public LinkedList(Collection extends E> c) {
        this();
        addAll(c);
    }
 
    // 获取头部元素
    public E getFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    // 获取尾部元素
    public E getLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    // 删除头部元素
    public E removeFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    // 删除尾部元素
    public E removeLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    // 添加头部元素
    public void addFirst(E e) {
        linkFirst(e);
    }
    
    // 添加头部元素的具体执行方法
    private void linkFirst(E e) {
        final Node f = first;
        final Node 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 l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    // 查询链表个数
    public int size() {
        return size;
    }

    // 清空链表
    public void clear() {
        for (Node x = first; x != null; ) {
            Node next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }
  
    // 根据下标获取元素
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    private static class Node<E> {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    // 忽略其他方法......
}

从上述节点 Node 的定义可以看出： LinkedList 其实是一个双向链表 ，因为它定义了两个指针 next 和 prev 分别用来指向自己的下一个和上一个节点。

链表常用方法

LinkedList 的设计还是很巧妙的，了解了它的实现代码之后，下面我们来看看它是如何使用的？或者说它的常用方法有哪些。

1.增加

接下来我们来演示一下增加方法的使用： 

public class LinkedListTest {
    public static void main(String[] a) {
        LinkedList list = new LinkedList();
        list.add("Java");
        list.add("中文");
        list.add("社群");
        list.addFirst("头部添加"); // 添加元素到头部
        list.addLast("尾部添加");  // 添加元素到最后
        System.out.println(list);
    }
}

以上代码的执行结果为：

[头部添加, Java, 中文, 社群, 尾部添加]

出来以上的 3 个增加方法之外， LinkedList 还包含了其他的添加方法，如下所示：

  • add(int index, E element)：向指定位置插入元素；
  • offer(E e)：向链表末尾添加元素，返回是否成功；
  • offerFirst(E e)：头部插入元素，返回是否成功；
  • offerLast(E e)：尾部插入元素，返回是否成功。

add 和 offer 的区别

它们的区别主要体现在以下两点：

  • offer 方法属于 Deque 接口，add 方法属于 Collection 的接口；
  • 当队列添加失败时，如果使用 add 方法会报错，而 offer 方法会返回 false。

2.删除

删除功能的演示代码如下： 

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] a) {
        LinkedList list = new LinkedList();
        list.offer("头部");
        list.offer("中间");
        list.offer("尾部");

        list.removeFirst(); // 删除头部元素
        list.removeLast();  // 删除尾部元素

        System.out.println(list);
    }
}

以上代码的执行结果为：

[中间]

除了以上删除方法之外，更多的删除方法如下所示：

  • clear()：清空链表；
  • removeFirst()：删除并返回第一个元素；
  • removeLast()：删除并返回最后一个元素；
  • remove(Object o)：删除某一元素，返回是否成功；
  • remove(int index)：删除指定位置的元素；
  • poll()：删除并返回第一个元素；
  • remove()：删除并返回第一个元素。

3.修改

修改方法的演示代码如下： 

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] a) {
        LinkedList list = new LinkedList();
        list.offer("Java");
        list.offer("MySQL");
        list.offer("DB");
        
        // 修改
        list.set(2, "Oracle");

        System.out.println(list);
    }
}

以上代码的执行结果为：

[Java, MySQL, Oracle]

4.查询

查询方法的演示代码如下： 

import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] a) {
        LinkedList list = new LinkedList();
        list.offer("Java");
        list.offer("MySQL");
        list.offer("DB");

        // --- getXXX() 获取 ---
        // 获取最后一个
        System.out.println(list.getLast());
        // 获取首个
        System.out.println(list.getFirst());
        // 根据下标获取
        System.out.println(list.get(1));

        // peekXXX() 获取
        System.out.println("--- peek() ---");
        // 获取最后一个
        System.out.println(list.peekLast());
        // 获取首个
        System.out.println(list.peekFirst());
        // 根据首个
        System.out.println(list.peek());
    }
}

以上代码的执行结果为：

DB

Java

MySQL

--- peek() ---

DB

Java

Java

5.遍历

LinkedList 的遍历方法包含以下三种。

遍历方法一： 

for (int size = linkedList.size(), i = 0; i     System.out.println(linkedList.get(i));
}

遍历方法二： 

for (String str: linkedList) {
    System.out.println(str);
}

遍历方法三： 

Iterator iter = linkedList.iterator();
while (iter.hasNext()) {
    System.out.println(iter.next());
}

链表应用：队列 & 栈

1.用链表实现栈

接下来我们用链表来实现一个先进先出的“队列”，实现代码如下： 

LinkedList list = new LinkedList();
// 元素入列
list.add("Java");
list.add("中文");
list.add("社群");

while (!list.isEmpty()) {
    // 打印并移除队头元素
    System.out.println(list.poll());
}

以上程序的执行结果如下：

Java

中文

社群


2.用链表实现队列

然后我们用链表来实现一个后进先出的“栈”，实现代码如下： 

LinkedList list = new LinkedList();
// 元素入栈
list.add("Java");
list.add("中文");
list.add("社群");

while (!list.isEmpty()) {
    // 打印并移除栈顶元素
    System.out.println(list.pollLast());
}

以上程序的执行结果如下：

社群

中文

Java


链表使用场景







请到「今天看啥」查看全文


推荐文章
三联生活周刊  ·  分享欲不对等，令我的八年友谊陷入危机
22 小时前
读者  ·  晚安一句话
2 天前
三联生活周刊  ·  开年王炸英剧，揭开了顶流女作家的“历史悬案”
2 天前
三联生活周刊  ·  孩子不想上学，我们该怎么办？
2 天前
新周刊  ·  网文世界里，TA们讲着“脑洞成金”的故事
3 天前
21世纪经济报道  ·  【夜读】对自己有要求的人，运气都不会太差
8 年前
桃叭啦  ·  【叮】原价¥18生命线首次限免，还有把爱豆装进通知栏的小插件！
8 年前
哈哈搞笑视频  ·  农村妇女卖豆腐，笑喷！
7 年前
V保险  ·  保险真奇怪：出事了都想买，想买了买不了！一首打油诗告诉你保险的好…
7 年前
湖南日报  ·  湖南抗击历史罕见特大洪水纪实四｜总有一种情怀温暖人心
7 年前
Sov5搜索   ·   小百科   ·   今天看啥   ·   移动版
51好读 - 好文章就要读起来!