实用数据结构LinkedList.ppt

1 回顾 数组Arrays类Arrays sort Arrays binarySearch Arrays fill Arrays asList ArrayList类结构特点常用方法 size isEmpty contains indexOf toArray get set add addAll remove clear 2 顺序表便于查找操作 而插入和删除元素时要大量移动元素 首先分析 插入元素时 线性表的逻辑结构发生什么变化 3 a1 ai 1 ai an 改变为 a1 ai 1 e ai an 4 插入算法时间复杂度分析 考虑移动元素的平均情况 插入位置 需要移动的结点次数 1 n 2 n 1 n 1 n 1 0 平均次数 1 2 n 1 n n 1 n 2 T n O n 5 其次分析 删除元素时 线性表的逻辑结构发生什么变化 6 a1 ai 1 ai ai 1 an 改变为 a1 ai 1 ai 1 an ai 1 an 表的长度减少 7 删除算法时间复杂度分析 考虑移动元素的平均情况 删除位置 需要移动的结点次数 1 n 1 2 n 2 n 0 平均次数 0 1 n 11 n n 1 2 T n O n 8 课前检查 创建一个类Cat包含属性name 在构造方法中进行初始化添加一个方法show 用以打印name属性的值创建一个类CatTest 添加main方法 实现创建一个ArrayList 向其中添加几个Cat对象遍历该集合 并且对每个Cat对象调用show 方法 9 参考代码 classCat privateStringname publicCat Stringname this name name publicvoidshow System out println name publicclassCatTest publicstaticvoidmain String args 创建一个ArrayList 向其中添加几个Cat对象 ArrayListlist newArrayList list add newCat mimi list add newCat qiqi list add newCat ding 遍历该集合 并且对每个Cat对象调用show 方法 for inti 0 i list size i Catc Cat list get i c show 10 掌握List接口的另一个实现类 LinkedList类掌握由LinkedList类构成的数据结构的特点 对比顺序表的存取特点 掌握LinkedList类的常用方法 对比ArrayList类 本讲目标 11 用一组地址任意的存储单元存放线性表中的数据元素 数据元素之间的逻辑关系是由结点中的指针域指示的 不要求物理地址相邻 访问时必须从头指针开始 顺序访问 不能随机访问 通常 使用有头结点的单链表 单链表 12 以元素 数据元素的映象 指针 指示后继元素存储位置 结点 表示数据元素或数据元素的映象 以 结点的序列 表示线性表 称作链表 13 链表 单向链表 data next data next data next null head节点 14 链表 data next data next data next null head节点 插入 data next data next data next data next null head节点 删除 15 线性表的操作 插入在单链表中的实现 有序对改变为和 16 线性表的操作 删除在单链表中的实现 有序对和改变为 17 链表 循环链表 data next data next data next head节点 18 链表 双向循环链表 data next data next data next head节点 previous previous previous 19 LinkedList类 20 LinkedList类 LinkedList实现了List接口 允许null元素 此外LinkedList提供额外的get remove insert方法在LinkedList的首部或尾部 这些操作使LinkedList可被用作堆栈 stack 队列 queue 或双向队列 deque 注意LinkedList没有同步方法 如果多个线程同时访问一个List 则必须自己实现访问同步 一种解决方法是在创建List时构造一个同步的List Listlist Collections synchronizedList newLinkedList 21 常用方法 新增以下新方法 构造方法LinkedList getFirst 和getLast removeFirst 和removeLast addFirst 和addLast 与ArrayList类中相同的方法contains size add remove addAll clear get set indexOf 22 List接口和LinkedList类 开发一套小型的新闻管理系统 要求如下 可以添加头条新闻标题可以删除末条新闻标题 存储方式如何选择 元素个数不确定 使用集合类 需要在列表的头或尾添加 删除元素 23 List接口和LinkedList类 第一步 确定存储方式1 LinkedList类是List接口的一个具体实现类2 LinkedList类用于创建链表数据结构3 插入或者删除元素时 它提供更好的性能 24 List接口和ArrayList类 第二步 确定存储对象1 创建类型 新闻标题2 包含属性 ID 名称 创建者 创建时间 publicclassFirstLevelTitle privateintid IDprivateStringtitleName 名称privateStringcreater 创建者privateDatecreateTime 创建时间publicFirstLevelTitle intid StringtitleName Stringcreater DatecreateTime this id id this titleName titleName this creater creater this createTime createTime publicStringgetTitleName returntitleName publicvoidsetTitleName StringtitleName this titleName titleName 25 List接口和LinkedList类 第二步 具体实现1 添加第一条 以及最末条新闻标题2 获取第一条 以及最末条新闻标题3 删除第一条 以及最末条新闻标题 publicclassFirstLevelTitleDB publicstaticvoidmain String args FirstLevelTitlecar newFirstLevelTitle 1 汽车 管理员 newDate FirstLevelTitlemedical newFirstLevelTitle 2 医学 管理员 newDate LinkedListnewsTitleList newLinkedList newsTitleList addFirst car newsTitleList addLast medical FirstLevelTitlefirst FirstLevelTitle newsTitleList getFirst System out println 头条的新闻标题为 first getTitleName FirstLevelTitlelast FirstLevelTitle newsTitleList getLast System out println 排在最后的新闻标题为 last getTitleName newsTitleList removeFirst newsTitleList removeLast 1 2 3 26 练习 创建一个类Stack 代表堆栈 其特点为 后进先出 添加方法add Objectobj 以及delete 添加main方法进行验证 要求 使用LinkedList实现堆栈在向LinkedList中添加时 使用addLast 方法在从LinkedList中取出时 使用removeLast 方法 27 参考代码 publicclassStack privateLinkedListlist newLinkedList publicvoidadd Objectobj list addLast obj publicObjectdelete returnlist removeLast publicstaticvoidmain String args Stackstack newStack stack add 1 stack add 2 System out println stack get 28 使用集合框架注意事项 Object Object Object 加入集合 从集合中取出 Rabbit object Car object Student object Rabbit Car Student Rabbit Car Student 任何对象加入集合类后 自动转变为Object类型 取出时 需要进行强制类型转换 恢复为特定的类型 29 总结 publicclassFirstLevelTitleDB publicstaticvoidmain String args FirstLevelTitlecar newFirstLevelTitle 1 汽车 管理员 newDate FirstLevelTitletest newFirstLevelTitle 2 高考 管理员 newDate ListnewsTitleList newArrayList newsTitleList put car newsTitleList put test print newsTitleList publicstaticvoidprint ArrayListnewsList for inti 0 i newsList size i FirstLevelTitletitle FirstLevelTitle newsList get i System out println i 1 title getTitleName 应使用add方法向ArrayList中添加元素 无法接收List类型的参数 采用面向接口编程的思想 此处改为List 请指出下面Java代码中的错误 30 读程序 publicclassLinkedListDemo publicstaticvoidmain String args LinkedListlnkList newLinkedList lnkList add 李四 lnkList add 赵六 addFirst Object 表示加到最前lnkList addFirst 张三 addLast Object 表示加到最后lnkList addLast 王五 下面显示链表中的元素System out println lnkList 下面增加并显示链表中的元素lnkList addLast 憨豆 System out println lnkList 下面从链表中删除一项lnkList removeFirst 下面显示链表中的元素System out println lnkList 31 ArrayList和LinkedList的比较 ArrayList底层采用数组完成 而LinkedList则是以一般的双向链表 double linkedlist 完成 其内每个对象除了数据本身外 还有两个引用 分别指向前一个元素和后一个元素 如果我们经常在List的开始处增加元素 或者在List中进行插入和删除操作 我们应该使用LinkedList 否则的话 使用ArrayList将更加快速