链表,链表尾插法

链表是什么东西

链表是一种有序的列表，链表的内容通常是存储与内存中分散的位置上。

链表的方式有两种1：一种是利用数组结构串连的有序列表。

例如；两个数组，一个存放数据，另一个存放连接的关系。这种缺乏弹性。

2：以动态内存配置的链表，（通常指的链表是一动态内存分配的链表）动态内存配置的链表，

是由许许多多的（node）所链接而成的，每一个结点，包含了数据部分和指向下一个结点的指针（Pointer）。

以动态内存配置的链表，在插入和删除元素的时候，只需要将指针改变指向就可以。

链表和数组一样是一种数据结构，如何使用完全基于你的应用需求。

链表和C++语言本身没有任何联系。很多语言都可以实现链表数据结构。

我讲一下数据和链表的区别有可能帮助你对链表的使用有个感觉。

数组是将元素在内存中连续存放，由于每个元素占用内存相同，所以你可以通过下标迅速访问数组中任何元素。但是如果你要在数组中增加一个元素，你需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果你想删除一个元素，你同样需要移动大量元素去填掉被移动的元素。

链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果你要访问链表中一个元素，你需要从第一个元素开始，一直找到你需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了， 只要修改元素中的指针就可以了。

从上面的比较你可以看出，如果你的应用需要快速访问数据，很少或不插入和删除元素，你就应该用数组；相反， 如果你的应用需要经常插入和删除元素你就需要用链表数据结构了。然后你自己可以想一想什么样的应用用链表合适。

另外，建议你找一本好一点的关于数据结构的书，里面应该关于链表和其上算法的详细介绍。链表本身是一个复杂的数据结构，而且包括很多种类，比如单向链表，双向链表，树，图等，不是一篇文章可以介绍得清楚的。

链表的定义

链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量，以head表示，它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据，二为下一个结点的地址。因此，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

链表是什么课程讲解的内容

链表是《数据结构》课程讲解的内容。

数据结构课程是由杨博为课程负责人，吉林大学为主要建设单位的国家级一流本科课程。

1、教师团队：

（1）课程负责人：杨博。

（2）授课教师：贾海洋、黄晶、虞强源、朱允刚。

2、所获荣誉：

2020年11月24日，该课程被中华人民共和国教育部认定为“首批国家级一流本科课程”。

常用数据结构“链表”介绍：

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。

其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。

以上内容参考：百度百科-数据结构（计算机存储、组织数据方式）

以上内容参考：百度百科-数据结构（国家级一流本科课程）

链表是什么

链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。链表是一种线性表，但它不像顺序表那样连续存储元素，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不用连续存储，插入的时间复杂度为O(1)，比顺序表快得多；但是查找一个节点或者访问特定编号的节点的时间复杂度均为O(n)，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

什么是链表?

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表—什么是链表

书本概念

链表是一种将数据存储到“结点”中的数据结构，需要存储多少个数据，就生成多少个“结点”，把这些“结点”用指针挂接起来。

为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)，这两部分信息组成数据元素ai的存储映像，称为结点。

结点中包括两个域，其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针。

慕课笔记

前面说过，对于链表数据是存储在结点中的。结点包括两部分，数据e和指针next，

说了这么多，举个例子吧。下图可以看做是一个链表，链表中共有三个结点，其中的1、2、3是数据e本身，而且箭头是next指针。链表不可能是无穷无尽的，对于最后一个结点，其next指针指向null，即指向了空结点。

可以看出，链表不像静态数组那样，一下子new出来一片空间，而是需要多少，就生成多少个空间(结点)，只需要把他们挂接起来。也不需要考虑空间是否大了或者小了。

同时，这也是链表的缺点：失去了随机访问的能力。这是因为：

在底层机制上，数组开辟的空间在内存里是连续分布的，直接去找这个索引对应的偏移，直接计算出相应元素的内存地址，用O(1)的复杂度把这个元素取出；而链表是靠next一层一层连接的，在计算机的底层，每一个结点所在的内存位置是不同的(每new一个结点，计算机就会随机分配一个地址)，只能靠next一点一点的去找到我们想要的元素

链表和数组对比：

数组最好用于索引有寓意的情况。例如，score[2]，代表学号为2的，学生的成绩；数组支持快速查询。

链表不适合用于索引有语意的情况；链表是动态的。

何时使用二者，就要看我们的需求是适合动态的数据结构，还是适合静态的数据结构。

简单的编写下链表这个数据结构