专栏首页IT笔记ArrayList和LinkedList的区别

ArrayList和LinkedList的区别

首先来看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, Serializable

ArrayList实现了随机访问的接口,LinkedList实现了Deque双向队列的接口,最终继承的是Queue。

  ArrayList是基于数据实现的list,而LinkedList是基于链表实现的list。所以,ArrayList拥有着数组的特性,LinkedList拥有着链表的特性。

优缺点   ArrayList

  优点:适合随机读取的时候,读取速度快,可以一步get(index)。

  缺点:添加值很慢——一方面,添加数据在array中间的时候,需要移动后面的数;另一方面,当长度大于初始长度的时候,每添加一个数,都会需要扩容。

  LinkedList:双向链表

  优点:添加值很快——添加在list中间也只需要更改指针;长度不固定。

  实现栈和队列方面,LinkedList要优于ArrayList。

其它   LinkedList的remove(int)和remove(Object)的方法的时间复杂度都是O(n),不是O(1).因为会有一个查找的过程。

  LinkedList的remove(int)要优于remove(Object),因为remove(int)在查找的时候,会从链表的中间查找,如果int比中间小,找前半部分,否则找后半部分(类似二分查找)。

  ArrayList的增删比LinkedList的开销更大,因为除了有查找的时间复杂度外,还有增删的移动过程。

使用LinkedeList<Integer>实现对链表的排序(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;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • springMVC配置 国际化实现中英文切换

    一.基于session的国际化实现: 首先配置我们项目的springservlet-mvc.xml文件添加的内容如下: <bean id="messageSou...

    小柒2012
  • Nginx学习之location匹配规则

    介绍 location指令是http模块当中最核心的一项配置,根据预先定义的URL匹配规则来接收用户发送的请求,根据匹配结果,将请求转发到后台服务器、非法的请求...

    小柒2012
  • Linux下安装 Python3

    Linux下大部分系统默认自带python2.x的版本,最常见的是python2.6或python2.7版本,默认的python被系统很多程序所依赖,比如cen...

    小柒2012
  • 杨老师带你深入研究ArrayList和LinkedList的区别不同

    ArrayList实现了随机访问的接口,LinkedList实现了Deque双向队列的接口,最终继承的是Queue。

    杨校
  • 对比java和python

    对比java和python    1.难易度而言。python远远简单于java。   2.开发速度。Python远优于java   3.运行速度。...

    py3study
  • 解决:Throwable:Stub index points to a file without PSI: com.intellij.openapi.fileTypes.UnknownFileType

    1. IDEA 报错:stub index point to a file without PSI

    微风-- 轻许--
  • XML快速入门学习笔记

    问:什么是 XML? 答:XML 指可扩展标记语言(EXtensible Markup Language);且是一种很像HTML的标记语言;设计宗旨是传输数据,...

    WeiyiGeek
  • Go 译文之词法分析与解析 Part Three

    最近发现我的翻译是越来越随性了,刚开始文章翻译的时候比较拘束,现在更多强调可读性,比如有些对文章大意没有什么影响的文字我现在都会选择直接跳过。

    波罗学
  • 关于IDEA的激活,我又来更新了……

    这个问题对我而言是已知的,只是已知没更新,因为我在公司的办公电脑的IDEA也遇到了这个问题,只是解决后没及时更新文章,正好看到有同学和我一样就喜欢用最新版,于是...

    软件测试君
  • 跟我学Kafka之NIO通信机制

    很久没有做技术方面的分享了,今天闲来有空写一篇关于Kafka通信方面的文章与大家共同学习。

    小程故事多

扫码关注云+社区

领取腾讯云代金券