我的日常

登录/注册
您现在的位置:论坛 盖世程序员(我猜到了开头 却没有猜到结局) 盖世程序员 > ArrayList和LinkedList的区别
总共48087条微博

动态微博

查看: 1183|回复: 1

ArrayList和LinkedList的区别

[复制链接]

95

主题

3

听众

2157

金钱

版主

  • TA的每日心情
    开心
    2019-10-29 10:01
  • 签到天数: 13 天

    [LV.3]偶尔看看II

    优秀版主

    跳转到指定楼层
    楼主
    发表于 2017-02-13 16:35:08 |只看该作者 |倒序浏览
    首先来看ArrayList和LinkedList的集成类和接口的区别。
    • public class ArrayList<E> extends AbstractList<E> implements List<E>,
    •         RandomAccess, Cloneable, Serializable
    • public class LinkedList<E> extends AbstractSequentialList<E> implements
    •         List<E>, Deque<E>, Cloneable, Serializable9 D/ m& n0 B  a, y
    ArrayList实现了随机访问的接口,LinkedList实现了Deque双向队列的接口,最终继承的是Queue。
      ArrayList是基于数据实现的list,而LinkedList是基于链表实现的list。所以,ArrayList拥有着数组的特性,LinkedList拥有着链表的特性。
    优缺点
    % t- ^" `! T% L9 g& U: \* H  ArrayList
      优点:适合随机读取的时候,读取速度快,可以一步get(index)。
      缺点:添加值很慢——一方面,添加数据在array中间的时候,需要移动后面的数;另一方面,当长度大于初始长度的时候,每添加一个数,都会需要扩容。
      LinkedList:双向链表
      优点:添加值很快——添加在list中间也只需要更改指针;长度不固定。
      实现栈和队列方面,LinkedList要优于ArrayList。
    其它
    2 B$ n9 g( u: X1 n% X  LinkedList的remove(int)和remove(Object)的方法的时间复杂度都是O(n),不是O(1).因为会有一个查找的过程。
      LinkedList的remove(int)要优于remove(Object),因为remove(int)在查找的时候,会从链表的中间查找,如果int比中间小,找前半部分,否则找后半部分(类似二分查找)。
      ArrayList的增删比LinkedList的开销更大,因为除了有查找的时间复杂度外,还有增删的移动过程。
    使用LinkedeList实现对链表的排序(sougou笔试题)
    • //LinkedList<Integer>实现链表的排序   使用插入排序
    •     public LinkedList<Integer> insertSortForLinkedList(LinkedList<Integer> list){
    •         int len=list.size();
    •         for(int i=1;i<len;i++){
    •             int j=i-1;
    •             int temp=list.get(i);
    •             list.remove(i);  //注意这里需要删除元素  
    •             while(j>=0&&temp<list.get(j)){
    •                 j--;   
    •             }
    •             list.add(j+1,temp);
    •         }
    •         return list;
    •     }' o. K+ n4 r# c

    4 G) J* w5 M& e1 R2 U9 L

    科帮网 1、本主题所有言论和图片纯属会员个人意见,与本社区立场无关
    2、本站所有主题由该帖子作者发表,该帖子作者与科帮网享有帖子相关版权
    3、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和科帮网的同意
    4、帖子作者须承担一切因本文发表而直接或间接导致的民事或刑事法律责任
    5、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责
    6、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除并致以最深的歉意
    7、科帮网管理员和版主有权不事先通知发贴者而删除本文


    JAVA爱好者①群:JAVA爱好者① JAVA爱好者②群:JAVA爱好者② JAVA爱好者③ : JAVA爱好者③

    已有 1 人评分帮币 收起 理由
    屁孩儿二 + 1 棒棒的

    总评分:  帮币 + 1         查看全部评分

    45

    主题

    0

    听众

    142

    金钱

    三袋弟子

    该用户从未签到

    沙发
    发表于 2017-02-13 22:02:20 |只看该作者
    你个 小逗比~~~
    回复

    使用道具 举报

    快速回复
    您需要登录后才可以回帖 登录 | 立即注册

       

    关闭

    站长推荐上一条 /1 下一条

    发布主题 快速回复 返回列表 联系我们 官方QQ群 科帮网手机客户端
    快速回复 返回顶部 返回列表