链表是一种逻辑上连续，内存上分散的线性表数据结构，是用一组任意的空间（可以连续，也可以不连续）来存放数据元素。每个数据元素成为一个”结点“，每个结点由数据域和指针域组成。

1. 访问元素（Access）O(N)
2. 搜索元素（Search）O(N)
3. 插入元素（Insert）O(1)
4. 删除元素（Delete）O(1)

特点：写的快读的慢（应用于写多读少）

最基本的链表如图所示：

以下参考：数据结构：链表及其C++实现 - 菜鸡刘 - 博客园 (cnblogs.com)

插入操作：

假如需要在C结点后面插入F结点，只需要使C结点的指针指向F，F结点的指针指向结点D即可，如图所示

需要注意的是，在具体实现的时候，需要先暂存C结点的指针，先将其赋值给F结点指针，然后再将F结点的地址赋值给C结点的指针，否则会丢失D结点的地址，链表就会在此处断开。

删除操作：

假如需要删除D结点，则直接让C结点的指针指向E结点即可，如图所示

具体代码实现：

本文利用C++面向对象的特性与模板实现了一个链表类，并实现了插入、删除、查找、拷贝构造、拷贝赋值等基本操作。

结点类实现：

// 链表节点类
template
class node
{
public:
    node() : next(nullptr){} // 这是构造函数
    node(T val) : data(val), next(nullptr) {} // 这是有参构造
private:
    T data;
    node* next;
    friend class list; //同时在node类中将链表类list声明为友元，便于访问node的成员。
};

链表类声明：

链表类list的声明如下，主要实现了以下操作。list类包含两个成员属性head_ptr和length，前者是链表的头指针，后者储存链表的长度。

template
class list
{
public:
    list(); // 构造函数
    list(const list& l); // 拷贝构造
    list& operator= (const list& l); // 拷贝赋值 
    void insert_node(int index, T val); // 在index处插入结点
    void del_node(int index); // 删除index处结点
    T get_node(int index); // 获取index处结点值
    int find(int value); // 查找值value，找到返回index，找不到返回-1
    int get_length(); // 获取链表长度
    void push_back(T val); // 在链表尾部插入数据
    ~list(); // 析构函数
private:
    node* head_ptr; // 链表头指针
    int length; // 链表长度
};

插入实现：

对于插入操作，本文将其分为了三种情况

• 超出索引，抛出异常
• 插在空链表的头
• 一般情况

  // 在index处插入结点
  template
  void list::insert_node(int index, T val)
  {
      if((index > this->length)) // 超过索引，最多可以插到当前结点的下一个结点，否则就是超过索引
      {
          throw runtime_error("index out of this list`s range");
      }
      else if((this->head_ptr == nullptr) && (index == 0)) // 插在空链表的头
      {
          this->head_ptr = new node;
          this->head_ptr->next = nullptr;
          this->head_ptr->data = val;
          this->length++;
      } 
      else // 一般情况
      {
          node* p1 = this->head_ptr;
          node* p2 = new node;
          for(int i = 0; i < index - 1; i++)
          {
              p1 = p1->next;
          }
          p2->data = val;
          p2->next = p1->next;
          p1->next = p2;
          this->length++;
      }
  }
  

  删除实现：

  删除操作需要注意的是，每个结点都是通过new在堆区申请的内存，因此删除节点需要手动释放其内存。

  // 删除index处结点
  template
  void list::del_node(int index)
  {
      node* p1 = this->head_ptr;
      node* p2 = nullptr;
      for(int i = 0; i < index - 1; i++)
      {
          p1 = p1->next;
      }
      p2 = p1->next->next;
      delete p1->next;
      p1->next = p2;
      this->length--;
  }
  

  索引实现：

  // 获取index处结点值
  template
  T list::get_node(int index)
  {
      if(index > this->length - 1) // 超过索引
      {
          throw runtime_error("index out of this list`s range");
      }
      
      node* p1 = this->head_ptr;
      for(int i = 0; i < index; i++)
      {
          p1 = p1->next;
      }
      return p1->data;
  }
  

  查找实现：

  // 查找值value，找到返回index，找不到返回-1
  template
  int list::find(int value)
  {
      node* p1 = this->head_ptr;
      for(int i = 0; i < this->length; i++)
      {
          if(p1->data == value)
          {
              return i;
          }
          p1 = p1->next;
      }
      return -1;
  }
  

  析构实现：

  析构函数需要做的就是释放链表每个节点的内存。

  // 析构函数
  template
  list::~list()
  {
      // 清空链表
      node* p1 = this->head_ptr;
      node* p2 = p1->next;
      while(p2 != nullptr)
      {
          delete p1;
          p1 = p2;
          p2 = p2->next;
      }
      delete p1;
      this->length = 0;
      this->head_ptr = nullptr;
  } 
  

  力扣练习：

  【203】移除链表元素

  【206】反转链表

  视频来源：【数据结构2】链表Linkedlist_哔哩哔哩_bilibili