简易教程：使用头插法和尾插法在C++中创建并打印链表

致敬卷风—一位伟大的战士

        首先用粗俗的语言描述一下链表是什么以及他的作用：

        链表在某些作用上大致等同于一个动态的数组，尽管链表的编码和管理比数组更复杂，但它们有一些明显的优势。首先，链表可以容易地扩大或缩小。实际上，程序员并不需要知道链表中有多少个结点。它们只是根据需要在内存中创建。这样一来使得内存的利用率大大提高了。当然，使用动态的数组模板还有很多，这里只是对比一下链表与数组的不同。

数组的特点

• 在内存中，数组是一块连续的区域。
• 数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。
• 插入数据和删除数据效率低。
• 随机读取的效率很高。

 链表的特点

• 内存不要求连续
• 拓展方便，随意增加大小
• 随机访问效率低，但是目前而言不需要考虑这一点

    

稍微介绍一下几个链表的创建方法：

1.最基本的定义

#include<bits/stdc++.h>
using namespace std;

// 定义一个结构体 就是单个节点  这里是储存包含数据的一个结构 value 
//同时还要有一个指向另一个相同类型节点的指针

struct List
{
	double value;
	List* next;
};


int main()
{
	List* head = nullptr;//初始化
	//不能用list 小写list是容器
	//nullptr是用来代替NULL的宏定义的 一般两者等价

	head = new List;//分配一个新的节点

	head->value = 1;//储存值进入value
	head->next = nullptr;//表示链表的结尾
	List * two = new List;
	two->value = 2;
	two->next = nullptr;
	//这里吧nullptr变成了two指向nest的结果，所以第二个节点现在变成了链表的结尾
	head->next = two;//现在第一个节点的next指向的是two

	cout << head->value<<endl;
	cout << two->value;
	//也可以写成
	//head->next-value;
	
	return 0;

}

2.特别一点的结构内定义函数

（这个方法使得在创建链表的时候变得更加简洁）

#include<bits/stdc++.h>
using namespace std;
struct ListNode
{
    double value;
    ListNode* next;
    //构造函数

    ListNode(double value1, ListNode* next1 = nullptr)
    {
        value = value1;
        next = next1;
    }
};
int main()
{
  
    ListNode* three = new ListNode(5);
    //通过仅指定其 value 部分，而后继指针则默认为 nullptr

    ListNode* secondPtr = new ListNode(13.5,three);
    //通过指定 value 部分和一个指向链表下一个结点的指针。

    ListNode* head = new ListNode(12.5, secondPtr);
    //领悟这个创建列表的方法 注意是倒着写

    cout << head->value<<endl;
    cout<<secondPtr->value<<endl;
    cout << three->value;

}

其次是一个经典的头插法链表

可以用来大炮打小鸡解决倒序问题

#include<bits/stdc++.h>
using namespace std;
struct ListNode
{
    double value;
    ListNode* next;
    //构造函数

    ListNode(double value1, ListNode* next1 = nullptr)
    {
        value = value1;
        next = next1;
    }
};
 int main()
{
  ListNode *one = nullptr;
    double a[5];

    for (int i = 0; i < 5; i++)
    {
        cin >> a[i];
        one = new ListNode(a[i],one);
    
    }

    ListNode* ntr = one;
    while (ntr != nullptr)
    {
        cout << ntr->value;
         ntr=ntr->next;
    }
}

尾插法

#include<bits/stdc++.h>
using namespace std;
struct List
{
	int data;
	List* next;
};
int main()
{
	List* head = new List;//新节点
	int a[5];
	List* rear = head;//开一个尾指针 一直指向尾巴
	for (int i = 0; i < 5; i++)
	{
		cin >> a[i];
		List* one = new List;
		one->data = a[i];
		rear->next = one;//让尾指针指向one
		rear = one;
		/*rear 本来在 one前面，但现在rear在one上，
		因为是赋地址值，原来rear并没有消失，下个循环one = new List，
		就又重新创建一个节点，反复执行*/
	}
	rear->next = nullptr;

	List* h = head->next;
	//头节点没数据 所以h直接指向头节点的next
	while (h != nullptr)
	{
		cout << h->data;
		h = h->next;
	}

}

END