注册

已有账号?请登录

登录

还没账号?请注册

单链表的遍历、插入、删除和反转操作

单链列表可以定义为元素的有序集合的集合。元素的数量可以根据程序的需要而变化。单链列表中的节点由两部分组成:数据部分链接部分。节点的数据部分存储将由该节点表示的实际信息,而节点的链接部分存储其直接后继者的地址。

1. 在单链表开头插入数据

时间复杂度:平均情况 θ(1) 最坏情况 O(1)

上述代码输出

单链表: C -> B -> A

2. 在单链表结尾插入数据

时间复杂度:平均情况 θ(1) 最坏情况 O(1)

上述代码输出

单链表: A -> B -> C

3. 删除单链表开始节点

时间复杂度:平均情况 θ(1) 最坏情况 O(1)

上述代码输出

删除前: 单链表: A -> B -> C

删除后: 单链表: B -> C

3. 删除单链表结尾节点

时间复杂度:平均情况 θ(1) 最坏情况 O(1)

上述代码输出

删除前: 单链表: A -> B -> C

删除后: 单链表: A -> B

4. 查找节点

时间复杂度:平均情况 θ(n) 最坏情况 O(n)

上述代码输出

已找到A, 位置: 0

没找到a

5. 反转单链表

算法

  1. 定义3个节点(current/prev/next),current存储当前节点,prev存储上一个节点,next存储下一个节点
  2. 重复步骤3、4、5、6,直到链表末尾
  3. 将当前节点的next赋值给下一个节点,即 next = current->next
  4. 将当前节点的next指向上一个节点,即 current->next = prev
  5. 将当前节点赋值给上一个节点,即 prev = current
  6. 将下一个节点赋值给当前节点,即 current = next
  7. 到达链尾后,将head设置成prev,即 *head = prev

时间复杂度:O(n)

空间复杂度:O(1)

上述代码输出

反转前: 单链表: A -> B -> C

反转后: 单链表: C -> B -> A

本站所有文章均由阿坤原创,欢迎转载!

Copyright © 2020 luozk.com All Rights Reserved