线性表的链式存储 - 单向链表

之前给大家介绍了线性表顺序存储，虽然它的查找很快O(1)的时间复杂度，但是一旦被创建出来，它的长度是固定的，即为MAXSIZE的长度，如果我们添加元素后超过这个值，不得不另外重新开辟一个比MAXSIZE更大长度的数组去存储它，更要命的是将之前的数组完全拷贝到这个新的数组中，而不得不额外花费O(n)的时间复杂度。

链式存储可以很好地解决这个问题，链式存储结构分为单向链表和双向链表，这篇主要介绍单向链表。

链表模型

单向链表

如图所示

由数据区域和指针区域组成，指针区域永远指向它的下一个节点的内存地址，也就是后继的位置，对应的后继有且只有一个，前驱也是确定的有且只有一个，不过单向链表只有指向后继的指针。

多个节点的模型如图所示

头节点：在链表的第一个节点，永远指向第一个数据节点。头指针的数据可以为空，但是不能删除，删除之后就丢失了整个链表。

尾结点：指向一个空的节点，没有后继节点。

头指针：指向头结点的指针。

单向链表操作

单向链表的头文件

#ifndef __SINGLE_LINK_H__
#define __SINGLE_LINK_H__

#include "include/type.h"


typedef struct singleLinkNode
{
    void * data;
    SingleLinkNode * next;
} SingleLinkNode;

class SingleLink {
private:
    /**
     * 单向链表头指针
    */
    SingleLinkNode * head = nullptr;

    /**
     * 单向链表长度
    */
    int lenSize = 0;

public:
    /**
     * 构造方法
    */
    SingleLink();

    /**
     * 析构方法
    */
    ~SingleLink();

    /**
     * 向链表中的第i个位置上插入节点
     * 
     * @param i [int] 节点位置
     * @param data [void *] 节点内容指针
     * 
     * @return D_RET 操作返回值
    */
    D_RET insert(int i, void * data);

    /**
     * 删除第i的元素，并且返回i上的内容
     * 
     * @param i [int] 节点位置
     * @param data [void *] 节点内容指针
     * 
     * @return D_RET 操作返回值
    */
    D_RET remove(int i, void *data);

    /**
     * 获取节点i的元素的值
     * 
     * @param i [int] 节点位置
     * @param data [void *] 节点内容指针
     * 
     * @return D_RET 操作返回值
    */
    D_RET getNodeAt(int i, void *data);

    /**
     * 获取单向链表的长度
     * 
     * @return int 链表的长度
    */
    int length();    
}

节点的定义

typedef struct singleLinkNode
{
    void * data;
    SingleLinkNode * next;
} SingleLinkNode;

定义了一个指向任意内存地址的void *的指针，和一个指向下一个数据的SingleLinkNode *的指针，其中每个节点的数据类型都是SingleLinkNode这个结构体。

对于单向链表，尤其重要的说明是插入和删除元素的操作：

插入操作

D_RET SingleLink::insert(int i, void *data)
{
    SingleLinkNode * tmp = this.head;
    int step = 1;
  
    while(tmp != nullptr && step < i)
    {
        tmp = tmp.next;
        step++;
    }

    if (step > i || !tmp) {
        return RET_ERR_OVERFLOW;
    }

    SingleLinkNode * newNode = new SingleLinkNode();
    newNode.data = data;
    newNode.next = tmp.next;
    tmp.next = newNode;
    return RET_OK;
}

代码注释描述新节点的插入过程，注意需要先执行newNode.next = tmp.next;再将原来的next给断开，如果先断开，那么插入节点的next指向下一个就找不到了。

插入示例图 i = 2位置插入节点：

删除操作

D_RET SingleLink::remove(int i, void * data)
{
    SingleLinkNode * tmp = this.head;
    SingleLinkNode * curNode = this.head;
    int step = 1;

    while(tmp.next != nullptr && step < i)
    {
        tmp = tmp.next;
        step++;
    }

    if (step > i || (tmp.next != nullptr)) {
        return RET_ERR_OVERFLOW;
    }

    curNode = tmp;
    tmp = tmp.next;
    delete curNode; 

    return RET_OK;
}

图文示例，删除 i = 3的节点：

这两个操作时间复杂度的最好的情况是1次，最坏的情况是循环n次，中间值是 n/2，时间复杂度为O(n)，与连续存储方式不同的是，我要获取一个元素它的时间复杂度是O(n)的情况，我不知道它的内存位置，必须要循环next，代码如下

D_RET SingleLink::getNodeAt(int i, void * data)
{
    SingleLinkNode * tmp = this.head;
    int step = 0;

    while(tmp.next != nullptr && step < i)
    {
        tmp = tmp.next;
        ++step;
    }

    if (step > i || (tmp == nullptr)) {
        return RET_ERR_OVERFLOW;
    }

    data = tmp.data;

    return RET_OK;
}

图文示例，获取i = 3的数据

单向循环链表

在单向链表的基础上，尾结点的指针指向头结点，首位相连，构成了一个环，如图

对于单向链表，我们访问首个元素是O(1)的复杂度，为head->next的就可以访问到，访问最后一个元素的时间复杂度为O(n)，对于单循环链表，我们记录一下它的尾指针rear，那么访问第一个元素的位置的时间复杂度为O(1)，rear->next->next，最后一个元素即为自己rear，很容易将元素插入到链表尾部。

其他操作

我们介绍了链表的一些特性和一些操作，其他的一些操作希望大家自己动手编写代码，例如：反转、合并、排序等。

示例代码链接请点击文章最下方的链接获取。

总结

相比顺序存储，单向链表的优缺点：

存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能

• 查找
• 顺序存储结构O(1)
• 单链表O(n)
• 插入和删除
• 顺序存储结构需要平均移动表长的一半的元素，时间为O(n)
• 单链表在找出某位置的指针后，插入和删除的时间仅为O(1)

空间性能

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

应用顺序存储结构和单链表各有各的优缺点，要根据实际情况采用那种数据结构，也可以混合使用，在编程场景中有没有用到过链表的形式，可以在评论区大家探讨。

[谢谢][谢谢][谢谢][谢谢][谢谢]小编码子不容易，希望关注一下小编，多多支持。