1. 速盾网络Home
  2. 网站运维

什么是链表结构（什么是链表中的节点）

小道研究 • • 网站运维

数组、对象这些数据结构我们经常使用，之前听说过「链表」这种数据结构，一直不太理解，这些天终于有时间来看一下「链表」到底是什么？

怎么会想起做「链表」呢？因为一直在 Leetcode 上刷题（查看原文获取链接）先从最简单的刷起，写过了一些数组、字符串什么的，然后就刷到了「链表」题。做了两道「链表」题后，想来梳理一下。
什么是链表？
链表是一种数据结构。
数据结构有很多种，栈、队列、数组、对象、哈希表、树、图，这些都属于数据结构中的一种，只是它们的表现方式不一样。
链表没有现成的语法表示，需要结合 Class 类来生成，每次添加节点的时候都需要向类里添加。

链表里最简单的就是「单链表」，第一个节点是 head，每个节点都有两个属性，一个是 data ，一个是 next 。data 是当前节点的数据，next 指向下一个节点的指针，最后一个节点指向 null 空指针。上图：

来源 Leetcode 设计链表

链表为何而生？
数组是需要一段连续的空间的，其次是插入或者删除元素的时候，也需要去移动其他元素的内存地址，数组有索引的特征，每次操作，内存地址都会移动，所以，操作起来，性能较低。
既然数组有索引的限制，我们可以用对象啊，对象是根据 key 来处理元素的，虽然在添加或者删除元素时，对象操作很快。对象的存储位置是随机的，在迭代的时候，性能较低。
所以，引出了链表。链表不需要连续的空间，添加和删除元素时性能较好。
链表有什么缺点？
内存空间占用大，每个节点都需要存储上下两个节点信息的指向。「对象」相对来说内存空间占用较小，也不需要连续空间。
链表也不具备随机访问性。对象和数组都可以做到随机访问，数组直接访问索引，对象直接访问 key 值。
查询效率低，只能通过 next 的指向依次查询。
如何生成一个链表？
直接提供代码：
class Node {    constructor(data) {        this.data = data        this.next = null        this.prev = null    }}class SingleList {    constructor() {        this.size = 0 //单链表长度        this.currNode = \\\'\\\'//当前节点指向    }    //在单链表中寻找 item 元素    find(item) {        while (currNode && (currNode.val !== item)) {            currNode = currNode.next        }        return currNode    }    //向单链表插入元素    inset(item, element) {        let itemNode = this.find(item)        if (!itemNode) return
        let newNode = new Node(element)        newNode.next = itemNode.next;        itemNode.next = newNode        this.size++    }    //在单链表尾部添加一个节点    append(element) {        let currNode = this.findLast();        let newNode = new Node(element);
        currNode.next = newNode;        this.size++;    }    //获取单链最后一个节点    findLast() {        currNode = this.currNode        while ( currNode && currNode.next) {            currNode = currNode.next        }        return currNode    }    //获取链表长度    getLength() {        return this.size    }    //单链表的遍历显示    display() {        let result = \\\'\\\'        let currNode = this.val        while (currNode) {            result += currNode.val            currNode = currNode.next            if (currNode) {                result += \\\'->\\\'            }        }        return result    }}
const link = new SingleList()link.append([1, 2, 3, 5])

学链表有什么用？

目前看，好像没啥用。就是刷算法题，刷到这里了。硬着头皮啃下去，可能以后会在某个时间点发挥出作用吧 …
链表在哪用啊？不知道，我目前项目里从来没有使用过，我知道使用链表数据非常好的项目是 React，React 就是使用链表来设计的组件库，哈哈哈。
点击关注公众号，查看更多 Vue 的内容
图片授权基于 www.pixabay.com 相关协议
参考文章：
https://leetcode-cn.com/problems/design-linked-list/solution/she-ji-lian-biao-by-leetcode/
https://segmentfault.com/a/1190000024565634
https://blog.csdn.net/u014082714/article/details/44259029

原创文章，作者：小道研究，如若转载，请注明出处：https://www.sudun.com/ask/34522.html

Like (0)
小道研究的头像小道研究
0 0
Previous 2024年4月12日
Next 2024年4月12日

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注