乐趣区

关于java:23张图万字详解链表从小白到大佬

jiezi

链表和数组是数据类型中两个重要又罕用的根底数据类型，数组是间断存储在内存中的数据结构，因而它的劣势是能够通过下标迅速的找到元素的地位，而它的毛病则是在插入和删除元素时会导致大量元素的被迫挪动，为了解决和均衡此问题于是就有了链表这种数据类型。

链表和数组能够造成无效的互补，这样咱们就能够依据不同的业务场景抉择对应的数据类型了。那么，本文咱们就来重点介绍学习一下链表，一是因为它十分重要，二是因为面试面试必考，先来看本文的纲要：

看过某些抗日神剧咱们都晓得，某些秘密组织为了避免组织的成员被“一窝端”，通常会采纳上下级复线分割的形式来爱护其余成员，而这种“行为”则是链表的次要特色。

本文已收录至 Github《小白学算法》系列：https://github.com/vipstone/a…

简介

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

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

复杂度剖析

因为链表无需按顺序存储，因而链表在插入的时能够达到 O(1) 的复杂度，比程序表快得多，然而查找一个节点或者拜访特定编号的节点则须要 O(n) 的工夫，而程序表插入和查问的工夫复杂度别离是 O(log n) 和 O(1)。

优缺点剖析

应用链表构造能够克服数组链表须要事后晓得数据大小的毛病，链表构造能够充沛利用计算机内存空间，实现灵便的内存动静治理。然而链表失去了数组随机读取的长处，同时链表因为减少了结点的指针域，空间开销比拟大。

分类

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

  • 单向链表
  • 双向链表

  • 循环链表

    • 单循链表
    • 双循环链表

1. 单向链表

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

单链表的遍历方向繁多，只能从链头始终遍历到链尾。它的毛病是当要查问某一个节点的前一个节点时，只能再次从头进行遍历查问，因而效率比拟低，而双向链表的呈现恰好解决了这个问题。

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

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

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

2. 双向链表

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

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

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

    Node(Node<E> prev, E element, Node<E> 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<E> first;

    // 链表尾部
    transient Node<E> last;

    public LinkedList() {}

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

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

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

    // 删除尾部元素
    public E removeLast() {
        final Node<E> 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<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++;
    }

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

    // 清空链表
    public void clear() {for (Node<E> x = first; x != null;) {
            Node<E> 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<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> 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<E> 接口，add 办法属于 Collection<E> 的接口；
  • 当队列增加失败时，如果应用 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 < size; 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

链表应用场景

链表作为一种根本的物理构造，常被用来构建许多其它的逻辑构造，如堆栈、队列都能够基于链表实现。

所谓的物理构造是指能够将数据存储在物理空间中，比方数组和链表都属于物理数据结构；而逻辑构造则是用于形容数据间的逻辑关系的，它能够由多种不同的物理构造来实现，比方队列和栈都属于逻辑构造。

链表常见口试题

链表最常见的口试题就是链表的反转了，之前的文章《链表反转的两种实现办法，后一种击败了 100% 的用户！》咱们提供了 2 种链表反转的办法，而本文咱们再来裁减一下，提供 3 种链表反转的办法。

实现办法 1：Stack

咱们先用图解的形式来演示一下，应用栈实现链表反转的具体过程，如下图所示。

全副入栈：

因为栈是先进后出的数据结构，因而它的执行过程如下图所示：



最终的执行后果如下图所示：

实现代码如下所示：

public ListNode reverseList(ListNode head) {if (head == null) return null;
    Stack<ListNode> stack = new Stack<>();
    stack.push(head); // 存入第一个节点
    while (head.next != null) {stack.push(head.next); // 存入其余节点
        head = head.next; // 指针挪动的下一位
    }
    // 反转链表
    ListNode listNode = stack.pop(); // 反转第一个元素
    ListNode lastNode = listNode; // 长期节点，在上面的 while 中记录上一个节点
    while (!stack.isEmpty()) {ListNode item = stack.pop(); // 以后节点
        lastNode.next = item;
        lastNode = item;
    }
    lastNode.next = null; // 最初一个节点赋为 null（不然会造成死循环）return listNode;
}

LeetCode 验证后果如下图所示：

能够看出应用栈的形式来实现链表的反转执行的效率比拟低。

实现办法 2：递归

同样的，咱们先用图解的形式来演示一下，此办法实现的具体过程，如下图所示。





实现代码如下所示：

public static ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;
    // 从下一个节点开始递归
    ListNode reverse = reverseList(head.next);
    head.next.next = head; // 设置下一个节点的 next 为以后节点
    head.next = null; // 把以后节点的 next 赋值为 null，防止循环援用
    return reverse;
}

LeetCode 验证后果如下图所示：

能够看出这种实现办法在执行效率方面曾经满足咱们的需要了，性能还是很高的。

实现办法 3：循环

咱们也能够通过循环的形式来实现链表反转，只是这种办法无需反复调用本身办法，只须要一个循环就搞定了，实现代码如下：

class Solution {public ListNode reverseList(ListNode head) {if (head == null) return null;
        // 最终排序的倒序链表
        ListNode prev = null;
        while (head != null) {
            // 循环的下个节点
            ListNode next = head.next;
            // 反转节点操作
            head.next = prev;
            // 存储下个节点的上个节点
            prev = head;
            // 挪动指针到下一个循环
            head = next;
        }
        return prev;
    }
}

LeetCode 验证后果如下图所示：

从上述图片能够看出，应用此办法在工夫复杂度和空间复杂度上都是目前的最优解，比之前的两种办法更加现实。

总结

本文咱们讲了链表的定义，它是由数据域和指针域两局部组成的。链表可分为：单向链表、双向链表和循环链表，其中循环链表又能够分为单循链表和双循环链表。通过 JDK 的源码可知，Java 中的 LinkedList 其实是双向链表，咱们能够应用它来实现队列或者栈，最初咱们讲了反转链表的 3 种实现办法，心愿本文的内容对你有帮忙。

如果感觉有用请各位老爷多多点赞和分享，原创不易，谢谢您了！

文末福利：搜寻公众号「Java 中文社群」发送“面试”，支付最新的面试材料。

退出移动版