【插入

【插入

文章目录

• 单链表的基本操作
• • 插入----在第i个结点前插入值为e的新结点
  • 删除----删除第i个结点
  • 单链表上的查找，插入，删除算法时间效率分析

单链表的基本操作

插入----在第i个结点前插入值为e的新结点

【算法步骤】
1.首先找到a（i-1）的存储位置。
2.生成一个数据域为e的新结点。
3.插入新结点：①新结点的指针域指向结点ai，
②结点a（i-1）的指针域指向新结点。

//在L中第i个元素之前插入数据元素e
int ListInsert(LinkList& L, int i, ElemType e) {LinkList p = L;int j = 0;while (p && j < i-1)//寻找第i-1个结点，p指向i-1个结点{p = p->next; ++j;}if (!p || j > i - 1) {//i大于表长+1或者小于1，插入位置非法return 0;}LinkList &s = new LNode;//生成新的结点s，将结点s的数据域置为es->data = e;s->next = p->next;//将结点s插入L中p->next = s;return 1;
}

删除----删除第i个结点

【算法步骤】
1.首先找到a（i-1）的存储位置p，保存想要删除的a的值。
2.令p->next指向a(i+1).
3.释放结点ai的空间。

//将线性表的第i个数据元素删除
int ListDelete(LinkList& L, int i, ElemType& e) {LinkList p = L;LinkList q;int j = 0;while (p->next && j < i - 1) {//寻找第i个结点，并令p指向其前驱p = p->next;++j;}if (!(p->next) || j > i - 1) {//删除位置不合理return 0;}q = p->next;//临时保存被删除结点的地址p->next = q->next;//将删除节点后一个的指针域赋给删除结点的指针域，从而实现覆盖e = q->data;//保存删除结点的指针域delete q;//释放删除结点的空间return 1;}

单链表上的查找，插入，删除算法时间效率分析

1.查找
因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O（n）。
2.插入和删除

• 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O（1）。
• 但是，在链表中要进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为0(n)。