链表是什么

链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。说到这里你应该就明白了，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素;……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”(表示“空地址”)，链表到此结束。

单链表双链表单循环链表双循环链表有什么区别

1、链接方式不同

单链表：每个节点只有一个指针，指向下一个节点，从而形成一个单向的链表。

双链表：每个节点有两个指针，一个指向前驱节点，一个指向后继节点，使得链表成为一个双向的链表。

单循环链表：每个节点也只有一个指针，但是可以将链表最后一个节点的指针指向链表的头节点，从而形成一个循环链表。

双循环链表：每个节点有两个指针，一个指向前驱节点，一个指向后继节点，同时链表的第一个节点的前驱指针指向最后一个节点，最后一个节点的后继指针指向第一个节点，也就是形成一个环。

2、遍历方式不同

单链表：只能单向遍历，无法回退。

双链表：可以双向遍历，可以在单链表的基础上支持反向遍历。

单循环链表：可以循环遍历。

双循环链表：可以通过任何一个节点开始正向或反向遍历整个链表，通过尾节点开始遍历也可以回到头节点。

3、应用场景不同

单链表：节点占用空间小，插入和删除节点速度快，适用于不需要反向遍历的场合。

双链表：节点占用空间比单链表大，插入和删除节点的操作复杂度更高，适用于需要双向遍历的场合。

单循环链表：在处理循环遍历的问题上更加方便，也可用于实现循环队列。

双循环链表：在需要首尾相连的问题中比较适用。