数据结构——头插法和尾插法_数据结构头插法和尾插法

作者：很楠不爱3 | 2024-05-06 09:51:58

踩

数据结构头插法和尾插法

头插法和尾插法

1.节点的定义
在这里插入图片描述
2.采用头节点的好处

3.采用头插法建立链表
该方法从空表开始，生成新节点，并将读取到的数据存放到新节点的数据域中，并将新节点插入到当前链表的表头，即头节点之后。
采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个节点插入的时间为O(1)，设单链表长为n，则总时间复杂度为O(n)。
在这里插入图片描述 4.采用尾插法建立链表
头插法建立单链表的算法虽然简单，但是生成的链表中的结点的次序和输入数据的顺序不一致。若希望两者的次序一致，则可以采用尾插法，该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。
因为附设了一个指向表尾结点的指针，故时间复杂度和头插法相同。
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/543673