『数据结构与算法』—— 链表

底层存储结构

与 数组 对比，数组需要一块 连续的内存空间 来存储，对内存要求很高。如果我们申请 50MB 的内存，即便内存的剩余内存大于 50MB，但是如果内存不是连续的，也是很有可能申请失败。

而 链表 与之相反，它并不需要一块连续的内存，通过 指针 将一组 零散的内存块 串联起来使用。

下面的图片可以看出两者之间的区别：

image

链表分类

单链表

单链表每个节点有两部分组成，数据 和 后继指针 next 。

image

第一个节点称为 头结点， 最后一个节点称为 尾节点 ，尾节点 next 指向 null。链表的插入增加和删除，不需要移动，只需要改变前后节点 next 的指针即可实现。

image

但是，如果需要访问第 N 个元素，则需要时间复杂度为 O(n) 。

循环链表

循环链表是从链尾直接连接到链头。

image

双向链表

相比于单链表，双向链表具有两个节点：前继节点和后继节点。

image

LRU 缓存淘汰算法

维护一个有序单链表，越靠近链尾的节点是越早访问的，当有一个新的数据访问时，我们从链表头部开始顺序遍历链表。

  1. 如果该数据已经存在于链表中，那么遍历拿个这个数据的节点删除，并将新的插入到头部。
  2. 如果此数据没有再缓存链表中：
    1. 如果缓存未满，则直接将该节点插入链表的头部
    2. 如果此时链表已满，则链表尾节点删除，将新的数据节点插入到链表的头部。

链表小总结

说一句尴尬的话，本人大学的时候也是挂了 算法与数据结构 这门课，说实话，对算法也是有一点阴影，总感觉自己会学不好。就拿写链表而言，经常被引用的移动产生误解，在过程中经常不知道指针移到到哪了，导致并不会实现自己预期想要的结果。其实练习题做下来还是蛮有感触的，还是要多练习，从中可以找到一些技巧，下面总结一下：

理解指针或引用的含义

对于我这个学习 Java 的而言，其实就是要理解引用的含义。

将某个变量赋值给引用，实际上是将这个变量的地址赋值给该引用，或者反过来说，引用中存储了这个变量的内存地址，指向了这个变量，通过这个指针就能找到这个变量。

例子

Node node1 = new Node(null, 1);
node1 = new Node(null, 2);
Node node2 = new Node(null, 3);
node1 = node2;
node1.value = 3;

只要是 node = 引用后面直接跟上等于，那就证明只是单纯的将这个引用指向另一个内存地址，并不会影响任何变量的值。而如果 node. 引用通过 . 的方式，那么他的值就有变化的可能。

警惕引用丢失和内存泄漏

image

比如链表插入节点操作。

Node targetNode = new Node(null, 1); // 待被插入的节点
Node preNode; // 已经被找到插入前一个节点

错误示范：

preNode.next = targetNode;
targeNode.next = preNode.next.next;

这里现将前节点指向目标节点，然后目标节点再指向前节点的下下个节点，意思是没有错误，但是会导致后节点以及之后都会被丢失。

正确的做法应该是：

targetNode.next = preNode.next.next;
preNode.next = targeNode;

虽然仅仅是调换了顺序，就会产生不同的结果。同样删除节点时，也要记得手动释放内存。

利用哨兵简化实现难度

针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。

重点留意边界条件处理

  1. 如果链表为空，代码是否能正常工作
  2. 如果链表只包含一个节点，代码是否能正常工作
  3. 如果链表只包含两个节点，代码是否能正常工作
  4. 代码逻辑在处理头结点和尾节点的时候，代码是否能正常工作

举例画图，辅助思考

我平常在做练习题时，身边必备一张纸和一纸笔，对特殊的逻辑进行画图举例演示，很大程度上可以帮助自己理清逻辑。

多写多练

多多练习吧！

下面写几个练习题

代码实现单链列表

class SinglyLinkedList {

    private Node head = null;

    void insertToHead(Node node) {
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            head = node;
        }
        System.out.println("insert head " + node.value + " data:\t" + toString());
    }

    void insertToHead(int value) {
        insertToHead(createNode(value));
    }

    void insertAfter(Node node, Node newNode) {
        if (node == null) return;
        newNode.next = node.next;
        node.next = newNode;
        System.out.println("insertAfter data:\t" + toString());
    }

    void insertAfter(Node node, int value) {
        insertAfter(node, createNode(value));
    }

    void insertBefore(Node before, Node newNode) {
        if (before == null) return;
        if (head == before) {
            insertToHead(newNode);
            return;
        }
        Node temp = head;
        while (temp != null && temp.next != before) {
            // 直到找打 before 的上个节点
            temp = temp.next;
        }
        newNode.next = before;
        temp.next = newNode;
        System.out.println("insertBefore data:\t" + toString());
    }

    void insertBefore(Node before, int value) {
        insertBefore(before, createNode(value));
    }

    Node findByValue(int value) {
        Node temp = head;
        while (temp != null && temp.value != value) {
            temp = temp.next;
        }
        return temp;
    }

    Node findByIndex(int index) {
        Node temp = head;
        int pos = 0;
        while (temp != null && pos != index) {
            temp = temp.next;
            pos++;
        }
        return temp;
    }

    void insertLast(Node node) {
        if (head == null) {
            head = node;
            System.out.println("insert last " + node.value + " data:\t" + toString());
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
        System.out.println("insert last " + node.value + " data:\t" + toString());
    }

    void insertLast(int value) {
        insertLast(createNode(value));
    }

    private Node createNode(int value) {
        return new Node(null, value);
    }

    void deleteByValue(int value) {
        if (head == null) {
            return;
        }
        Node before = null;
        Node current = head;
        while (current != null && current.value != value) {
            before = current;
            current = current.next;
        }
        if (current == null) {
            return;
        }
        if (before == null) {
            head = head.next;
        } else {
            before.next = current.next;
        }
        System.out.println("deleteByValue:\t" + toString());
    }

    void deleteByNode(Node node) {
        if (head == null || node == null) {
            return;
        }
        Node temp = head;
        while (temp != null && temp.next != node) {
            temp = temp.next;
        }
        temp.next = node.next;
        System.out.println("deleteByNode:\t" + toString());
    }


    @Override
    public String toString() {
        Node temp = head;
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        while (temp != null) {
            sb.append(temp.value).append(",");
            temp = temp.next;
        }
        sb.append("]");
        return sb.toString();
    }

    static class Node {
        int value;
        Node next;

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

        int getData() {
            return value;
        }
    }

    public static void main(String[] args) {
        SinglyLinkedList linkedList = new SinglyLinkedList();
        linkedList.insertLast(1);
        linkedList.insertLast(2);
        linkedList.insertLast(3);
        linkedList.insertLast(4);
        linkedList.insertToHead(5);
        linkedList.insertAfter(linkedList.findByValue(3), 6);
        linkedList.insertBefore(linkedList.findByValue(1), 7);

        linkedList.deleteByValue(2);
        linkedList.deleteByNode(linkedList.findByValue(1));

    }

}

输出结果：

insert last 1 data: [1,]
insert last 2 data: [1,2,]
insert last 3 data: [1,2,3,]
insert last 4 data: [1,2,3,4,]
insert head 5 data: [5,1,2,3,4,]
insertAfter data:   [5,1,2,3,6,4,]
insertBefore data:  [5,7,1,2,3,6,4,]
deleteByValue:  [5,7,1,3,6,4,]
deleteByNode:   [5,7,3,6,4,]

判断是否为回文数

核心思想：使用两个指针，一个慢指针，每次移动一个节点，一个快指针，每次移动两个节点。

private boolean isPalindrome() {
        if (head == null || head.next == null) {
            return false;
        }
        Node pre = null;
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            // 快指针每次跳两个
            fast = fast.next.next;
            // 临时指针指向下个节点
            Node temp = slow.next;
            // 将 slow 回转
            slow.next = pre;
            pre = slow;
            slow = temp;
        }
        if (fast != null) {
            // 这种代表着节点数为偶数，slow 需要往后移动一位
            slow = slow.next;
        }
        while (slow != null && pre != null) {
            if (slow.value != pre.value) {
                return false;
            }
            slow = slow.next;
            pre = pre.next;
        }
        return true;
    }

输出结果

insert last 1 data: [1,]
insert last 2 data: [1,2,]
insert last 2 data: [1,2,2,]
insert last 1 data: [1,2,2,1,]
是否为回文函数:    true

节点回转

核心思想：每次遍历时，回转节点的逻辑操作顺序，且看代码

    private static Node reversed(Node node) {
        if (node.next == null) {
            return node;
        }
        Node pre = null;
        while (node != null) {
            // 现将下个节点用 temp 保存下来
            Node temp = node.next;
            node.next = pre;
            pre = node;
            node = temp;
        }
        return pre;
    }

输出结果：

01234

43210

判断是否是循环节点

核心思想：循环节点的特点就在于链表的尾部指向头部，只需要是用快慢节点进行遍历，如果不是循环节点，循环一次就结束了。

    /**
     * 判断是否是循环链表
     * 快慢节点，如果两者相等必然是循环链表，时间复杂度为 O(n)
     */
    private static boolean isCircle(Node node) {
        int count = 0;
        Node slow = node;
        Node fast = node;
        while (slow != null && fast != null && fast.next != null) {
            count++;
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                System.out.println("循环了 " + count + "次");
                return true;
            }
        }
        System.out.println("循环了 " + count + "次");
        return false;
    }

输出结果

循环了 5次
is circle:  true

拼接两个有序节点

核心思想：首先创建一个空的头节点，然后两个有序链表依次遍历，谁小就把这个空节点指向谁(默认从小到大排序)。其中需要注意的是，如果一个节点提前结束了，那么就需要将新节点直接指向剩下的那个节点。

    private static Node mergeNode(Node aNode, Node bNode) {
        Node head = new Node(null, -1);
        Node tail = head;
        if (aNode == null) {
            head = bNode;
        }
        if (bNode == null) {
            head = aNode;
        }

        while (aNode != null && bNode != null) {
            if (aNode.value > bNode.value) {
                tail.next = bNode;
                bNode = bNode.next;
            } else {
                tail.next = aNode;
                aNode = aNode.next;
            }
            tail = tail.next;
        }
        if (aNode == null) {
            tail.next = bNode;
        }
        if (bNode == null) {
            tail.next = aNode;
        }
        if (head == null) {
            return null;
        }
        return head.next;
    }

输出结果：

A 节点:   135

B 节点:   24689

12345689

删除倒数第 N 个节点

核心思想：快慢指针，快的比慢 的多 N 个，遍历到最后，慢节点指向倒数第 N 个节点，然后直接进行删除。

    /**
     * 删除倒数 N 个节点
     *
     */
    private static void deleteLast(Node node, int n) {
        int count = 0;
        Node head = node;
        while (head != null) {
            count ++;
            head = head.next;
        }
        if (n > count) {
            return;
        }
        if (n == count) {
            if (n == 1) {
                node.next = null;
            } else {
                node.value = node.next.value;
                node.next = node.next.next;
            }
            return;
        }
        Node slow = node;
        Node fast = node;
        int tempCount = 0;
        while (slow != null && fast.next != null) {
            if (tempCount < n) {
                tempCount ++;
            } else {
                slow = slow.next;
            }
            fast = fast.next;
        }
        slow.next = slow.next.next;
    }

输出结果：

01234567

0124567

找出中间节点

核心思想：直接使用快慢指针进行遍历，慢指针每次移动一个，快指针每次移动两个。

    private static int findMiddleNode(Node node) {
        Node fast = node;
        Node slow = node;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow.value;
    }

输出结果：

01234567

4

参考自极客时间

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