`

Java中的Collection和Map(二)--List体系

 
阅读更多

 正如我们在Java中的Collection和Map(一)中所看到的那样,我们经常使用的有ArrayList、LinkedList、Vector、Stack。这里不再累述它们的使用方法,这里主要是说一下他们的底层结构以及使用时机。

 1、ArrayList

  我们都知道ArrayList是我们经常使用的List集合之一。我们在使用的时候经常通过 new ArrayList() 方法来创建一个ArrayList集合,然后调用它的 add(E e) 方法向集合中存储元素。那么你是否了解当我们使用 new 关键字来创建一ArrayList 集合时底层究竟做了什么事情呢?其实当我们使用new ArrayList()创建集合的时候,底层创建了一个Object类型的数组,初始化长度为0,当我们首次调用 add(E e) 方法的时候,数组长度初始化我10。我们都知道 ArrayList 在一定长度内是没有 限制长度的。既然初始时ArrayList 底层用于存放元素的数组长度为10,那么当我们添加第11 个元素的时候数组角标就会越界。这就牵扯到ArrayList的扩容机制。下面让我们来看一下ArrayList 到底是如何扩容的。

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       // minCapacity is usually close to size, so this is a win:
       elementData = Arrays.copyOf(elementData, newCapacity);
   }

从上面代码中我们发现 ArrayList 在扩容时候。底层数组长度增加原来的1/2。将原数组中的数据通过Arrays.copyOf 方法拷贝到新数组中,原数组指向新的数组。

综上所述:我们知道了ArrayList底层数据结构其实就是一Object类型的数组。当我们频繁的想ArrayList 中添加元素时ArrayList扩容会影响一定的效率。

2、LinkedList

  LinkedList 也是我们经常使用的List集合之一。LinkedList 的使用方法和ArrayList的使用方法大致相同。不过LinkedList 多了些自己特有的方法(这源自于LinkedList和ArrayList 底层数据结构的不同)--addFirst(E e)、addLast(E e),下面我们就来看一下LinkedList 底层数据结构。

  构造方法:

  public LinkedList() {
  }

  当我们通过 new LinkedList() 创建已LinkedList 集合的时候其实就是 new 了一个简单的java 类 ,但当我们使用add(E e) 方法想集合中添加元素时就和ArrayList不同了。

复制代码
 public void addFirst(E e) {
    linkFirst(e);
  }

  public void addLast(E e) {
    linkLast(e);
  }

  public boolean add(E e) {
    linkLast(e);
    return true;
  }

void linkLast(E e) {
  final Node<E> l = last;
  final Node<E> newNode = new Node<>(l, e, null);
  last = newNode;
  if (l == null)
  first = newNode;
  else
  l.next = newNode;
  size++;
  modCount++;
}

private void linkFirst(E e) {
  final Node<E> f = first;
  final Node<E> newNode = new Node<>(null, e, f);
  first = newNode;
  if (f == null)
  last = newNode;
  else
  f.prev = newNode;
  size++;
  modCount++;
}
 private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
复制代码

  我们从源码中无论是 addFirst、addLast 还是add 方法调用的方法 linkFirst 或者linkLast 方法,而linkLast 又是通过 将一个个Node 结点通过指向的方式将他们连接起来,从中我们可以看出LinkedList 底层是一种自定义的数据结构---链表,在add(E e) 方法的时候不会牵扯到扩容问题。

3、ArrayList和LinkedList  比较

  1. ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构。
  2. 对于随机访问get和set,ArrayList优于LinkedList,因为LinkedList要移动指针。
  3. 对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据还有增加数据时候会牵扯到扩容 (这里只是理论上分析,事实上也不一定,ArrayList在末尾插入和删除数据的话,速度反而比LinkedList要快)。
  4. 随机查找指定节点的操作get,ArrayList速度要快于LinkedList.

4、Vector

  Vector底层也是采用数组结构来实现的。整体来说和ArrayList差不多。但还存在不同之处:

  1. Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe),而ArrayList的方法不是,由于线程的同步必然要影响性能,因此,ArrayList的性能比Vector好。
  2. 当Vector或ArrayList中的元素超过它的初始大小时,Vector会将它的容量翻倍,而ArrayList只增加50%的大小,这样,ArrayList就有利于节约内存空间。
1
2
3
4
5
6
7
8
9
10
11
//Vector扩容方法:<br>private void grow(int minCapacity) {
       // overflow-conscious code
       int oldCapacity = elementData.length;
       int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                        capacityIncrement : oldCapacity);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       elementData = Arrays.copyOf(elementData, newCapacity);
   }

5、Stack(栈)

  它是Vector的子类。Stack(栈)的特性是先进后出。

  Stack 类表示后进先出(LIFO)的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ,允许将向量视为堆栈。它提供了通常的 push 和 pop 操作,以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。
  首次创建堆栈时,它不包含项。
  直接Stack()创建一个空栈
  方法摘要:
   方法摘要
 boolean empty() 
          测试堆栈是否为空。
 E peek() 
          查看堆栈顶部的对象,但不从堆栈中移除它。
 E pop() 
          移除堆栈顶部的对象,并作为此函数的值返回该对象。
 E push(E item) 
          把项压入堆栈顶部。
 int search(Object o) 
          返回对象在堆栈中的位置,以 1 为基数。
  我们再来看下Stack 的源码:
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
public
class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }
 
    /**
     * Pushes an item onto the top of this stack. This has exactly
     * the same effect as:
     * <blockquote><pre>
     * addElement(item)</pre></blockquote>
     *
     * @param   item   the item to be pushed onto this stack.
     * @return  the <code>item</code> argument.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);
 
        return item;
    }
 
    /**
     * Removes the object at the top of this stack and returns that
     * object as the value of this function.
     *
     * @return  The object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();
 
        obj = peek();
        removeElementAt(len - 1);
 
        return obj;
    }
 
    /**
     * Looks at the object at the top of this stack without removing it
     * from the stack.
     *
     * @return  the object at the top of this stack (the last item
     *          of the <tt>Vector</tt> object).
     * @throws  EmptyStackException  if this stack is empty.
     */
    public synchronized E peek() {
        int     len = size();
 
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
 
    /**
     * Tests if this stack is empty.
     *
     * @return  <code>true</code> if and only if this stack contains
     *          no items; <code>false</code> otherwise.
     */
    public boolean empty() {
        return size() == 0;
    }
 
    /**
     * Returns the 1-based position where an object is on this stack.
     * If the object <tt>o</tt> occurs as an item in this stack, this
     * method returns the distance from the top of the stack of the
     * occurrence nearest the top of the stack; the topmost item on the
     * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
     * method is used to compare <tt>o</tt> to the
     * items in this stack.
     *
     * @param   o   the desired object.
     * @return  the 1-based position from the top of the stack where
     *          the object is located; the return value <code>-1</code>
     *          indicates that the object is not on the stack.
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);
 
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
 
    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}
  1. 通过peek()方法注释The object at the top of this stack (the last item of the Vector object,可以发现数组(Vector)的最后一位即为Stack的栈顶
  2. pop、peek以及search方法本身进行了同步
  3. push方法调用了父类的addElement方法
  4. empty方法调用了父类的size方法
  5. Vector类为线程安全类

  综上,Stack类为线程安全类

  Stack并不要求其中保存数据的唯一性,当Stack中有多个相同的item时,调用search方法,只返回与查找对象equal并且离栈顶最近的item与栈顶间距离。

 

分享到:
评论

相关推荐

    Java_Collection_List-Set-Map.zip_list set map

    在Java编程语言中,集合框架是处理对象组的重要工具,主要包括List、Set和Map三大接口。这些接口由Java Collection Framework提供,它是一个统一的架构,用于存储和操作各种类型的对象。接下来,我们将深入探讨这三...

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

    Java 集合类 List-Set-Map 的区别和联系 Java 集合类 List、Set 和 Map 是 Java 语言中最基本的集合类,它们之间存在着紧密的联系和区别。在本文中,我们将对 Java 集合类 List、Set 和 Map 的区别和联系进行详细的...

    Collection-and-Map.zip_java list map

    关于Map,List,collection集合遍历,泛型等

    java-collection-all-in-one.pdf

    Java集合框架由Collection和Map两大父接口统领。Collection接口是List、Set和Queue的父接口,用于存储单一数据类型的集合;Map接口用于存储键值对集合,由不同的实现类支持不同的访问机制和顺序特性。 List接口是...

    JavaMap.rar_arraylist map_collection_java map_javamap_地图 java

    在Java中,Map接口不继承Collection接口,而是独立存在,因为它代表的是键值对(key-value)的关系,而不是单个元素的线性序列。 Map接口提供了多种实现类,如HashMap、TreeMap、LinkedHashMap等,每种实现类有不同...

    Collection、Map、List、Set、Iterator

    ### Collection、Map、List、Set、...以上就是关于 `Collection`、`Map`、`List`、`Set` 和 `Iterator` 的详细解析,这些概念和类是 Java 编程中非常基础且重要的部分,掌握它们有助于更好地理解和使用 Java 集合框架。

    java Collection&Map

    在这个框架中,Collection和Map接口及其实现类扮演着核心角色。 1. **Collection接口**: - Collection是所有单值容器的基接口,包括Set和List接口。 - **Set接口**:不允许重复元素,主要实现有HashSet、TreeSet...

    java笔记整理(超详细) java笔记整理(超详细)

    - `Collection`接口是所有集合类的根接口,分为`List`和`Set`两大分支。 - `List`接口包括`ArrayList`和`LinkedList`等实现,`ArrayList`适合随机访问,`LinkedList`适合频繁的插入和删除操作。 - `Map`接口用于...

    Java集合:Collection、List、Set、Map使用详解

    本文将深入探讨Java集合框架中的四个主要接口:Collection、List、Set和Map,以及它们的实现原理。 ### 集合框架概述 集合框架是Java API中用于存储和管理对象的统一框架。它为数据结构提供了抽象接口,使得程序员...

    Collection,List,Set和_Map用法和区别

    Collection, List, Set 和 Map 用法和区别 Collection 是 Java 中的一种对象...Collection、List、Set 和 Map 等集合类是 Java 中非常重要的一部分,需要深入了解其用法和区别,以便更好地使用集合类来实现业务逻辑。

    Java集合Collection、List、Set、Map使用详解编程资料

    Java集合Collection、List、Set、Map使用详解

    Java集合Collection、List、Set、Map使用详解.pdf

    Java集合类包括Collection、List、Set、Map等,每个集合类都有其特点和使用场景。Collection接口是Java集合框架的根接口,定义了基本的集合操作,而List接口和Set接口继承自Collection接口,提供了有序和无序的集合...

    java collection framework

    - `Collections.max()` 和 `Collections.min()`: 获取 List 中的最大值和最小值。 - `Collections.binarySearch()`: 在已排序的 List 中进行二分查找。 #### 六、使用注意事项 在使用 Java Collection Framework ...

    Java集合Collection、List、Set、Map使用详解.doc

    Java 集合框架中的容器可以分为两大类:Collection 和 Map。Collection 是一个接口,定义了容器的基本操作,而 Map 则是键值对的容器。 1.2 Collection Collection 是 Java 集合框架中的一个接口,定义了容器的...

    Java集合排序及java集合类详解(Collection、List、Map、Set)

    ### Java集合排序及java集合类详解(Collection、...以上是对Java集合框架中的`Collection`、`List`、`Set`和`Map`的详细介绍,涵盖了它们的基本概念、常用方法、实现原理等方面,希望对理解和使用Java集合有所帮助。

Global site tag (gtag.js) - Google Analytics