之前完成了单向链表的创建和遍历,这里来说说如何插入与删除。
因为链表的特性,插入与删除十分方便,只需要在前后两个结点进行操作。而数组等连续存储则必须重新申请全部数据的空间,并且复制。因此插入与删除时,链表效率较高( ̄^ ̄゜)

单向链表之插入

还是使用《数据结构与算法学习:单向链表之构造与遍历》中的代码,先创建一个链表。
生成链表

0->2->4->6->8->10->12->14->16->18

此时假设给定一个int,要求按数值大小插入链表中,此时有几步需要完成

  1. 寻找要插入的位置
  2. 创建新数据结点,插入数据,指针域指向插入位置的下一个结点
  3. 修改前一数据结点的指针域,指向该新数据结点
  • 一个普遍的情形是,该位置在链表中,此时需要遍历并通过比较数据大小来找到位置。
  • 另一个特殊的情形则是,该位置位于第一个结点,此时第三步则变成修改head指针指向新结点。
    (当链表存在头结点时还得处理下头结点的问题,注意“头结点”≠“第一个数据结点”,头结点并不用于存储数据,本文中不设头结点)

函数原型:void Insert(List *&head, List *node);

首先考虑特殊情形,当要插入的位置刚好位于链表首部时,此时较容易检测出,直接将node与head的数据比较即可(不会的自己回去复习( •̀д•́) ),而后直接执行第二步生成新结点后返回。

1
2
3
4
5
6
if ( node->data <= head->data ) //1. 检测特殊情形
{
node->pNext = head; // 2. 指向之前的第一个第一个结点
head = node; //3. 修改
return ; //完成了插入操作,可以返回啦
}

更普遍的情形,就需要遍历链表并逐个比较数据大小啦( ̄^ ̄゜)

1
2
3
4
5
6
7
8
9
10
11
12
List *q = head->pNext, *p = head; // 因为首位置是特殊情形已处理,从第二个结点开始比较
while (q != NULL)
{
if ( node->data > q->data )
{
p = q;
q = q->pNext; //继续向下遍历
}else{
break; //找到位置,退出循环
}

}

结束循环后,p所指向的即为要插入数据的前一结点
而后插入新结点

1
2
p->pNext = node;
node->pNext = q;

此时插入完成,执行返回return ;
整个函数如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Insert(List *&head, List *node) //必须保证链表中数据为升序
{
if ( node->data <= head->data )
{
node->pNext = head;
head = node;
return ;
}
List *q = head->pNext, *p = head;
while (q != NULL)
{
if ( node->data > q->data )
{
p = q;
q = q->pNext;
}else{
break;
}
}
p->pNext = node;
node->pNext = q;
return ;
}

最后,我们可以用点小技巧,即可认为第一个结点之前还存在一个NULL结点,即可将该两种情形的代码逻辑合并,处理链表问题中这也是个思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Insert(List *&head, List *node) //必须保证链表中数据为升序
{
List *q = head, *p = NULL; //从第一个结点开始比较,设置第一个结点的前一个结点为NULL
while (q != NULL)
{
if ( node->data > q->data )
{
p = q;
q = q->pNext;
}else{
break;
}
}
if (p != NULL) //要注意空指针问题,否则可能引起异常
p->pNext = node;
else
head = node; //特殊情形,修改head指针指向新结点
node->pNext = q;
return ;
}

单向链表之删除

还是这个链表,与插入大同小异,除了插入中的那些坑,还需要注意下内存的释放。
直接上代码算了。相信只要会插入就可以看懂下面这段(/ω\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void delete(List *&head, int data)
{
List *q = head, *p = NULL;
while (q != NULL)
{
if ( data != q->data )
{
p = q;
q = q->pNext;
}else{
break;
}
}
if (p != NULL){
p->pNext = q->pNext; //链接前后结点
}else{
head = q->pNext; //修改head指针
}
delete q; //释放从链表脱离的结点所占用内存,否则内存泄漏
return ;
}

自我吐槽:懒癌无药可救╮( ̄⊿ ̄)╭