基本数据结构：链表（list）C小加C++博客

基本数据结构：链表（list） - C小加 - C++博客

基本数据结构：链表（list）

作者：C小加 更新时间：2012-7-31

谈到链表之前，先说一下线性表。线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表有两种存储方式，一种是顺序存储结构，另一种是链式存储结构。

顺序存储结构就是两个相邻的元素在内存中也是相邻的。这种存储方式的优点是查询的时间复杂度为O(1)，通过首地址和偏移量就可以直接访问到某元素，关于查找的适配算法很多，最快可以达到O(logn)。缺点是插入和删除的时间复杂度最坏能达到O(n)，如果你在第一个位置插入一个元素，你需要把数组的每一个元素向后移动一位，如果你在第一个位置删除一个元素，你需要把数组的每一个元素向前移动一位。还有一个缺点，就是当你不确定元素的数量时，你开的数组必须保证能够放下元素最大数量，遗憾的是如果实际数量比最大数量少很多时，你开的数组没有用到的内存就只能浪费掉了。

我们常用的数组就是一种典型的顺序存储结构，如图1。

链式存储结构就是两个相邻的元素在内存中可能不是相邻的，每一个元素都有一个指针域，指针域一般是存储着到下一个元素的指针。这种存储方式的优点是插入和删除的时间复杂度为O(1)，不会浪费太多内存，添加元素的时候才会申请内存，删除元素会释放内存，。缺点是访问的时间复杂度最坏为O(n)，关于查找的算法很少，一般只能遍历，这样时间复杂度也是线性（O(n)）的了,频繁的申请和释放内存也会消耗时间。

顺序表的特性是随机读取，也就是访问一个元素的时间复杂度是O(1)，链式表的特性是插入和删除的时间复杂度为O(1)。要根据实际情况去选取适合自己的存储结构。

链表就是链式存储的线性表。根据指针域的不同，链表分为单向链表、双向链表、循环链表等等。

一、 单向链表（slist）

链表中最简单的一种是单向链表，每个元素包含两个域，值域和指针域，我们把这样的元素称之为节点。每个节点的指针域内有一个指针，指向下一个节点，而最后一个节点则指向一个空值。如图2就是一个单向链表。

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

我写了一个简单的C++版单向链表类模板，就用这段代码讲解一下一个具体的单向链表该怎么写（代码仅供学习），当然首先你要具备C++基础知识和简单的模板元编程。
完整代码

首先我们要写一个节点类，链表中的每一个节点就是一个节点类的对象。如图3。

代码如下：

template<class T>
class slistNode
{
    public:
    slistNode(){next=NULL;}//初始化
    T data;//值
    slistNode* next;//指向下一个节点的指针
};

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/2083814.html