文档章节

java中ArrayList和LinkedList的区别

天王盖地虎626
 天王盖地虎626
发布于 06/18 18:43
字数 666
阅读 42
收藏 1

首先来看ArrayList和LinkedList的集成类和接口的区别。

复制代码
// lang java
public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Queue<E>, Cloneable, Serializable
复制代码

  ArrayList实现了随机访问的接口,LinkedList实现了Quene的接口。

  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;
    }
复制代码
  • 使用LinkedeList实现栈和队列  

 Stack.java

复制代码
import java.util.*;

class Stack{
    private LinkedList list;
    public Stack(){
        list=new LinkedList();
    }
    
    public Object top(){   //输出最上面的元素
        if(list.size()!=0){
            return list.getFirst();
        }
        return -1;
    }
    
    public void pop(){   //出栈
        if(list.size()!=0){
            list.removeFirst();
        }
    }
    
    public void push(Object v){ //入栈
        list.addFirst(v);
    }
    
    public int getLen(){
        return list.size();
    }
}
复制代码

Test.java

复制代码
import java.util.*;

class Test{
    public static void main(String[] args){
        Stack stack = new Stack();
        stack.push("张三");
        stack.push(3);
        stack.push("李四");
        stack.push("5");
        System.out.println("长度---"+stack.getLen());  //4
        
        /**
        //注意这样写是有问题的,因为在出栈的过程中stack.getLen()是会发生变化的
        for(int i=0;i<stack.getLen();i++){   
            System.out.println(stack.top());
            stack.pop();
            //System.out.println("长度---"+stack.getLen());  //4
        }
        **/
        
        /**
        //正确
        int i=stack.getLen()-1;
        while(i>=0){
            System.out.println(stack.top());
            stack.pop();
            i--;
        }
        **/
        //正确,但是会引来不安全操作提醒
        while(stack.getLen()>0){   
            System.out.println(stack.top());
            stack.pop();
        }
        System.out.println(stack.top());
        stack.pop();
    }
}
复制代码

  为什么while的编译时间长于for循环。

本文转载自:https://www.cnblogs.com/lxq0309/p/3655742.html

天王盖地虎626

天王盖地虎626

粉丝 31
博文 522
码字总数 20708
作品 0
南京
私信 提问
Vector、ArrayList、LinkedList 有什么区别?

版权声明:本文供交流学习,能够帮助到你是我最大的荣幸! https://blog.csdn.net/u014231523/article/details/82086185 这个问题主要是考察集合框架的问题,主要考察三者之间的设计区别,以...

兴国First
2018/08/26
0
0
Java核心(四)你不知道的数据集合

导读:Map竟然不属于Java集合框架的子集?队列也和List一样属于集合的三大子集之一?更有队列的正确使用姿势,一起来看吧! Java中的集合通常指的是Collection下的三个集合框架List、Set、Q...

王磊的博客
2018/11/28
93
0
java面试题--基础知识(精化版)

版权声明:本文供交流学习,能够帮助到你是我最大的荣幸! https://blog.csdn.net/u014231523/article/details/89302178 1. JDK 和 JRE 有什么区别? JDK:Java Development Kit 的简称,Jav...

兴国First
04/14
0
0
关于java.util.Vector 或 java.util.Hashtable类过时的讨论

某些高级IDE在检测代码成熟问题时,会报告集合是否过时的问题。目前过时的集合类有两个java.util.Vector 和 java.util.Hashtable 。 Vector的api描述是:从jdk 1.2版本开始,该类被修正为实现...

Barudisshu
2013/09/10
2.2K
2
ArrayList和LinkedList的几种循环遍历方式及性能对比分析

最新最准确内容建议直接访问原文:ArrayList和LinkedList的几种循环遍历方式及性能对比分析 主要介绍ArrayList和LinkedList这两种list的五种循环遍历方式,各种方式的性能测试对比,根据Arr...

Trinea
2013/10/31
618
1

没有更多内容

加载失败,请刷新页面

加载更多

消息中间件——RabbitMQ的高级特性

前言 前面我们介绍了RabbitMQ的安装、各大消息中间件的对比、AMQP核心概念、管控台的使用、快速入门RabbitMQ。本章将介绍RabbitMQ的高级特性。分两篇(上/下)进行介绍。 消息如何保障100%的...

Java架构师ya七
45分钟前
8
0
如何编写高质量的 JS 函数(1) -- 敲山震虎篇

本文首发于 vivo互联网技术 微信公众号 链接:https://mp.weixin.qq.com/s/7lCK9cHmunvYlbm7Xi7JxQ 作者:杨昆 一千个读者,有一千个哈姆雷特。 此系列文章将会从函数的执行机制、鲁棒性、函...

vivo互联网技术
今天
7
0
学会这5个Excel技巧,让你拒绝加班

在网上,随处都可以看到Excel技巧,估计已看腻了吧?但下面5个Excel技巧会让你相见恨晚。关键的是它们个个还很实用 图一 技巧1:快速删除边框 有时当我们处理数据需要去掉边框,按Ctrl+Shif...

干货趣分享
今天
11
0
JS基础-该如何理解原型、原型链?

JS的原型、原型链一直是比较难理解的内容,不少初学者甚至有一定经验的老鸟都不一定能完全说清楚,更多的"很可能"是一知半解,而这部分内容又是JS的核心内容,想要技术进阶的话肯定不能对这个...

OBKoro1
今天
11
0
高防CDN的出现是为了解决网站的哪些问题?

高防CDN是为了更好的服务网络而出现的,是通过高防DNS来实现的。高防CDN是通过智能化的系统判断来路,再反馈给用户,可以减轻用户使用过程的复杂程度。通过智能DNS解析,能让网站访问者连接到...

云漫网络Ruan
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部