写在前面：在我看来链表就是对指针操作的练习，能很好的实现和使用链表将能更好地使用指针，并且链表也是重要的数据结构。
（1）链表的优势，插入和删除任意结点都很快
（2）劣势：随机访问能力较差
链表的注意事项

链表的分类

一.链表的简单介绍

链表就是通过指针把它的一串存储结点链接成一个链
以单链表为例：
存储结点由两部分组成：
（2）数据域 + 指针域（后继地址）

data 保存数据，next连上后一个结点，像一个链条一样一节一节的链接而成！
可以看出data和next相等于关联在一起，很容易想到用结构体可以完成这个定义。

那么既然如此 肯定就有头（head）和尾（tail），这两个也是最重要的结点，
头结点分为保存数据和不保存数据的。本文才用头结点不存储数据的方式创建链表。


这样就创建了一个头结点和尾结点（初始时没有数据他们自然指向同一处）

现在有个头和尾，我我们得往链表中插入数据。下面介绍两种添加数据的方法：
（头插法）头插法就是一直插在头后面，也就是head->next的位置
这样就可以制造出先进后出的方法（在栈中会用到）


（2）尾插法，一直在链表的尾部插入数据，也就是tail的后面一直添加元素。


两种方法各有千秋，不过本文主要采用的尾插法。
上面提到了链表的插入和删除的优势，接下来看看他是怎么实现的
（1）单链表的插入
**1 先找到结点的位置 2 建一个新结点 3 前屈next和新结点连上，新结点next和位置后继连上。（一定要先处理特殊结点）


（2）双链表插入则 多考虑一步prev的链接

2 （1）单链表的删除

（1）找到删除位置，（2）让此位置的前屈指向后继（一定要先出来特殊结点）
（2）双链表仍然是多考虑一步prev

二：c中单链表的实现

#include <stdio.h>
#include<stdlib.h>
typedef int ElementType;
typedef struct list
{struct list *next;ElementType element;
} List, *Position; //List为 struct list ，Position为 struct list *
void DeleteList(List *L);   //删除链表中数据为X的元素
List  *MakeEmpty( List *L ) //制造一个空链表
{if ( L != NULL ) //有数据则删掉整个链表的数据DeleteList( L );L = malloc( sizeof( List) ); //开一个头结点if ( L == NULL )printf( "Out of memory!\n" );L->next = NULL;       //制空return L;
}
int IsEmpty( List *L )  //检测链表是否为空
{return L->next == NULL;
}
int IsLast( Position P) //检测是否是链表的最后一个结点
{return P->next == NULL;
}
Position Find( ElementType X, List *L ) //查找链表中的X元素
{Position P;P = L->next;while ( P != NULL && P->element != X ) //从第一个数据结点开始遍历P = P->next;return P;
}
Position FindPrevious( ElementType X, List *L )//找到X元素对应位置的前屈
{Position P;P = L;while ( P->next != NULL && P->next->element != X )P = P->next;return P;
}
void Delete( ElementType X, List *L )//删除链表中数据为X的元素
{Position P, TmpCell;P = FindPrevious( X, L );               //找到X之前一个元素的位置if ( !IsLast( P) )  //P是尾结点，则说明链表中不存在X。因此那部分不考虑{TmpCell = P->next;  //预留P->next = TmpCell->next;  //改变指向free( TmpCell );    //free}
}void insert(  Position P, ElementType X ) //插入一个值为X的元素在P后
{Position TmpCell;TmpCell = malloc( sizeof( List ) ); //创建if ( TmpCell == NULL )printf( "Out of memory!\n" );TmpCell->element = X; //存X到新结点TmpCell->next = P->next; //新元素结点next 指向 P后置P->next = TmpCell;  //P后置 指向新元素结点，这样就插在 P和P_after之间了
}
void DeleteList( List *L )//删除整个链表的数据
{Position P, Tmp;P = L->next;  //第一个有数据的结点L->next = NULL; //让头结点的后一个next为空while ( P != NULL )  //去free掉后面的空间{Tmp = P->next;free( P );P = Tmp;}
}
void BeforeCreat(List *L)
{ElementType element;while (~scanf("%d", &element)) { //头插法建立一个链表insert(L, element);}
}
void AfterCreat(List *L)
{ElementType element;while (~scanf("%d", &element)) { //尾插法建立一个链表List *temp = L;insert(temp, element);temp = temp->next;}
}
void print(List *L)
{if (L->next == NULL) {printf("The is a blank list!\n");return;}List *temp = L->next;for (; temp != NULL; temp = temp->next) {printf("%d ", temp->element);}printf("\n");
}
int main()
{List *head = NULL;head = MakeEmpty(head);BeforeCreat(head); //头插法创建链表数据成员print(head);AfterCreat(head);//尾插法创建链表数据成员print(head);Delete(Find(1, head)->element, head); //找到1再删掉print(head);DeleteList(head); //删除整个链表数据成员print(head);return 0;
}

三.（1）C++中单链表的实现

#include<iostream>
#include<initializer_list>
using namespace std;
template <class T> class Link
{
public:T data; //用于保存结点元素的内容Link<T> *next; //指向后继结点的指针Link(const T info, Link<T> *nextValue = nullptr):data(info),next(nextValue) { }Link(Link<T> *nextValue = nullptr ):next(nextValue){}
};template <class T>
class forward_list
{
public:forward_list(initializer_list<T> ls);//{}初始化forward_list(unsigned int n, T data);  //(n,data)初始化forward_list() {tail = head = new Link<T>; //建一个空表}int getPos(T value); //返回value元素对应的下标~forward_list(); //析构函数bool insert(unsigned int i, const T value); //插入在i下标处bool erase(unsigned int i); //删除下标为i的元素void push_back(T value); //在链表尾部插入一个valuevoid print(); //输出整个链表private:Link<T> *head;Link<T> *tail;Link<T> *setPos(int i); //定位函数，找到下标为i的元素的位置
};template <class T>
forward_list<T>::forward_list(initializer_list<T> ls) //{}初始化
{tail = head = new Link<T>; //初始化让尾和头指向同一处；for (auto lst : ls) {auto t = new Link<T>(lst, tail->next);tail->next = t;tail = t;}
}
template <class T>
forward_list<T>::forward_list (unsigned int n, T element) //使链表有n个data数据。
{//初始化让尾和头指向同一处；tail = head = new Link<T>;for (int i = 0; i < n; ++i) { //将n个data连在链表上auto temp = new Link<T>(element, tail->next);tail=tail->next = temp;     }
}
template <class T>              // 假定线性表的元素类型为T
Link<T > *forward_list<T> ::setPos(int i)
{int count = 0;Link<T> *p;if (i == -1)                // i为-1则定位到"虚"头结点return head;p = head->next;         // 若i为0则定位到第一个结点while (p != NULL && count < i) { //寻找位置p = p-> next;count++;};return p;               // 指向第 i 结点，i＝0,1,…，当链表中结点数小于i时返回NULL
}
template <class T>
int forward_list<T>:: getPos(T value) //找到元素value对应的下标
{unsigned int count = 0;Link<T> *p = head->next;for (; p != nullptr && p->data != value; ++count, p = p->next) {} //寻找相等的值if (p != nullptr)return count; //不是尾后结点 则说明找到了cout << "not found the value";return -1;
}template  <class T>                 // 假定线性表的元素类型为T
bool forward_list<T> :: insert(unsigned int i, T value) //在下标为i处插入value
{Link<T> *p = setPos(i - 1); // p是第i个结点的前驱if (p == NULL) //说明i越界了，不是链表中的元素{cout << " the inserted point is illegal" << endl;return false;}Link<T> *q = new Link<T>(value, p->next);p->next = q;if (q->next == nullptr )             // 插入点在链尾，插入结点成为新的链尾tail = q;return true;
}
template  <class T>
bool forward_list<T>::erase(unsigned int i) //删除掉下标为i的元素
{Link<T> *p = setPos(i - 1); //寻找前屈if (p == NULL)     //找不着则不处理{cout << "the deleted pint is illegal" << endl;return false;}Link<T> *deleted = p->next;if (deleted != nullptr) { if (deleted == tail) { //尾结点，直接删掉尾部就行，然后tail也要重置一下tail = p;}p->next = deleted->next; //平常结点，改一下指向delete deleted;}return true;
}
template  <class T>
void forward_list<T>::push_back(T value) //直接在末尾添加一个元素
{tail = tail->next = new Link<T>(value, tail->next); //记得重置tail
}
template<class T>
void forward_list<T>::print() //输出整个链表
{if(head->next==nullptr){// 空链表则提示一下cout << "The list is a blank list!"<<endl;return;}for (auto p = head->next; p != nullptr; p = p->next)cout << p->data << " ";cout << endl;
}
template <class T>
forward_list<T>::~forward_list()  //删掉整个链表
{Link<T> *tmp;while (head != nullptr) {tmp = head;head = head->next;delete tmp;}
}
int main()
{forward_list<int> x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ;for (int i = 10; i < 20; ++i)x.push_back(i);x.print();for (int i = 10; i < 20; ++i) {int index;if ((index = x.getPos(i)) >= 0) {x.erase(index);}}x.print();for (int i = 10; i >= 0; --i) {x.erase(i);}x.print();for (int i = 0; i < 5; ++i) {x.insert(0, i);if (i >= 4)for (int j = 4; j >= 0; --j)x.insert(5, j);}x.print();return 0;
}

（2）c++中双链表的实现

#include<iostream>
#include<initializer_list>
using namespace std;
template <class T>
class Link
{
public:T data;Link<T> *prev;   //双链表需要加多一个prevLink<T> *next;Link(T value, Link<T> *prevvalue = nullptr, Link<T> *nextvalue = nullptr  ): data(value), prev(prevvalue), next(nextvalue) { }Link(Link<T> *nextvalue = nullptr, Link<T> *prevvalue = nullptr) : next(nextvalue), prev(prevvalue) {}
};
template<class T>
class list
{
public:list(initializer_list<T> lis) {  //{} 初始化 c++11head = tail = new Link<T>;for (auto ls : lis) {auto temp = new Link<T>(ls, tail);tail = tail->next = temp;//尾插}}list(unsigned int n, T element) {  //初始化为n个 值为element的链表tail = head = new Link<T>;//初始化让尾和头指向同一处for (int i = 0; i < n; ++i) { //将n个data连在链表上tail = tail->next  = new Link<T>(element, tail, nullptr); //尾插}}list() { //默认初始化一个空链表tail = head = new Link<T>;}bool insert(Link<T> *pos, T value); //插入在pos前一个元素的位置bool insert_after(Link<T> *pos, T value);  //插入在pos后一个元素的位置void push_back(T value) {tail = tail->next = new Link<T>(value, tail, nullptr); //插入一个元素在尾后}bool erase(Link<T> *pos); //删除pos位置上的元素void MakeEmpty(); //使整个链表的数据为空void print();  //输出整个链表~list(); //析构函数Link<T> *begin() {  //返回第一个有数据的结点的位置return head->next;}Link<T> *end() { //返回尾后结点的位置return tail->next;}private:Link<T> *head;Link<T> *tail;
};
template  <class T>                 // 假定线性表的元素类型为T
bool list<T>::insert(Link<T> *pos, T value)//插入在pos之前的位置
{if (pos == head) { //不能插在头结点之前cout << "The insertion position is an error!\n ";return false;}if (pos == nullptr)   //插入到尾部不必考虑prev{tail = tail->next = new Link<T>(value, tail, nullptr);return true;}Link<T> *insertion = new Link<T>(value, pos->prev, pos); //建一个insertion结点并对prev和next初始化pos->prev->next = insertion;//一定得先做这一步，pos->next 先变得话，那么再改pre->next->prevpos->prev = insertion;  //就是pos了 而不是pos之前的insertion。就连不上了return true;
}
template <class T>
bool list<T>::insert_after(Link<T> *pos, T value) //插入一个元素到pos位置之后
{if (pos == nullptr) { //不能插入到尾后结点之后cout << "The insertion position is an error!\n ";return false;}if (pos == tail)    //插入到尾部不必考虑prev{tail = tail->next = new Link<T>(value, tail, nullptr);return true;}Link<T> *insertion = new Link<T>(value, pos, pos->next); //建一个insertion结点并对prev和next初始化pos->next->prev = insertion;  //一定得先做这一步，pos->next 先变得话，那么再改pre->next->prevpos->next = insertion;  //就是pos了 而不是 pos之后的元素insertion。就连不上了return true;
}template <class T>
bool list<T>::erase(Link<T> *pos) //删除
{if (pos == nullptr || pos == head) { //不能删除 尾后结点 和 头结点cout << "The erased position is an error!\n ";return false;}if (pos == tail) {  //尾部得特殊处理，因为pos->next为nullptr  是没有prev的tail = tail->prev;tail->next = nullptr;delete pos;return true;}pos->prev->next = pos->next;        //尾部之前的情况 改一下指向就行了pos->next->prev = pos->prev;delete pos;                         //记得deletereturn true;
}
template <class T>
void list<T>::MakeEmpty()   //使链表制空
{   //从尾部开始删不必考虑 尾部特殊情况。for (auto temp = tail; temp != head; temp = tail) {tail = tail->prev;tail->next = nullptr;delete temp;}
}
template <class T>
void list<T>::print() //输出整个链表
{if (head->next == nullptr) {cout << "The list is a blank list!" << endl;return;}for (auto p = head->next; p != nullptr; p = p->next)cout << p->data << " ";cout << endl;
}template <class T>
list<T>::~list()//析构函数，删掉整个链表（包括head结点）
{Link<T> *tmp;while (head != nullptr) {tmp = head;head = head->next;delete tmp;}
}
int main()
{list<double> insertion(10, 1.1);list<int> insertion_after = {0, 0, 0};list<int> erased = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ;list<string> empty = {"I", " love", " you!"};list<int> PushBack;auto p = insertion.begin();for (int i = 0; i < 5; ++i) {insertion.insert(insertion.begin()->next, 10 );}for (int i = 1; i < 6; ++i) {insertion_after.insert_after(insertion_after.begin(), i);}for (int i = 0; i < 2; ++i){erased.erase(erased.begin());}for (int i = -1; i > -6; --i) {PushBack.push_back(i);}empty.MakeEmpty();empty.push_back("c++");cout << "The inserted list is: " << endl;insertion.print();cout << "The inserted in after position list is: " << endl;insertion_after.print();cout << "The erased list is: " << endl;erased.print();cout << "The pushback list is: " << endl;PushBack.print();cout << "The MakeEmpty and push_back  list is: " << endl;empty.print();return 0;
}

四c++中list和forward的一般使用规则

此文篇幅过长了，不易查看。list用法的总结我写在这个博客上了如有兴趣请移步：
https://blog.csdn.net/qq_45923646/article/details/107299760