专栏首页Java技术分享圈杨老师带你深入研究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实现对链表的排序(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 条评论
登录 后参与评论

相关文章

  • [人间也值得] - Mryang带你快速得去认识 Python

    计算机不能直接理解任何除机器语言以外的语言,所以必须要把程序员所写的程序语言翻译成机器语言,计算机才能执行程序。将其他语言翻译成机器语言的工具,被称为编译器

    杨校
  • IntellJ IDEA的常用快捷键和基础配置

    右侧有一个 Code Completion 下方是Case senstive completion:[ All | None | First Letter ]...

    杨校
  • [人间也值得] - Mryang带你快速入门第一个 Python 程序

    目前市场上有两个 Python 的版本并存着,分别是 Python 2.x 和 Python 3.x

    杨校
  • ArrayList和LinkedList的区别

    首先来看ArrayList和LinkedList的集成类和接口的区别。 public class ArrayList<E> extends AbstractLi...

    小柒2012
  • 对比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通信方面的文章与大家共同学习。

    小程故事多

扫码关注云+社区

领取腾讯云代金券