实用数据结构LinkedList.ppt
回顾数组数组ArraysArrays类类Arrays.sort()Arrays.binarySearch()Arrays.fill()Arrays.asList()ArrayListArrayList类类结构特点常用方法：size(),isEmpty(),contains(),indexOf(),toArray(),get(),set(),add(),addAll(),remove(),clear()1顺序表便于查找操作，而插入和删除元素时要大量移动元素。首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？2(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加3插入算法时间复杂度分析：插入算法时间复杂度分析：考虑移动元素的平均情况考虑移动元素的平均情况插入位置插入位置需要移动的结点次数需要移动的结点次数1n2n-1n1n+10平均次数平均次数:(1+2+n-1+n)/(n+1)=n/2T(n)=O(n)4其次分析：删除元素时，线性表的逻辑结构发生什么变化？5(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 6 删除算法时间复杂度分析：删除算法时间复杂度分析：考虑移动元素的平均情况考虑移动元素的平均情况删除位置删除位置需要移动的结点次数需要移动的结点次数1n-12n-2n0平均次数平均次数:(0+1+n-11)/n=(n-1)/2T(n)=O(n)7课前检查创建一个类创建一个类Cat Cat 包含属性name，在构造方法中进行初始化 添加一个方法show()，用以打印name属性的值 创建一个类创建一个类CatTestCatTest，添加，添加mainmain方法，实现方法，实现 创建一个ArrayList，向其中添加几个Cat对象 遍历该集合，并且对每个Cat对象调用show()方法 8参考代码class Catprivate String name;public Cat(String name)this.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();9掌握掌握ListList接口的另一个实现类：接口的另一个实现类：LinkedListLinkedList类类掌握由掌握由LinkedListLinkedList类构成的数据结构的特点（对比类构成的数据结构的特点（对比顺序表的存取特点）顺序表的存取特点）掌握掌握LinkedListLinkedList类的常用方法（对比类的常用方法（对比ArrayListArrayList类）类）本讲目标10 用一组地址任意地址任意的存储单元存放存放线性表中的数据元素。数据元素之间的逻辑关系是由结点中的指针域指示的。不要求物理地址相邻，访问时必须从头指针开始，顺序访问，不能随机访问。通常，使用有头结点的单链表。单链表单链表11以元素元素(数据元素的映象数据元素的映象)+指针指针(指示后继元素存储位置指示后继元素存储位置)=结点结点 (表示数据元素 或 数据元素的映象数据元素的映象)以“结点的序列结点的序列”表示线性表 称作链表链表12链表单向链表单向链表datanextdatanextdatanextnullhead节点13链表datanextdatanextdatanextnullhead节点插入插入datanextdatanextdatanextdatanextnullhead节点删除删除14ai-1线性表的操作：插入在单链表中的实现：有序对有序对 改变为改变为 和和 eaiai-115线性表的操作：删除在单链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-116链表循环链表循环链表datanextdatanextdatanexthead节点17链表双向循环链表双向循环链表datanextdatanextdatanexthead节点previouspreviousprevious18LinkedList类19LinkedList类LinkedListLinkedList实现了实现了ListList接口，允许接口，允许nullnull元素。此外元素。此外LinkedListLinkedList提供额外的提供额外的getget，removeremove，insertinsert方法在方法在 LinkedListLinkedList的首部或尾部。这些操作使的首部或尾部。这些操作使LinkedListLinkedList可可被用作堆栈（被用作堆栈（stackstack），队列（），队列（queuequeue）或双向队列）或双向队列（dequedeque）。）。注意注意LinkedListLinkedList没有同步方法。如果多个线程同时访没有同步方法。如果多个线程同时访问一个问一个ListList，则必须自己实现访问同步。一种解决方，则必须自己实现访问同步。一种解决方法是在创建法是在创建ListList时构造一个同步的时构造一个同步的ListList：List list=List list=Collections.synchronizedList(new Collections.synchronizedList(new LinkedList(.);LinkedList(.);20常用方法新增以下新方法：新增以下新方法：构造方法LinkedList()getFirst()和getLast()removeFirst()和removeLast()addFirst()和addLast()与与ArrayListArrayList类中相同的方法类中相同的方法contains()size()add()remove()addAll()clear()get()set()indexOf()21List接口和LinkedList类开发一套小型的新闻管理系统，要求如下：开发一套小型的新闻管理系统，要求如下：可以添加头条新闻标题可以删除末条新闻标题存储方式如何选择？存储方式如何选择？元素个数不确定元素个数不确定使用集合类使用集合类需要在列表的头或尾添加、删除元素需要在列表的头或尾添加、删除元素22List接口和LinkedList类第一步，确定存储方式第一步，确定存储方式 1、LinkedList类是List接口的一个具体实现类2、LinkedList 类用于创建链表数据结构3、插入或者删除元素时，它提供更好的性能23List接口和ArrayList类第二步：确定存储对象第二步：确定存储对象1、创建类型：新闻标题2、包含属性：ID、名称、创建者、创建时间public class FirstLevelTitle private int id;/IDprivate 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;24List接口和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();12325练习创建一个类创建一个类StackStack，代表堆栈（其特点为：后进先出），代表堆栈（其特点为：后进先出），添加方法添加方法add(Object obj)add(Object obj)、以及、以及delete()delete()，添加，添加mainmain方法进行验证，要求：方法进行验证，要求：使用LinkedList实现堆栈在向LinkedList中添加时，使用addLast()方法在从LinkedList中取出时，使用removeLast()方法26参考代码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();27使用集合框架注意事项ObjectObjectObject加入集合加入集合从集合中取出从集合中取出(Rabbit)object(Car)object(Student)objectRabbitCarStudentRabbitCarStudent 任何对象加入集合类后，自动转变为任何对象加入集合类后，自动转变为Object类型；取出类型；取出时，需要进行强制类型转换，恢复为特定的类型时，需要进行强制类型转换，恢复为特定的类型 28总结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 请指出下面请指出下面JavaJava代码中的错误代码中的错误 29读程序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);/下面从链表中删除一项下面从链表中删除一项 lnkList.removeFirst();/下面显示链表中的元素下面显示链表中的元素 System.out.println(lnkList);30ArrayList和LinkedList的比较ArrayListArrayList底层采用数组完成，而底层采用数组完成，而LinkedListLinkedList则是以一则是以一般的双向链表般的双向链表(double-linked list)(double-linked list)完成，其内每个完成，其内每个对象除了数据本身外，还有两个引用，分别指向前一对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素。个元素和后一个元素。如果我们经常在如果我们经常在ListList的开始处增加元素，或者在的开始处增加元素，或者在ListList中进行插入和删除操作，我们应该使用中进行插入和删除操作，我们应该使用LinkedListLinkedList，否则的话，使用否则的话，使用ArrayListArrayList将更加快速。将更加快速。31
