`

Java集合工具类之List - ArrayList & LinkedList

 
阅读更多

1.ArrayList 的数据结构和工作原理

与 Vector 一样, ArrayList 的 基本数据结构也是一个可变(动态)数组,数组的元素可以是任意对象。

ArrayList 的构造器有两种:

public ArrayList()

默认构造器的数组的长度是 10

public ArrayList(int initialCapacity)

指定 ArrayList 的初始化大小很重要, ArrayList 当添加元素的数量大于初始化(或上一次)数组的大小时,数组自动扩容成 oldSize*3/2+1, 新数组的元素是从老的数组 copy 而来的。

 

2.ArrayList 使用时需要注意的问题

1) ArrayList 使用时,最好能够预期需要存放元素的个数,这样可以避免数组长度频繁的改变而引起数据的 copy带来的开销,同时会引起内存大小的增加。

2 )使用 ArrayList 需要知道 ArrayList 是非线程安全的。因此,在使用时,最好是考虑这个对象会不会因为多个线程访问该 ArrayList 对象,如果确认多个线程访问,则可以用 Vector 或者 CopyOnWriteArrayList 来代替 ArrayList。

 

. LinkedList 的数据结构和工作原理

LinkedList 的基本数据结构是双向循环链表。链表的优点是插入和删除快,而查找或者修改比较慢。因为插入操作不会像 ArrayList 那样基于数组的数据结构,当插入时,超过原数组尺寸时,会将原数组的尺寸变成原来的3*size/2+1, 然后将原来数组的元素拷贝到新数组中,基于链表的操作只需将目标元素的尾部链接到原来链表的尾部就可以了。删除机制是同样的,基于数组的 ArrayList ,要删除元素,需要将该元素后面所有的元素向前 move一位。

 

构造器:

private transient Entry<E> header new Entry<E>( null null null );

 

// 初始花一个空的 header 链表,并将首尾相连成一个双向循环链表

public LinkedList() {

        header . next header . previous header ;

}

/**

核心方法之一:获取 index 位置的链表信息。此方法在 get , remove , add , set 都会用到

此处用到了二分查找来提高效率,如果 index

* 是在链表的前半段,则从头开始遍历,如果 index 在链表的后半部分,则从链尾遍历

  */

    private Entry<E> entry ( int index) {

        if (index < 0 || index >= size )

            throw new IndexOutOfBoundsException( "Index: " +index+

                                                ", Size: " + size );

        Entry<E> e = header ;

        if (index < ( size >> 1)) {

            for ( int i = 0; i <= index; i++)

                e = e. next ;

        } else {

            for ( int i = size ; i > index; i--)

                e = e. previous ;

        }

        return e;

}

 

/**

核心方法之一:将新的 e 元素, add 在指定 entry 的前面

  */

private Entry<E> addBefore (E e, Entry<E> entry) {

    Entry<E> newEntry = new Entry<E>(e, entry, entry. previous );

    newEntry. previous . next = newEntry;

    newEntry. next . previous = newEntry;

    size ++;

    modCount ++;

    return newEntry;

}

/**

将指定元素放在 header 之前,实际上就是放在链表的尾部

  */

public boolean add (E e) {

    addBefore(e, header );

        return true ;

}

/**

找到指定位置的元素,并将指定元素放在查找处的前面

  */

 

public void add ( int index, E element) {

        addBefore(element, (index== size header : entry(index)));

}

 

2. LinkedList 的其它应用

LinkedList 的双向性,可以轻松做一个 Stack 和 Queue :

public class LinkedListQueue <E> extends LinkedList<E>{

   

    //Like poll/remove

    public E dequeue(){

       return this .removeFirst();

    }

   

    //Like offer/add

    public void enqueue(E e){

       this .add(e);

    }

   

    //Like peek

    public E getHeader(){

       return this .getFirst();

    }

   

    public boolean empty(){

       return this .size()==0;

    }

}

分享到:
评论

相关推荐

    Java集合类List-Set-Map的区别和联系.doc

    Collections 是 Java 中提供的一个工具类,提供了对集合类的操作方法,如 sort()、binarySearch()、max() 等。Collections 类提供了对集合类的搜索、排序、线程安全等操作。 四、如何选择集合类 在选择集合类时,...

    【IT十八掌徐培成】Java基础第10天-03.List-集合框架-ArrayList.zip

    本课程“【IT十八掌徐培成】Java基础第10天-03.List-集合框架-ArrayList”深入讲解了Java中的ArrayList类,这是集合框架中的一个重要组成部分,特别适用于对元素有序且可变大小的需求。 ArrayList是Java.util包下的...

    huihua-java-kuangjia-wendang&code

    2. **Java集合框架**:Java集合框架是处理对象组的重要工具,包括List(如ArrayList和LinkedList)、Set(如HashSet和TreeSet)和Map(如HashMap和TreeMap)接口以及实现这些接口的类。 3. **异常处理**:Java通过...

    java提高篇(二一)-----ArrayList.pdf

    为了使用线程安全的ArrayList,可以使用Collections工具类提供的synchronizedList方法,该方法会返回一个线程安全的List的包装器。需要注意的是,这只是一个包装器,如果需要在多个线程之间共享ArrayList实例,应该...

    Core Java(Volume-I&II;--Fundamentals 9th Edition).rar

    5. **数组和集合**:讲解数组的使用,以及Java集合框架,包括List、Set、Map接口及其实现类,如ArrayList、LinkedList、HashSet、HashMap等。 6. **字符串处理**:介绍String类的特性和常用方法,以及StringBuilder...

    Java集合排序及java集合类详解.pdf

    ### Java集合排序及Java集合类详解 #### 一、集合框架概述 集合框架是Java编程语言的核心组件之一,用于组织和操作数据集。Java集合框架提供了多种数据结构,包括列表(List)、集(Set)和映射(Map),这些数据结构...

    java日常处理工具类part1-代码

    2. **集合操作**:在Java中,ArrayList、LinkedList、HashSet、HashMap等集合类广泛使用。工具类可能会提供一些便利的集合转换、过滤、排序等功能,例如`reverse(List&lt;?&gt; list)`反转列表,`isEmptyOrNull(Collection...

    java的集合类教学

    - Collections工具类提供了很多静态方法,如对List进行排序(sort())、查找最大或最小元素(max()和min())、二分搜索(binarySearch())等。 - ArrayList和LinkedList各有特点,ArrayList适合频繁的随机访问,而...

    list集合案例增、删、改、查,ArrayList与LinkedList的区别,LinkedList堆栈/队列的开发

    在Java编程语言中,集合框架是处理对象数组的重要工具,其中`List`接口是最常用的集合类型之一。本篇文章将深入探讨`List`集合的各种操作,包括增、删、改、查,以及`ArrayList`和`LinkedList`两种实现`List`接口的...

    Java基础----集合类汇总

    Java集合框架还包含了一些工具类,如Collections和Arrays,它们提供了各种实用方法,如排序、复制、反转和查找集合中的特定元素。此外,Set和List接口都有一个叫做CopyOnWriteArrayList和CopyOnWriteArraySet的特殊...

    精通java集合框架--List,Set..

    ### 精通Java集合框架——List, Set, Map #### 概述 Java集合框架是一种高度抽象且灵活的数据组织工具,它通过一系列接口来定义不同类型的数据容器,并提供了丰富的操作这些容器的方法。本文将深入探讨Java集合...

    Java-Java集合教程

    - `List`:有序、允许重复元素的集合,例如ArrayList和LinkedList。 - `Set`:不允许重复元素的集合,如HashSet和TreeSet。 - `Queue`:用于队列操作的接口,如LinkedList(作为双端队列)和PriorityQueue。 2. ...

    02-Java集合容器面试题-重点.docx

    Java集合容器概述、集合框架、List、Set、Map接口、Iterator、ArrayList、LinkedList、Vector、HashSet、HashMap、Queue、BlockingQueue、ConcurrentHashMap等。 Java 集合容器概述 Java 集合容器是用于存储数据...

    Java集合类详解总结

    Java集合框架主要包括`Collection`、`Set`、`List`、`Queue`、`Deque`、`Map`等接口和它们的具体实现类如`ArrayList`、`LinkedList`、`Vector`、`Stack`、`HashSet`、`HashMap`等。下面将对这些核心概念和类进行深入...

    ArrayList-LinkedList:ArrayList和LinkedList的完整演示

    在Java编程语言中,ArrayList和LinkedList是两种常用的集合类,它们都实现了List接口,用于存储和操作有序的数据序列。这两个类各有特点,适用于不同的场景。本文将深入探讨ArrayList和LinkedList的内部实现、性能...

    java集合类的讲解文件

    3. **Collections**:Collections是Java提供的工具类,提供了对集合的各种操作,如排序(sort())、查找最大/最小元素(max()和min())以及二分查找(binarySearch())等。 此外,文件还涉及到了数据结构的基础知识...

    易语言仿java集合 list map源码

    标题提到的“仿java集合 list, 以及map工具类”,是指易语言中对Java集合框架的模拟实现。在Java中,List和Map是两种主要的数据结构。List是一种有序的集合,允许重复元素,可以按索引访问。常见的List实现有...

    java 集合分组与排序

    - `Collections.sort()`:适用于`List`接口的实现类,如`ArrayList`和`LinkedList`。它直接在原地对列表进行排序,无需额外的流处理。例如: ```java List&lt;Person&gt; people = ...; Collections.sort(people, ...

Global site tag (gtag.js) - Google Analytics