查看: 200|回复: 0

什么是链表?

[复制链接]
发表于 2020-2-16 10:59:11 | 显示全部楼层 |阅读模式
在了解完什么是数据结构之后,让我们一起来探索下数据结构中常见的一种—链表
链表

链表是数据结构之一,此中的数据呈线性分列。在链表中,数据的添加和删除都较为方便,就是访问比力耗费时间

如上图所示就是链表的概念图,Blue、Yellow、Red 这 3 个字符串作为数据被存储于链表中,也就是数据域,每个数据都有 1 个指针,即指针域,它指向下一个数据的内存地址,此中 Red 是末了 1 个数据,Red 的指针不指向任何位置,也就是为 null,指向 NULL 的指针通常被称为空指针。

在链表中,数据一般都是分散存储于内存中的,无须存储在一连空间内。

因为数据都是分散存储的,所以如果想要访问数据,只能从第 1 个数据开始,顺着指针的指向一一往下访问(这便是次序访问)。比如,想要找到 Red 这一数据,就得从 Blue 开始访问,这之后,还要颠末 Yellow,我们才气找到 Red。

如果想要添加数据,只需要改变添加位置前后的指针指向就可以,非常简单。比如,在 Blue 和 Yellow 之间添加 Green。

起首将 Blue 的指针指向的位置酿成 Green,然后再把 Green 的指针指向 Yellow,数据的添加就大功告成了。

数据的删除也一样,只要改变指针的指向就可以,比如删除 Yellow。

这时,只需要把 Green 指针指向的位置从 Yellow 酿成 Red,删除就完成了。固然 Yellow 本身还存储在内存中,但是不管从那里都无法访问这个数据,所以也就没有特意去删除它的必要了。以后需要用到 Yellow 所在的存储空间时,只要用新数据覆盖掉就可以了。
那么对链表的操作所需的运行时间到底是多少呢?在这里,我们把链表中的数据量记成 n。访问数据时,我们需要从链表头部开始查找(线性查找),如果目标数据在链表末了的话,需要的时间就是 O(n)。
另外,添加数据只需要更改两个指针的指向,所以耗费的时间与 n 无关。如果已经到达了添加数据的位置,那么添加操作只需耗费 O(1)的时间,删除数据同样也只需 O(1)的时间。
链表的实现

在对链表有了大概的认识以后,我们用 Java 去实现属于自己的链表:
  1. public class ListNode {    int val;    ListNode next;    ListNode(int x) {        val = x;    }}class MyLinkedList {    int size;    /**     * 哨兵节点作为伪头     */    ListNode head;    public MyLinkedList() {        size = 0;        head = new ListNode(0);    }    /**     * 获取链表第 index 个节点的值。如果索引是无效的,返回-1     *     * @param index     * @return     */    public int get(int index) {        // 若索引无效        if (index < 0 || index >= size) {            return -1;        }        ListNode curr = head;        // 从伪头节点开始,向前走 index+1 步        for (int i = 0; i < index + 1; ++i) {            curr = curr.next;        }        return curr.val;    }    /**     * 在头部插入节点     *     * @param val     */    public void addAtHead(int val) {        addAtIndex(0, val);    }    /**     * 在尾部插入节点     *     * @param val     */    public void addAtTail(int val) {        addAtIndex(size, val);    }    /**     * 在链表中的第 index 个节点前添加值为 val 的一个节点。如果 index 即是链表的长度时,节点将被添加到链表的末尾。如果 index 大于链表长度,节点将无法插入     *     * @param index     * @param val     */    public void addAtIndex(int index, int val) {        // 如果index大于长度,则不会插入该节点。        if (index > size) {            return;        }        // 如果 index 为负,则该节点将插入列表的开头。        if (index < 0) {            index = 0;        }        ++size;        // 查找要添加的节点的前驱节点        ListNode pred = head;        for (int i = 0; i < index; ++i) {            pred = pred.next;        }        // 要添加的节点        ListNode toAdd = new ListNode(val);        // 通过改变 next 来插入节点        toAdd.next = pred.next;        pred.next = toAdd;    }    /**     * 如果 index 是有效的,删除链表中的第 index 个节点     *     * @param index     */    public void deleteAtIndex(int index) {        // 如果 index 无效,则不执行任何操作        if (index < 0 || index >= size) {            return;        }        size--;        // 找到要删除节点的前驱节点        ListNode pred = head;        for (int i = 0; i < index; ++i) {            pred = pred.next;        }        // 通过改变 next 来删除节点        pred.next = pred.next.next;    }}
复制代码
到这里,我相信各人应该对链表有了进一步的理解,各人可以用不同的语言去操持实现下。
链表扩展

以上讲述的链表是最基本的一种链表,除此之外,还存在几种扩展方便的链表。
固然上文中提到的链表在尾部没有指针,但我们也可以在链表尾部使用指针,并且让它指向链表头部的数据,将链表酿成环形,这便是循环链表,也叫环形链表。循环链表没有头和尾的概念,想要生存数目固定的最新数据时通常会使用这种链表。

另外,以上提到的链表里的每个数据都只有一个指针,但我们可以把指针设定为两个,并且让它们分别指向前后数据,这就是双向链表。使用这种链表,不但可以从前往后,还可以从后往前遍历数据,十分方便。
但是,双向链表存在两个缺点:一是指针数的增长会导致存储空间需求增长;二是添加和删除数据时需要改变更多指针的指向。

总结

看完之后,相信各人都对链表和链表的基本操作有了肯定的了解,还对循环链表和双向链表有了初步的认识,各人可以使用自己喜欢的语言去操持实现下单向链表,有本领的话可以把循环链表和双向链表也实现下。
说完链表,固然不能忘记经常和链表同时出现在面试官口中的—数组,将在接下来的文章对其举行展开介绍。
参考
《我的第一本算法书》

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?用户注册

x

天涯海角也要找到Ni:什么是链表?

中发现Ni: 什么是链表?
中发现Ni: 什么是链表?
中发现Ni: 什么是链表?
中发现Ni: 什么是链表?
中发现Ni: 什么是链表?
中发现Ni: 什么是链表?
相关技术服务需求,请联系管理员和客服QQ:2753533861或QQ:619920289
您需要登录后才可以回帖 登录 | 用户注册

本版积分规则

帖子推荐:
客服咨询

QQ:2753533861

服务时间 9:00-22:00

快速回复 返回顶部 返回列表