链表

一、定义

1.1 概念

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续

1.2 分类

  • 单向链表：每个元素只知道其下一个元素是谁
  • 双向链表：每个元素知道其上一个元素和下一个元素
  • 循环链表：通常的链表尾节点 tail 指向的都是 null，而循环链表的 tail 指向的是头节点 head
image.png

链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（ Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断。

随机访问性能
根据 index 查找，时间复杂度 O(n)

插入或删除性能

  • 起始位置：O(1)
  • 结束位置：如果已知 tail 尾节点是 O(1)，不知道 tail 尾节点是 O(n)
  • 中间位置：根据 index 查找时间 + O(1)

二、单向链表

2.1 定义

public class SinglyLinkedList {

    // 头节点
    private SingleNode head; 
    
     // 节点类
    static class SingleNode {
        private int value;
        private SingleNode next;
        public SingleNode(int value, SingleNode next) {
            this.value = value;
            this.next = next;
        }
    }
}
  • SingleNode 定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关心 Node 结构
  • 定义为 static 内部类，是因为 SingleNode 不需要与 SinglyLinkedList 实例相关，多个 SinglyLinkedList实例能共用 SingleNode 类定义

2.2 头部添加

    private static void addFirst(int value) {
        //链表为空
        // head = new SingleNode(value, null);
        //链表非空
        head = new SingleNode(value, head);
    }

2.3 遍历

public class SinglyLinkedList implements Iterable<Integer> {
    // .....
   /**
     * 遍历while
     */
    private static void loopWhile(Consumer<Integer> consumer) {
        SingleNode pointer = head;
        while (pointer != null) {
            consumer.accept(pointer.value);
            pointer = pointer.next;
        }
    }

    /**
     * 遍历for
     *
     * @param consumer
     */
    private static void loopFor(Consumer<Integer> consumer) {
        for (SingleNode pointer = head; pointer != null; pointer = pointer.next) {
            consumer.accept(pointer.value);
        }
    }

    /**
     * 递归遍历
     */
    private static void loopRecursion(Consumer<Integer> before, Consumer<Integer> after) {
        recursion(head, before, after);
    }

    private static void loop(SingleNode node) {
        if (node == null) {
            return;
        }
        System.out.println("before:" + node.value);
        loop(node.next);
        System.out.println("after:" + node.value);
    }

    /**
     * 递归调用
     * @param node
     * @param before
     * @param after
     */
    private static void recursion(SingleNode node, Consumer<Integer> before, Consumer<Integer> after) {
        if (node == null) {
            return;
        }
        before.accept(node.value);
        recursion(node.next, before, after);
        after.accept(node.value);
    }

    // 迭代器遍历
    private static class IntegerIterator implements Iterator<Integer> {
        // 指针
        SingleNode pointer = head;

        /**
         * 是否有下一个元素
         *
         * @return
         */
        @Override
        public boolean hasNext() {
            return pointer != null;
        }

        /**
         * 返回当前元素，并指向下一个元素
         *
         * @return
         */
        @Override
        public Integer next() {
            int value = pointer.value;
            pointer = pointer.next;
            return value;
        }
    }

以上遍历都可以把要做的事以 Consumer 函数的方式传递进来

  • Consumer 的规则是一个参数，无返回值，因此像 System.out::println 方法等都是 Consumer
  • 调用 Consumer 时，将当前节点 curr.value 作为参数传递给它

迭代器遍历：

  • hasNext 用来判断是否还有必要调用 next
  • next 做两件事
    • 返回当前节点的 value
    • 指向下一个节点

2.4 尾部添加

    /**
     * 尾插
     *
     * @param value
     */
    private static void addLast(int value) {
        SingleNode last = findLast();
        if (last == null) {
            addFirst(value);
        } else {
            last.next = new SingleNode(value, null);
        }
    }

    /**
     * 找到最后一个元素
     *
     * @return
     */
    private static SingleNode findLast() {
        if (head == null) {
            return null;
        }
        SingleNode pointer = head;
        while (pointer.next != null) {
            pointer = pointer.next;
        }
        return pointer;
    }

2.5 根据索引获取元素

    /**
     * 根据索引获取节点值
     *
     * @param index
     * @return
     */
    public static int getNodeVal(int index) {
        SingleNode node = findNode(index);
        if (node == null) {
            throw new IllegalArgumentException(String.format("index [%d] 不合法 %n", index));
        }
        return node.value;
    }

    /**
     * 根据索引查找节点
     *
     * @param index
     * @return
     */
    private static SingleNode findNode(int index) {
        int i = 0;
        for (SingleNode pointer = head; pointer != null; pointer = pointer.next, i++) {
            if (i == index) {
                return pointer;
            }
        }
        return null;
    }

2.6 插入元素（任意位置）

    /**
     * 往对应位置index插入元素
     *
     * @param index
     * @param val
     */
    private static void addByIndex(int index, int val) {
        if (index == 0) {
            addFirst(val);
        } else {
            //获取当前要插入的索引的上一个元素
            SingleNode pre = findNode(index - 1);
            if (pre == null) {
                throw new IllegalArgumentException(String.format("index [%d] 不合法 %n", index));
            }
            pre.next = new SingleNode(val, pre.next);
        }
    }

2.7 删除元素

    /**
     * 删除第一个节点
     */
    public static void removeFirst() {
        if (head == null) {
            throw new IllegalArgumentException("没有可删除的节点");
        }
        head = head.next;
    }

    /**
     * 按照索引删除对应的节点
     * @param index
     */
    public static void remove(int index) {
        if (index == 0) {
            removeFirst();
        } else {
            SingleNode pre = findNode(index - 1);
            if (pre == null || pre.next == null) {
                throw new IllegalArgumentException("没有可删除的节点");
            }
            pre.next = pre.next.next;
        }
    }

2.8 带哨兵的单向链表操作

public class SentinelSingleLinkedList implements Iterable<Integer> {

    /**
     * 让头指针指向哨兵节点 减少非空判断
     */
    private static SingleNode head = new SingleNode(-1,null);

    @Override
    public Iterator<Integer> iterator() {
        return new IntegerIterator();
    }

    static class SingleNode {

        private int value;

        private SingleNode next;

        public SingleNode(int value, SingleNode next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 头插
     *
     * @param value
     */
    private static void addFirst(int value) {
        //链表为空
        // head = new SingleNode(value, null);
        //链表非空
        // head = new SingleNode(value, head);
        addByIndex(0, value);
    }


    /**
     * 尾插
     *
     * @param value
     */
    private static void addLast(int value) {
        SingleNode last = findLast();
//        if (last == null) {
//            addFirst(value);
//        } else {
        last.next = new SingleNode(value, null);
//        }
    }

    /**
     * 根据索引查找节点
     *
     * @param index
     * @return
     */
    private static SingleNode findNode(int index) {
        int i = -1;
        for (SingleNode pointer = head; pointer != null; pointer = pointer.next, i++) {
            if (i == index) {
                return pointer;
            }
        }
        return null;
    }

    /**
     * 往对应位置index插入元素
     *
     * @param index
     * @param val
     */
    private static void addByIndex(int index, int val) {
//        if (index == 0) {
//            addFirst(val);
//        } else {
        //获取当前要插入的索引的上一个元素
        SingleNode pre = findNode(index - 1);
        if (pre == null) {
            throw new IllegalArgumentException(String.format("index [%d] 不合法 %n", index));
        }
        pre.next = new SingleNode(val, pre.next);
//        }
    }

    /**
     * 根据索引获取节点值
     *
     * @param index
     * @return
     */
    public static int getNodeVal(int index) {
        SingleNode node = findNode(index);
        if (node == null) {
            throw new IllegalArgumentException(String.format("index [%d] 不合法 %n", index));
        }
        return node.value;
    }

    /**
     * 删除第一个节点
     */
    public static void removeFirst() {
//        if (head == null) {
//            throw new IllegalArgumentException("没有可删除的节点");
//        }
//        head = head.next;
        remove(0);
    }

    /**
     * 按照索引删除对应的节点
     * @param index
     */
    public static void remove(int index) {
//        if (index == 0) {
//            removeFirst();
//        } else {
            SingleNode pre = findNode(index - 1);
            if (pre == null || pre.next == null) {
                throw new IllegalArgumentException("没有可删除的节点");
            }
            pre.next = pre.next.next;
//        }
    }

    /**
     * 遍历while
     */
    private static void loopWhile(Consumer<Integer> consumer) {
        SingleNode pointer = head.next;
        while (pointer != null) {
            consumer.accept(pointer.value);
            pointer = pointer.next;
        }
    }

    /**
     * 遍历for
     *
     * @param consumer
     */
    private static void loopFor(Consumer<Integer> consumer) {
        for (SingleNode pointer = head.next; pointer != null; pointer = pointer.next) {
            consumer.accept(pointer.value);
        }
    }

    /**
     * 找到最后一个元素
     *
     * @return
     */
    private static SingleNode findLast() {
        // 因为头指针指向的是哨兵 所以不会为空
//        if (head == null) {
//            return null;
//        }
        SingleNode pointer = head;
        while (pointer.next != null) {
            pointer = pointer.next;
        }
        return pointer;
    }
}

三、双向链表

带哨兵的双向链表

public class SentinelDoubleLinkedList implements Iterable<Integer> {

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            DoubleNode pointer = head.next;

            @Override
            public boolean hasNext() {
                return pointer != tail;
            }

            @Override
            public Integer next() {
                Integer value = pointer.value;
                pointer = pointer.next;
                return value;
            }
        };
    }

    static class DoubleNode {
        DoubleNode pre;
        int value;
        DoubleNode next;

        public DoubleNode(DoubleNode pre, int value, DoubleNode next) {
            this.pre = pre;
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 头哨兵
     */
    private static DoubleNode head;

    /**
     * 尾哨兵
     */
    private static DoubleNode tail;

    public SentinelDoubleLinkedList() {
        head = new DoubleNode(null, -1, null);
        tail = new DoubleNode(null, -2, null);
        head.next = tail;
        tail.pre = head;
    }

    /**
     * 根据索引查找节点
     *
     * @param index
     * @return
     */
    private static DoubleNode findNodeByIndex(int index) {
        int i = -1;
        for (DoubleNode pointer = head; pointer != tail; i++, pointer = pointer.next) {
            if (i == index) {
                return pointer;
            }
        }
        return null;
    }

    /**
     * 根据索引位置插入值
     *
     * @param index
     * @param value
     */
    private static void addByIndex(int index, int value) {
        //找到要插入的上一个节点
        DoubleNode pre = findNodeByIndex(index - 1);
        if (pre == null) {
            throw new IllegalArgumentException();
        }
        DoubleNode next = pre.next;
        //要插入的新节点
        DoubleNode node = new DoubleNode(pre, value, next);
        pre.next = node;
        next.pre = node;
    }

    /**
     * 从头部添加节点
     *
     * @param value
     */
    private static void addFirst(int value) {
        addByIndex(0, value);
    }

    /**
     * 从尾部添加节点
     *
     * @param value
     */
    private static void addLast(int value) {
        // 最后一个节点
        DoubleNode last = tail.pre;
        DoubleNode node = new DoubleNode(last, value, tail);
        last.next = node;
        tail.pre = node;
    }

    /**
     * 删除第一个节点
     */
    public void removeFirst() {
        removeByIndex(0);
    }

    /**
     * 删除最后一个节点
     */
    public void removeLast() {
        if (tail.pre == head) {
            throw new IllegalArgumentException();
        }
        // 最后一个节点的前一个节点
        DoubleNode node = tail.pre.pre;
        node.next = tail;
        tail.pre = node;
    }

    /**
     * 按索引删除节点
     *
     * @param index
     */
    public void removeByIndex(int index) {
        // 要删除的上一个
        DoubleNode pre = findNodeByIndex(index - 1);
        // 找不到pre或者要删除的是尾哨兵的时候
        if (pre == null || pre.next == tail) {
            throw new IllegalArgumentException();
        }
        // 要删除的下一个
        DoubleNode next = pre.next.next;

        pre.next = next;
        next.pre = pre;
    }
}

四、双向环形链表

哨兵既作为头，也作为尾

image.png

带哨兵的双向环形链表

public class SentinelDoubleCircularLinkedList implements Iterable<Integer> {

    // 哨兵节点
    private static DoubleCircularNode sentinel = new DoubleCircularNode(null, -1, null);

    public SentinelDoubleCircularLinkedList() {
        sentinel.pre = sentinel;
        sentinel.next = sentinel;
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {

            DoubleCircularNode pointer = sentinel.next;

            @Override
            public boolean hasNext() {
                return pointer != sentinel;
            }

            @Override
            public Integer next() {
                Integer value = pointer.value;
                pointer = pointer.next;
                return value;
            }
        };
    }

    private static class DoubleCircularNode {
        DoubleCircularNode pre;
        int value;
        DoubleCircularNode next;

        public DoubleCircularNode(DoubleCircularNode pre, int value, DoubleCircularNode next) {
            this.pre = pre;
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 从头部添加节点
     */
    private static void addFirst(int value) {
        //前驱
        DoubleCircularNode pre = sentinel;
        // 后继
        DoubleCircularNode next = sentinel.next;
        DoubleCircularNode node = new DoubleCircularNode(pre, value, next);

        pre.next = node;
        next.pre = node;
    }

    /**
     * 从尾部添加节点
     *
     * @param value
     */
    private static void addLast(int value) {
        DoubleCircularNode node = new DoubleCircularNode(sentinel.pre, value, sentinel);
        sentinel.pre.next = node;
        sentinel.pre = node;
    }

    /**
     * 从头部删除节点
     */
    private static void removeFirst() {
        //要删除的元素
        DoubleCircularNode remove = sentinel.next;
        if (remove == sentinel) {
            throw new IllegalArgumentException();
        }
        sentinel.next = remove.next;
        remove.next.pre = sentinel;
    }

    /**
     * 从尾部删除节点
     */
    private static void removeLast() {
        //要删除的节点
        DoubleCircularNode remove = sentinel.pre;
        if (remove == sentinel) {
            throw new IllegalArgumentException();
        }
        remove.pre.next = sentinel;
        sentinel.pre = remove.pre;
    }

    /**
     * 根据值删除对应的节点
     */
    private static void removeByValue(int value) {
        //要删除的节点
        DoubleCircularNode remove = findByValue(value);
        if (remove == null) {
            return;
        }
        remove.pre.next = remove.next;
        remove.next.pre = remove.pre;
    }

    /**
     * 根据值查找节点
     *
     * @return
     */
    private static DoubleCircularNode findByValue(int value) {
        DoubleCircularNode pointer = sentinel.next;
        while (pointer != sentinel) {
            if (pointer.value == value) {
                return pointer;
            }
            pointer = pointer.next;
        }
        return null;
    }

}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,651评论 6赞 501
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,468评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,931评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,218评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,234评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,198评论 1赞 299
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,084评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,926评论 0赞 274
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,341评论 1赞 311
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,563评论 2赞 333
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,731评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,430评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,036评论 3赞 326
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,676评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,829评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,743评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,629评论 2赞 354

推荐阅读更多精彩内容

  • Java数据结构——链表
    2.2 链表 概述 定义 在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续...
    康小庄阅读 1,012评论 0赞 1
  • 一文搞懂链表
    链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个...
    人月神话Lee阅读 158评论 0赞 0
  • 2021-02-28 数组、链表、跳表
    线性表 定义：线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、...
    竹blue阅读 320评论 0赞 0
  • 链表
    一、什么是链表？ 和数组一样，链表也是一种线性表。 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散...
    蹩脚的小三阅读 1,034评论 0赞 0
  • Redis数据结构——链表
    前言 Redis链表为双向无环链表！ Redis使用了简单动态字符串，链表、字典(散列表)、跳跃表、整数集合、压缩...
    小波同学阅读 512评论 0赞 4