数组表示方法:
结点表示方法:
#define maxlength 100
struct LIST{
elementtype elements[maxlength];
int last
}
优点:查找方便
缺点:插入和删除需要移动大量数据(从而引出新的结构,链表)
链表表示方法:
结点表示方法:
struct celltype{
elementtype element;
celltype *next
}
单链表的后插时间复杂度:0(1)
单链表的前插复杂度:(需要查找定位)0(n)
特殊的,如果使用后插+交换,时间复杂度就为0(1)
另外,单链表中表头节点的使用使得在任意位置的插入和删除操作代码统一,而不必对不同的情况分别处理。 |