链表是什么
链表是一种常见的基础数据结构,结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配,也就是说,链表是一个功能极为强大的数组,他可以在节点中定义多种数据类型,还可以根据需要随意增添,删除,插入节点。链表都有一个头指针,一般以head来表示,存放的是一个地址。链表中的节点分为两类,头结点和一般节点,头结点是没有数据域的。链表中每个节点都分为两部分,一个数据域,一个是指针域。说到这里你应该就明白了,链表就如同车链子一样,head指向第一个元素:第一个元素又指向第二个元素;……,直到最后一个元素,该元素不再指向其它元素,它称为“表尾”,它的地址部分放一个“NULL”(表示“空地址”),链表到此结束。
单链表双链表单循环链表双循环链表有什么区别
1、链接方式不同
单链表:每个节点只有一个指针,指向下一个节点,从而形成一个单向的链表。
双链表:每个节点有两个指针,一个指向前驱节点,一个指向后继节点,使得链表成为一个双向的链表。
单循环链表:每个节点也只有一个指针,但是可以将链表最后一个节点的指针指向链表的头节点,从而形成一个循环链表。
双循环链表:每个节点有两个指针,一个指向前驱节点,一个指向后继节点,同时链表的第一个节点的前驱指针指向最后一个节点,最后一个节点的后继指针指向第一个节点,也就是形成一个环。
2、遍历方式不同
单链表:只能单向遍历,无法回退。
双链表:可以双向遍历,可以在单链表的基础上支持反向遍历。
单循环链表:可以循环遍历。
双循环链表:可以通过任何一个节点开始正向或反向遍历整个链表,通过尾节点开始遍历也可以回到头节点。
3、应用场景不同
单链表:节点占用空间小,插入和删除节点速度快,适用于不需要反向遍历的场合。
双链表:节点占用空间比单链表大,插入和删除节点的操作复杂度更高,适用于需要双向遍历的场合。
单循环链表:在处理循环遍历的问题上更加方便,也可用于实现循环队列。
双循环链表:在需要首尾相连的问题中比较适用。