首页 > 代码库 > ArrayList与LinkedList实现比较

ArrayList与LinkedList实现比较

2024-07-18 11:26:52   224人阅读

1、ArrayList实现是基于数组来实现的，这可由ArrayList的源码看出；

1 public class ArrayList<E> extends AbstractList<E>2         implements List<E>, RandomAccess, Cloneable, java.io.Serializable3 {4     private transient Object[] elementData;5 6     private int size;7     8     /*其他参数和方法*/9 }

 

ArrayList是List接口的长度可变的数组实现。

2、LinkedList是List和Deque接口的双向链表的实现，但是Java中并没有指针的概念，遂查看源码；

 1 public class LinkedList<E> 2     extends AbstractSequentialList<E> 3     implements List<E>, Deque<E>, Cloneable, java.io.Serializable 4 { 5     private transient Entry<E> header = new Entry<E>(null, null, null); 6     private transient int size = 0; 7  8     /** 9      * 构造器，构建空表10      */11     public LinkedList() {12         header.next = header.previous = header;13     }14 15     /*其他参数、方法*/16 17     /**18     * LinkedList链表元素19     */20     private static class Entry<E> {21     E element;22     Entry<E> next;23     Entry<E> previous;24 25     Entry(E element, Entry<E> next, Entry<E> previous) {26         this.element = element;27         this.next = next;28         this.previous = previous;29     }30     }31  32     /**33     * LinkedList获取第一个元素的方法实现34     */35     public E getFirst() {36     if (size==0)37         throw new NoSuchElementException();38 39     return header.next.element;40     }41 42 }

 

LinkedList利用私有静态类Entry定义了链表所用的数据成员。在Entry类中，每个类成员除了含有数据部分，还包括两个分别指向前一链表元素和后一链表元素的Entry类型的引用变量（跟C++中的指针很相似），由这种结构构成了LinkedList的链表结构。

注：ArrayList与LinkedList的实现都是不同步的。


联系
我们