数据结构(五)链表
- 真正的动态数据结构
- 最简单的动态数据结构
- 可以深入的理解引用
- 可以深入的理解递归
LinkedList实现
内部类Node,用于存放数据和next;
LinkedList有一个Node类型的变量指向head。
- 在List头部添加元素
- 在List中间添加元素
- 删除List中指定位置的元素
- 修改List中指定位置的元素
- 查找指定位置的元素
注意:此处的List的实现都使用了虚拟头节点dummyHead,dummyHead的元素value为null,next指向索引为0的节点。
时间复杂度分析
这是的链表是单链表的分析:
- 增:,在链表头节点增加元素时间复杂度为;
- 删:,在链表头节点删除元素时间复杂度为;
- 改:
- 查:
用链表实现栈
用带有尾指针的链表实现队列
删除链表中的元素:
删除一个节点首先找到被删除节点之前的一个节点。如果是头节点需要单独处理,因为头节点没有前一个节点。另一种思路是加入虚拟头节点,统一操作。