《实用数据结构LinkedList.ppt》由会员分享，可在线阅读，更多相关《实用数据结构LinkedList.ppt（31页珍藏版）》请在三一办公上搜索。
1、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,插入算法时间复杂度分析：考虑移
2、动元素的平均情况,插入位置,需要移动的结点次数,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，在构造方法中进行初始化
3、 添加一个方法show()，用以打印name属性的值 创建一个类CatTest，添加main方法，实现 创建一个ArrayList，向其中添加几个Cat对象 遍历该集合，并且对每个Cat对象调用show()方法,9,参考代码,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，向其中添加
4、几个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类）,本讲目标
5、,11,用一组地址任意的存储单元存放线性表中的数据元素。数据元素之间的逻辑关系是由结点中的指针域指示的。不要求物理地址相邻，访问时必须从头指针开始，顺序访问，不能随机访问。通常，使用有头结点的单链表。,单链表,12,以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表 称作链表,13,链表,单向链表,data,next,data,next,data,nextnull,head节点,14,链表,data,next,data,next,data,nextnull,head节点,插入,data,next,data,next,da
6、ta,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
7、，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：List list=Collections.synchronizedList(new LinkedList(.);,21,常用方法,新增以下新方法：构造方法LinkedList()getFirst()和getLast()removeFirst()和removeLast()add
8、First()和addLast()与ArrayList类中相同的方法contains()size()add()remove()addAll()clear()get()set()indexOf(),22,List接口和LinkedList类,开发一套小型的新闻管理系统，要求如下：可以添加头条新闻标题可以删除末条新闻标题,存储方式如何选择？,元素个数不确定,使用集合类,需要在列表的头或尾添加、删除元素,23,List接口和LinkedList类,第一步，确定存储方式 1、LinkedList类是List接口的一个具体实现类2、LinkedList 类用于创建链表数据结构3、插入或者删除元素时，它提
9、供更好的性能,24,List接口和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.titl
10、eName=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 sta
11、tic 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)newsTitleL
12、ist.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)、以及delet
13、e()，添加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)Stac
14、k 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 s
15、tatic 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(
16、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
17、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);,31,ArrayList和LinkedList的比较,ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表(double-linked list)完成，其内每个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素。如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。,
