第2篇 C++ 数据结构-链表概述

本篇我们会讨论单向链表，在所有线性存储结构当中，链表是最常用且非常重要的数据结构，因为链表实现队列(Queue)以及环形队列(Circle Queue),栈(Stack)的最佳选择,在许多app中,单链表应用随处可见。例如很多即时通讯工具的好友列表，电话中的通讯录,以及媒体播放器的播放列表都广泛地用到了链表。

单向链表(Single-LinkedList)，由一个或多个节点(Node)组成,每个结点承载着特定数据类型的对象。

链表示意图

结点(Node)

• 数据域(Data Field):用于保存实际的对象数据，
• 指针域(Data Pointer),用于指向下一个相同数据类型的节点的内存地址。

ArrayList vs LinkedList

我们用一个形象生动的例子，来比较一下ArrayList和LinkedList的差别

• ArrayList内部的堆内存块是连续的内存块，而LinkedList的元素存储位置在堆中通常是不连续的。

  
  LinkedList的节点在堆内存中可能不连续
  ArrayList在堆中是连续的内存空间

• 对于中间元素的插入/删除操作，ArrayList的性能消耗通常是O(n)，而LinkedList通常是O(1).

  • ArrayList元素插入场景,需要将后面的N个元素逐个向后移动。

    
    ArrayList和Vector中间插入元素

  • LinkedList元素插入元素的场景,只需改变现有元素与新增元素的指针指向关系即可。

    
    LinkedList中间插入元素

• 对于遍历搜索元素操作，ArrayList的性能开消为O(n),而LinkedList通常为O(n)
• 对于下标索引访问操作, ArrayList的性能开销为O(1),而LinkedList通常为O(n)

那么我们来看看ArrayList与LinkedList的各种操作下的时间复杂度对比，这个表并没有考虑到最差的情况。这表面上看，LinkedList似乎跟ArrayList没什么优势。LinkList在中间位置和末尾插入的时间复杂度之所以为O(n)，是因为每次在插入元素之前必须发生遍历操作找到插入元素对应的位置。

性能比较

如果你对标准库vector或我前一篇文章ArrayList的内部堆内存管理有所了解的话,应该知道ArrayList在添加或删除达到一个指定比例值时，内存可能需要扩容/收缩(简称resize).

假设ArrayList的元素类型为T,原有内存数量为n,resize的内存数量为m=malloc(sizeof(T)*n)的内存空间重分配的时间复杂度为O(m)这个malloc操作属于操作系统底层的,另外ArrayList本身n个元素的深度拷贝到新堆内存空间的一系列过程,这个时间复杂度就为O(n)那么这种最差的情况下

那么，ArrayList在插入/删除操作最差的情况，确切是O(m)+O(n)

LinkedList相比之下就没有这些昂贵的操作,LinkedList只会对插入/删除的元素的一次性malloc或free操作，无需额外的连续内存重分配。所以LinkedList在插入或删除方面有着明显的性能优势。

需要注意的是遍历操作与下标访问是两个绝然不同的概念

• 遍历操作是值通过for/while/foreach循环控制语句遍历整个线性表,例如arr是一个线性表，下面的示例都属于遍历结构，他们的时间复杂度约定为O(n)

for(auto i=0;i<arr.size;i++){....}
//或
foreach(item in arr){...}
//或
size_t i=0;
while(i<arr.size){...}
//或
while(arr.next()){...}

• 下标索引访问:可能会有人疑问ArrayList的下标索引操作的时间复杂度不是O(n)吗？当然不是，因为ArrayList的下表访问的底层实现是其内部的数据指针d_arr加或减整数，即表达式*(d_arr+i)或d_arr[i]，只要i的值确定,这是可以在恒定时间内完成指针偏移的常量,因此ArrayList的下标索引操作的时间复杂度为O(1).通常遍历操作内嵌下标索引访问。

链表类接口的基本定义

以前说过用C++实现数据结构合适，写类接口对比C代码,C++在语法上更优雅和逻辑清晰，并且C++具有访问级别的限制，使得外部调用代码无法随意修改链表中的数据。该系列的文章，我会用到C++来实现该单向链表。

首先LinkedList由一个节点类(Node)和一个链表类(LinkedList)构成。

• 节点类(Node)：类名英文写法上约定一般为Node，他包括两个数据属性，
  • 数据字段，我们约定为data,用于承载类型为T的对象数据的实体。
  • 指针字段，我们约定为next用于指向下一个同样T类型的Node节点。
• 链表类(LinkedList):就是构成整个链表的驱动主体，你可以将链表比喻为一辆很长的火车。LinkedList对象可是就是“驾驶员”他负责维护整个链表的状态，而Node对象就是(车厢)，而最后一个节点需要指向一个nullptr。
  • head指针:负责指向整个链表的第一个节点(火车头)，它是遍历整个链表的起点。
  • 尺寸(size):负责记录整个链表的节点数(有多少节车厢)
    LinkedList对象与Node对象的关系

Node类接口

这里需要注意的是我们定义的同时，我们需要类内部声明一个LinkedList接口的友元函数，以便LinkedList类接口的成员函数能够访问Node类接口的私有数据成员。这是设计模式中典型的组合模式，在C++中普遍存在。

#include <iostream>
#include <stdlib.h>

template <class T>
class LinkedList;

template <class T>
class Node
{
private:
    Node *d_next; //指向下一个节点
    T d_data;

public:
    Node();
    //自定义构造函数
    Node(T);
    //返回节点上的元素实体
    const T &elem();

    //返回当前节点的下一个节点的地址
    Node<T> *next();

    //析构函数
    ~Node();
    //LinkList的友元函数
    friend class LinkedList<T>;

    template <typename R>
    friend std::ostream &operator<<(std::ostream &, const Node<R> &);
};

LinkedList类接口

template <class T>
class LinkedList
{
private:
    //头指针
    Node<T> *d_head;
    //中间节点
    Node<T> *d_mid;
    //未指针
    Node<T> *d_last;
    //链表尺寸
    size_t d_size;

    //查找元素所在位置
    Node<T> *_search(const T &val);
    //二分查找法
    size_t binary_search(size_t s, size_t e, size_t k);

public:
    //默认构造函数(空链表)
    LinkedList();

    LinkedList(size_t);
    //拷贝构造函数
    LinkedList(const LinkedList &list);
    //移动构造函数
    LinkedList(LinkedList &&otl);
    //析构函数
    ~LinkedList();
    //末端插入元素
    void push_back(T);
    //在头部插入元素
    void push_head(T);

    //获取头部元素
    T front();
    // 获取末端元素
    T last();

    //颠倒链表顺序
    void reverse();

    //查找元素的值，删除该元素
    void remove(const T &value);
    //在指定位置，插入元素
    void insert(size_t idx, T elem);

    //迭代接口:返回下一个节点
    // T next();

    //公开的查找节点函数
    Node<T> *search(const T &val);

    Node<T> *search_v2(size_t);

    //清空整个链表
    void clear();

    //打印链表
    template <class R>
    friend std::ostream &operator<<(std::ostream &, const LinkedList<R> &);

    //索引访问操作符号
    T operator[](size_t);

    //获取尺寸
    size_t size()
    {
        return d_size;
    }
    //获取中间节点
    Node<T> *mid_node();
    //获取中间节点
    Node<T> *mid_node(size_t &);
};

小结

本篇主要是对链表一个概念，以及和ArrayList做了一些性能上的对比，可以知道，在写入/删除元素操作方面具有其他线性表结构代替的性能优势。似乎单项链表本质上来说是不支持下标索引访问，只能通过每次O(n)的遍历来模拟下标索引的访问操作，因此这方面不如ArrayList和标准库的vector,后面的相关随笔会谈到这方面。很晚了，睡觉去~~!!