有用数据结构LinkedList.ppt

回顾 数组 Arrays类 Arrays.sort() Arrays.binarySearch() Arrays.fill() Arrays.asList() ArrayList类 结构特点 常用方法：size(), isEmpty(),contains(),indexOf(),toArray(), get(),set(),add(),addAll(),remove(),clear() 课前检查 创建一个类Cat 包含属性name，在构造方法中进行初始化 添加一个方法show()，用以打印name属性的值 创建一个类CatTest，添加main方法，实现 创建一个ArrayList，向其中添加几个Cat对象 遍历该集合，并且对每个Cat对象调用show()方法 参考代码 本讲目标 掌握List接口的另一个实现类：LinkedList类 掌握由LinkedList类构成的数据结构的特点（对比顺序表的存取特点） 掌握LinkedList类的常用方法（对比ArrayList类） 链表 单向链表 链表 链表 循环链表 链表 双向循环链表 LinkedList类 LinkedList类 LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。 注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List： 　　　　List list = Collections.synchronizedList(new LinkedList(...)); 常用方法 新增以下新方法： 构造方法LinkedList() getFirst()和getLast() removeFirst()和removeLast() addFirst()和addLast() 与ArrayList类中相同的方法 contains() size() add() remove() addAll() clear() get() set() indexOf() List接口和LinkedList类 开发一套小型的新闻管理系统，要求如下： 可以添加头条新闻标题 可以删除末条新闻标题 List接口和LinkedList类 List接口和ArrayList类 第二步：确定存储对象 1、创建类型：新闻标题 2、包含属性： ID、名称、创建者、创建时间 List接口和LinkedList类 第二步：具体实现 1、添加第一条、以及最末条新闻标题 2、获取第一条、以及最末条新闻标题 3、删除第一条、以及最末条新闻标题 练习 创建一个类Stack，代表堆栈（其特点为：后进先出），添加方法add(Object obj)、以及delete( )，添加main方法进行验证，要求： 使用LinkedList实现堆栈 在向LinkedList中添加时，使用addLast( )方法 在从LinkedList中取出时，使用removeLast( )方法 参考代码 public class Stack { private LinkedList list = new LinkedList(); public void add(Object obj){ list.addLast(obj); } public Object delete(){ return list.removeLast(); } public static void main(String[] args){ Stack stack = new Stack(); stack.add(1); stack.add(2); System.out.println(stack.get()); } } 使用集合框架注意事项 总结 读程序 ArrayList和LinkedList的比较 ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表(double-linked list)完成，其内每个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素。 如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。 public class FirstLevelTitleDB { public static void main(String[ ] args)