MEI实用数据结构第三讲LinkedList.ppt

第三讲 LinkedList类 课程回顾 List接口 Iterator接口、ListIterator接口 ArrayList类 泛型 List接口 常见方法 对列表元素进行定位（索引）访问 特殊的迭代器——ListIterator 有哪些信誉好的足球投注网站指定对象 在任意位置插入和删除多个元素 课堂案例 创建一个类Cat 包含属性name，在构造方法中进行初始化 添加一个方法show()，用以打印name属性的值 创建一个类CatTest，添加main方法，实现 创建一个ArrayList，向其中添加几个Cat对象 遍历该集合，并且对每个Cat对象调用show()方法 本讲内容 LinkedList类 栈和队列 LinkedList类 定义 List 接口的链式存储实现 双向循环链表 实现List、Deque等接口 特点 优点 列表大小可变，存储空间分散 插入、删除元素不需移动大量元素，效率较高 在列表头部和尾部进行操作效率极高 缺点 顺序访问 应用 LinkedList提供专门方法来操作列表的头部和尾部，故可被用作LIFO（后进先出）堆栈 ，FIFO（先进先出）队列或双端队列（Deque）。 常用方法 新增以下新方法 构造方法LinkedList() getFirst()和getLast() removeFirst()和removeLast() addFirst()和addLast() 与ArrayList类中相同的方法 contains() size() add() remove(i) addAll() clear() get(i) set() indexOf() lastIndexOf() iterator() listIterator() toArray() 基本操作实现一 getFirst() getLast() 基本操作实现二 removeFirst() removeLast() remove(i) remove(o) for(Entry e=header.next; e!=header; e=e.next) if(o.equals(e.element)) remove(e); remove(Entry e)删除算法思想 确定被删除的元素 修改其前驱和后继引用 释放其空间 表长减1 基本操作实现三 addFirst(e) addLast(e) add(e) addBefore(e,entry)插入算法思想 生成新的Entry 修改指针 表长加1 基本操作实现四 indexOf(Object o) lastIndexOf(Object o) 基本操作实现五 get(int index) set(int index,E element) add(int index,E element) remove(int index) Queue接口——队列 队列通常（但并非一定）以 FIFO（先进先出）的方式排序各个元素。 队尾插入、队头删除 基本操作方法 Deque接口——双端队列 Deque 是“Double ended queue（双端队列）”的缩写 两端插入和移除元素 接口扩展了Queue接口 基本操作方法 双端队列应用一——FIFO 在将双端队列用作队列时，将得到 FIFO（先进先出）行为 将元素添加到双端队列的末尾，从双端队列的开头移除元素 双端队列应用二——LIFO 双端队列也可用作 LIFO（后进先出）堆栈 应优先使用此接口而不是遗留 Stack类 在将双端队列用作堆栈时，元素被推入双端队列的开头并从双端队列开头弹出 * * 实用数据结构 授课人：李群 E-MAIL: sdbzlq@126.com javaruan3wang3@163.com (happyjava) get(i)、set(i,e)、add(i,e)、remove(i) listIterator()、 listIterator(i) 允许元素插入、替换、 双向访问 contains(o)、remove(o)、indexOf(o)、lastIndexOf(o) addAll(i,c)、removeAll() 除数据本身外，还有两个引用， 分别指向前驱和后继 a:空表 b:非空表 a1 a2 … ... an 基本形态示意图： header 条件：header.next==header且 header.previo