实用数据结构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,参考代码,class Cat private String name; public Cat(String name) = name; public void show() System.out.println(name); public class CatTest public static void main(String args) /创建一个ArrayList，向其中添加几个Cat对象； ArrayList list = new ArrayList(); list.add(new Cat(“mimi“); list.add(new Cat(“qiqi“); list.add(new Cat(“ding“); /遍历该集合，并且对每个Cat对象调用show()方法。 for(int i= 0;ilist.size();i+) Cat c = (Cat)list.get(i); c.show(); ,10,掌握List接口的另一个实现类：LinkedList类 掌握由LinkedList类构成的数据结构的特点（对比顺序表的存取特点） 掌握LinkedList类的常用方法（对比ArrayList类）,本讲目标,11,用一组地址任意的存储单元存放线性表中的数据元素。数据元素之间的逻辑关系是由结点中的指针域指示的。不要求物理地址相邻，访问时必须从头指针开始，顺序访问，不能随机访问。通常，使用有头结点的单链表。,单链表,12,以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表 称作链表,13,链表,单向链表,data,next,data,next,data,nextnull,head节点,14,链表,data,next,data,next,data,nextnull,head节点,插入,data,next,data,next,data,next,data,nextnull,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： List list = Collections.synchronizedList(new LinkedList(.);,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、名称、创建者、创建时间,public class FirstLevelTitle private int id; /ID private String titleName; /名称 private String creater; /创建者 private Date createTime; /创建时间 public FirstLevelTitle(int id, String titleName, String creater,Date createTime) this.id = id; this.titleName = titleName; this.creater = creater; this.createTime = createTime; public String getTitleName() return titleName; public void setTitleName(String titleName) this.titleName = titleName; ,25,List接口和LinkedList类,第二步：具体实现 1、添加第一条、以及最末条新闻标题 2、获取第一条、以及最末条新闻标题 3、删除第一条、以及最末条新闻标题,public class FirstLevelTitleDB public static void main(String args) FirstLevelTitle car = new FirstLevelTitle(1, “汽车“, “管理员“, new Date(); FirstLevelTitle medical = new FirstLevelTitle(2, “医学“, “管理员“,new Date(); LinkedList newsTitleList = new LinkedList(); newsTitleList.addFirst(car); newsTitleList.addLast(medical); FirstLevelTitle first = (FirstLevelTitle) newsTitleList.getFirst(); System.out.println(“头条的新闻标题为:“ + first.getTitleName(); FirstLevelTitle last = (FirstLevelTitle) newsTitleList.getLast(); System.out.println(“排在最后的新闻标题为:“ + last.getTitleName(); newsTitleList.removeFirst(); newsTitleList.removeLast(); ,1,2,3,26,练习,创建一个类Stack，代表堆栈（其特点为：后进先出），添加方法add(Object obj)、以及delete( )，添加main方法进行验证，要求： 使用LinkedList实现堆栈 在向LinkedList中添加时，使用addLast( )方法 在从LinkedList中取出时，使用removeLast( )方法,27,参考代码,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(); ,28,使用集合框架注意事项,Object,Object,Object,加入集合,从集合中取出,(Rabbit) object,(Car) object,(Student) object,Rabbit,Car,Student,Rabbit,Car,Student,任何对象加入集合类后，自动转变为Object类型；取出时，需要进行强制类型转换，恢复为特定的类型,29,总结,public class FirstLevelTitleDB public static void main(String args) FirstLevelTitle car = new FirstLevelTitle(1, “汽车“, “管理员“, new Date(); FirstLevelTitle test = new FirstLevelTitle(2, “高考“, “管理员“, new Date(); List newsTitleList = new ArrayList(); newsTitleList.put(car); newsTitleList.put(test); print(newsTitleList); public static void print(ArrayList newsList) for (int i = 0; i newsList.size(); i+) FirstLevelTitle title = (FirstLevelTitle)newsList.get(i); System.out.println(i + 1 + “:“ + title.getTitleName( ); ,应使用add方法向ArrayList中添加元素,无法接收List类型的参数。采用面向接口编程的思想，此处改为List,请指出下面Java代码中的错误,30,读程序,public class LinkedListDemo public static void main(String args) LinkedList lnkList = new LinkedList(); lnkList.add(“李四“); lnkList.add(“赵六“); / addFirst(Object)表示加到最前 lnkList.addFirst(“张三“); / addLast(Object)表示加到最后 lnkList.addLast(“王五“); / 下面显示链表中的元素 System.out.println(lnkList); / 下面增加并显示链表中的元素 lnkList.addLast(“憨豆“); System.out.println(lnkList); / 下面