链表 在電腦科學中链表英語Linked list是一种常见的基础数据结构是一种线性表但是并不会按线性的顺序存储数据而是在每一个节点里存到下一个节点的指针由于不必须按顺序存储链表在插入的时候可以达到O的复杂度比另一种线性表顺序表快得多但是查找一个节点或者访问特定编号的节点则需要On的时间而顺序表相应的时间复杂度分别是Ologn和O 使用链表结构可以克服数组链表需要预先知道数据大小的缺点链表结构可以充分利用计算机内存空间实现灵活的内存动态管理但是链表失去了数组随机读取的优点同时链表由于增加了结点的指针域空间开销比较大 在计算机科学中链表作为一种基础的数据结构可以用来生成其它类型的数据结构链表通常由一连串节点组成每个节点包含任意的实例数据data fields和一或两个用来指向上一个或下一个节点的位置的链接links链表最明显的好处就是常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序数据的存取往往要在不同的排列顺序中转换而链表是一种自我指示数据类型因为它包含指向另一个相同类型的数据的指针链接链表允许插入和移除表上任意位置上的节点但是不允许随机存取链表有很多种不同的类型单向链表双向链表以及循环链表 链表可以在多种编程语言中实现像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作程序语言或面向对象语言如CC和Java依靠易变工具来生成链表