`
sanry
  • 浏览: 36635 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

浅谈JAVA容器之list

阅读更多

1、  list

          1、ArrayList

 

publicclass ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 

AbstractList继承了AbstractCollection类实现了List

AbstractCollection又实现Collection类。List也是继承了Collection

ArrayList存储的形式是一个数组,读取时可以按下标读取。插入的时候是把要插入的数据放到对应的位置,在把之前此位置之后的所有数据重新拷贝到,插入数据之后。

publicvoid add(int index, E element) {

        rangeCheckForAdd(index);

 

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        System.arraycopy(elementData, index, elementData, index + 1,

                         size - index);

        elementData[index] = element;

        size++;

    }

 

A、set(int index, E element)方法与add(int index, E element)

 

set(int index, E element)就是将 index位替换为element

 

add(int index, E element)set方法不同的是,add是先将index位移到size+1位,然后再将element放到index位。

 

 

        public E set(int index, E e) {

            rangeCheck(index);

            checkForComodification();

            E oldValue = ArrayList.this.elementData(offset + index);

            ArrayList.this.elementData[offset + index] = e;

            return oldValue;

        }

 

B、remove(int index),remove(Object o) removeRange(int fromIndex, int toIndex)

remove(int index)移除第index位,index+1位开始向前移动一位,然后将size位置为null

remove(Object o)通过比较移除O对象,index+1位开始向前移动一位,然后将size位置为null

removeRange(int fromIndex, int toIndex)移除从fromIndex位到toIndex位的对象

    public E remove(int index) {

        rangeCheck(index);

 

        modCount++;

        E oldValue = elementData(index);

 

        int numMoved = size - index - 1;

        if (numMoved > 0)

            System.arraycopy(elementData, index+1, elementData, index,

                             numMoved);

        elementData[--size] = null; // clear to let GC do its work

 

        return oldValue;

    }

 

    publicboolean remove(Object o) {

        if (o == null) {

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

                if (elementData[index] == null) {

                    fastRemove(index);

                    returntrue;

                }

        } else {

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

                if (o.equals(elementData[index])) {

                    fastRemove(index);

                    returntrue;

                }

        }

        returnfalse;

    }

    protectedvoid removeRange(int fromIndex, int toIndex) {

        modCount++;

        int numMoved = size - toIndex;

        System.arraycopy(elementData, toIndex, elementData, fromIndex,

                         numMoved);

 

        // clear to let GC do its work

        int newSize = size - (toIndex-fromIndex);

        for (int i = newSize; i < size; i++) {

            elementData[i] = null;

        }

        size = newSize;

    }

 

C、addAll(Collection c)addAll(int index,Collection c)

addAll(Collection c)直接从最后位置添加对象

addAll(int index,Collection c)先将原index位及以后的所有位添加到index+c.size以后的位置。再将c放到从index位往后放。相当于在将c对象从index位开始插入,原数据依次往后推。

publicboolean addAll(Collection<? extends E> c) {

        Object[] a = c.toArray();

        int numNew = a.length;

        ensureCapacityInternal(size + numNew);  // Increments modCount

        System.arraycopy(a, 0, elementData, size, numNew);

        size += numNew;

        return numNew != 0;

    }

publicboolean addAll(int index, Collection<? extends E> c) {

        rangeCheckForAdd(index);

 

        Object[] a = c.toArray();

        int numNew = a.length;

        ensureCapacityInternal(size + numNew);  // Increments modCount

 

        int numMoved = size - index;

        if (numMoved > 0)

            System.arraycopy(elementData, index, elementData, index + numNew,

                             numMoved);

 

        System.arraycopy(a, 0, elementData, index, numNew);

        size += numNew;

        return numNew != 0;

    }

A、 D、removeAll(Collection<?> c)retainAll(Collection<?> c)

Are       moveAll删除cretainAll保留c

 

publicboolean removeAll(Collection<?> c) {

        return batchRemove(c, false);

    }

publicboolean retainAll(Collection<?> c) {

        return batchRemove(c, true);

    }

privateboolean batchRemove(Collection<?> c, boolean complement) {

        final Object[] elementData = this.elementData;

        int r = 0, w = 0;

        boolean modified = false;

        try {

            for (; r < size; r++)

if (c.contains(elementData[r]) == complement)

                    elementData[w++] = elementData[r];

        } finally {

            // Preserve behavioral compatibility with AbstractCollection,

            // even if c.contains() throws.

            if (r != size) {

                System.arraycopy(elementData, r,

                                 elementData, w,

                                 size - r);

                w += size - r;

            }

            if (w != size) {

                // clear to let GC do its work

                for (int i = w; i < size; i++)

                    elementData[i] = null;

                modCount += size - w;

                size = w;

                modified = true;

            }

        }

        return modified;

    }

E、subList(int fromIndex, int toIndex)

此方法意思是取fromIndex位到toIndex位作为一个新的ArrayList。实际上原list没有变而是新建了一个内部类重写了Arraylist的方法,每个涉及到指定位置的地方都index都变成index+fromIndex

 

    public List<E> subList(int fromIndex, int toIndex) {

        subListRangeCheck(fromIndex, toIndex, size);

        returnnew SubList(this, 0, fromIndex, toIndex);

    }

 SubList部分代码:

privateclass SubList extends AbstractList<E> implements RandomAccess {

        privatefinal AbstractList<E> parent;

        privatefinalintparentOffset;

        privatefinalintoffset;

        intsize;

 

        SubList(AbstractList<E> parent,

                int offset, int fromIndex, int toIndex) {

            this.parent = parent;

            this.parentOffset = fromIndex;

            this.offset = offset + fromIndex;

            this.size = toIndex - fromIndex;

            this.modCount = ArrayList.this.modCount;

        }

2、LinkedList

linkedlist存储单元形式是Node<E>Node有三个属性:

E item;(当前存储内容)

               Node<E> next;(下一个节点内容)

Node<E> prev;(上一个节点内容)

每个节点都包括这三个属性,就构成了链表的形式。

所以linkedlist中的添加删除插入等方法都是通过改变每个Node节点的nextprev来实现的。

链头的prevnull链尾的next同样也是null

linkedList有三个属性size-长度,first-链头,last-链尾。Firstlast分别就是在链头和链为的Node<E>

privatestaticclass 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;

        }

    }

LinkedList插入时只需要修改相应位置的prevnext就可以。然而ArrayList如果要进行插入操作,插入的时候是把要插入的数据放到对应的位置,在把之前此位置之后的所有数据重新拷贝到,插入的数据之后。由此可见LinkedList插入要比ArrayList快。然而ArrayList读取的时候很方便。可以直接找到位置,LinkedList读取需要循环的读。

3、Vector

继承AbstractList类,实现List接口。也是list的一个实现类。Vector存储的形式是一个Object数组

public Vector(int initialCapacity, int capacityIncrement) {

        super();

        if (initialCapacity < 0)

            thrownew IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        this.elementData = new Object[initialCapacity];

        this.capacityIncrement = capacityIncrement;

    }

Vector的对外方法都用synchronized修饰,也就是说vector其实就是一个线程安全的ArrayList

Stack:

Stack继承自Vector,是Vector的一个扩展类。此类扩展的比较简单,只扩展了pushpoppeeksearch

Push():就是调用VectoraddElement方法,就是在数组最后增加添加一个数据

public E push(E item) {

        addElement(item);

 

        return item;

    }

    publicsynchronizedvoid addElement(E obj) {

        modCount++;

        ensureCapacityHelper(elementCount + 1);

        elementData[elementCount++] = obj;

    }

pop():是从数组最后删除一个数据

peek():是获取数组最后一个数据。

这几个增加、删除、获取的方法就是实现了堆栈的概念(先进后出)。

search(Object o):就是循环比较,然后返回o在数组中的位置。

还有一个heap()的概念heapstack的异同点还没有具体研究。

 

 

分享到:
评论

相关推荐

    Java应用:两种Java容器类List和Set分析

    ### Java应用:两种Java容器类List和Set分析 #### 一、概述 在Java编程语言中,集合框架(Collections Framework)是处理数据的核心组件之一,它提供了存储和操作对象的各种方式。本文将深入探讨Java中的两种重要...

    java容器详细解析

    Java容器详细解析 Java容器是一种基本的数据结构,用于存储和管理对象。Java容器主要分为两大类:Collection和Map。 Collection Collection是一个独立元素的序列,这些元素都服从一条或多条规则。Collection接口...

    JAVA容器效率深度分析List

    ArrayList是最常用的List实现之一,基于动态数组实现。它的优点在于随机访问速度快,因为可以通过索引直接定位到元素,但插入和删除元素(特别是中间位置)时,需要移动大量元素,效率较低。因此,当需要频繁进行...

    java容器学习心得

    1. **Collection容器**:这是Java中最基础的容器类型,它包括`List`、`Set`等子接口,用于存储一组不重复的对象。关键方法包括: - `boolean add(Object obj)`:向集合添加一个元素。 - `Iterator iterator()`:...

    JAVA容器的概述,List,Map,Set

    JAVA容器的概述,List,Map,Set

    浅谈C++容器.pdf

    本文旨在通过解析《浅谈C++容器》的内容,帮助读者深入了解C++容器的基本概念、分类及其背后的原理。 #### 二、容器的基本概念 容器是C++标准库中用于存储和管理数据的一种机制。它们提供了一种高效的方式来组织和...

    Java容器类List、ArrayList、Vector及map、HashTable应用

    Java容器类List、ArrayList、Vector及map、HashTable应用 List、ArrayList、Vector及map、HashTable是Java中常用的容器类,它们都继承自Collection接口,并提供了不同的实现方式和特点。在实际开发中,选择合适的...

    JAVA容器知识积累

    在这个主题下,我们将深入探讨Java中的核心容器类,包括数组、List、Set和Map,以及它们各自的特点和使用场景。 1. **数组**:数组是最基本的容器形式,它允许存储相同类型的数据元素,并通过索引来访问。数组提供...

    java 数组转list list转数组 list数组互转

    java 数组转list list转数组 list数组互转 java8 代码示例

    java容器(持有对象)

    在Java中,常见的容器主要分为三类:List、Set和Map,这些都是Java集合框架的重要组成部分。 首先,我们来看Collection接口,它是所有单值容器的基础接口。Collection接口定义了通用的操作方法,比如size()返回容器...

    Java 容器.pdf_电子版pdf版

    Java 容器详解 Java 容器是 Java 语言中的一种集合类库,主要包括 Collection 和 Map 两种类型。Collection 存储着对象的集合,而 Map 存储着键值对(两个对象)的映射表。 Collection Collection 是一种集合接口...

    浅谈java集合框架

    ### 浅谈Java集合框架 Java集合框架是一个用于存储、操作和检索一组对象的强大工具集。集合框架的设计目的是为了提供一套高效且灵活的数据结构来满足不同的应用需求。本篇文章将详细探讨Java集合框架中的一些核心...

    JAVA容器的作用和概览

    Java容器(集合框架)是Java编程中极其重要的部分,它提供了多种数据结构,如列表、集合和映射,以适应不同场景下的数据存储和处理需求。通过合理选择和使用不同的容器,可以优化代码的性能和可维护性。同时,了解和...

    java List 深度复制方法

    在Java编程中,数据结构是程序设计的基础,而List接口作为集合框架的重要组成部分,常常用于存储有序的元素序列。当我们需要复制一个List时,可能会遇到浅复制和深复制的概念。浅复制只复制对象本身,而不复制它引用...

    JAVA容器讲解.pdf

    Java容器讲解PPT,Collection Map(HashMap TreeMap LinkedHashMap) List (ArrayList LinkedList Vector) Set (HashSet TreeSet LinkedHashSet)

    java练习题--容器使用练习

    在Java编程语言中,容器是用于存储对象的集合框架,它们提供了一种高效且灵活的方式来组织和管理数据。本练习题旨在帮助你深入理解和熟练掌握Java中的容器使用,特别是其核心类库`java.util`中的ArrayList、...

    Java 实现泛型List

    Java 实现泛型List的源码,基本实现了List接口的全部所有方法。欢迎大家发表自己的观点和建议。

    浅谈Java中的Set、List、Map的区别.docx

    Java 中的 Set、List、Map 的区别 Java 中的集合可以存储和操作数目不固定的一组数据。所有的 Java 集合都位于 java.util 包中!Java 集合只能存放引用类型的数据,不能存放基本数据类型。 Collection 接口是最...

Global site tag (gtag.js) - Google Analytics