精华内容
下载资源
问答
  • java常用集合集合讲解

    万次阅读 2018-07-04 13:32:59
    一、java集合系列 java的集合主要分为List列表、Set集合、Map映射、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections )java中集合类的关系图 由此图可以看到,主要分为Collection和Map两大类: 1....

    一、java集合系列(ArrayList、LinkedList)

            java的集合主要分为List列表、Set集合、工具类(Iterator迭代器、Enumeration枚举类、Arrays和Collections )


    java中集合类的关系图

           

    由此图可以看到,主要分为Collection和Map两大类:

           1.Collection:是单列集合的顶层父类,是一个独立元素的序列,这些个元素都服从一条或者多条规则。List必须按照插入的顺序保存元素,而Set不能有重复的元素。即Collection分为List和Set两大分支。

                1)List集合是一个有序的队列,每一个元素都有他的索引。第一个元素的索引值为0。

                        List的实现类有LinkedList、ArrayList、Vector、Stack。

                2)Set集合是一个不允许有重复元素的集合。

                        Set的实现类有HashSet、TreeSet。HashSet依赖于HashMap,他实际上是通过HashMap实现的;TreeSet依赖 于TreeMap,他实际是通过TreeMap实现的。

            2.Map:是双列集合的顶层父类接口,是一个映射接口,即key-Value键值对。允许使用键来查找对应的值,从某种意义上来说,他将数字和对象关联在一起。Map中的每一个元素包含"key"和"key对应的value"。

               1)AbstractMap是一个抽象类,它实现了Map接口中的大部分API。二HashMap、TreeMap、WeakHashMap都是继承了AbstractMap。Hashtable虽然继承与Dictionary,但是他实现了Map接口。

            3.再看看迭代器Iterator

                1)Iterator通常被称为轻量级对象,创建它的代价很小,它是遍历集合的工具,即我们通常通过Iterator迭代器来遍历集合。我们说Collection依赖于Iterator,是因为Collection的实现类都要实现iterator()函数,返回一个Iterator对象。后面再详细介绍。

    有了上面的整体框架之后,接下来我们对每个集合在具体介绍。

    二、ArrayList的基本概述

               ArrayList是一个数组队列,也是一个动态数组,其中的容量是自增长的。它继承与AbstractList,实现与List,RandomAccess,Cloneable,ava.io.Serializable这些接口。

            ArrayList线程是非安全的,一般使用在单线程的情况下,如果在多线程的情况下可以使用collections.synchronizedList(List 1)函数返回一个线程安全的ArrayList类。而且ArrayList也可以有null值。

    ArrayList的关注点

    关注点    结论
    集合底层的数据结构动态数组
    集合中的元素是否为空可以为空
    是否可以有重复的元素可以重复
    是否有序有序
    线程是否安全非安全(不同步)

    2.1 ArrayList的数据结构

              (1) 两个比较重要的对象

    /** 
          * The array buffer into which the elements of the ArrayList are stored. 
          * The capacity of the ArrayList is the length of this array buffer. 
          */  
         private transient Object[] elementData;  
    
         /** 
          * The size of the ArrayList (the number of elements it contains). 
          * 
          * @serial 
          */  
         private int size;

       ArrayList包含了两个比较重要的对象: elementData、size

            elementData是“Object[]类型的数组”,他保存了添加到ArrayList中的元素。实际上,elementData是一个动态数组,我们通过ArrayList(intinitialCapacity)来执行他的初始容量为initialCapacity;如果通过不包含参数的构造函数ArrayList()来创建ArrayList,则elementData的默认容量是10.elementData的容量会根据集合中元素的的容量增长而增长。

            size则是动态数组具体的长度。

            这里有一个关键字需要解释一下 : transient。  中文意思就是:短暂的,瞬时的。

            java中serializable提供了一种持久化对象实例的机制,当持久化对现实,我们可能会有一个特殊的对象数据成员,我们不想用serializable序列化机制来保存他。为了让一个特定对象的一个域关闭上serializable,我们可以用trasient来进行修饰。

            下面根据代码分析:

    public class User {
        private String name;
        private transient String password;
    
        public User(String name, String password) {
            this.name = name;
            this.password = password;
        }
    
    
        @Override
        public String toString() {
            return "User{" +
                    "name='" + name + '\'' +
                    ", password='" + password + '\'' +
                    '}';
        }
    }
    
    public static void main(String[] args) {
            //创建user对象
            User user = new User("张三","123");
            System.out.println("序列化前输出");
            System.out.println(user);
            //将对象进行序列化
            try {
                ObjectOutputStream os = new ObjectOutputStream(new FileOutputStream("user.out"));
                os.writeObject(user);
                os.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
    
            //使用序列化流读取序列后的文件
            try {
                ObjectInputStream oi = new ObjectInputStream(new FileInputStream("user.out"));
                User readUser  = (User) oi.readObject();
                System.out.println("序列化后输出");
                System.out.println(readUser.toString());
            } catch (Exception e) {
                e.printStackTrace();
            }
    
        }
    }

    当user的password属性被trasient修饰的结果:

    序列化前输出
    User{name='张三', password='123'}
    序列化后输出
    User{name='张三', password='null'}

    当user的password属性没有被trasient修饰的结果:

    序列化前输出
    User{name='张三', password='123'}
    序列化后输出
    User{name='张三', password='123'}

    结论:被trasient修饰的属性在对象进行序列化的时候不会被保存。

    2.2 ArrayList常用的API

    (1) 构造方法

    ArrayList提供了三种方式的构造器,可以构造一个初始容量为10的空列表、构造一个指定初始量的空列表以及构造一个包含指定collection的元素的列表,这些元素按照collection的迭代器返回他们的顺序进行排列的。

    // ArrayList无参构造函数。默认容量是10。    
        public ArrayList() {    
            this(10);    
        }   
    
    // ArrayList带容量大小的构造函数。    
        public ArrayList(int initialCapacity) {    
            super();    
            if (initialCapacity < 0)    
                throw new IllegalArgumentException("Illegal Capacity: "+    
                                                   initialCapacity);    
            // 新建一个数组    
            this.elementData = new Object[initialCapacity];    
        }    
    
        // 创建一个包含collection的ArrayList    
        public ArrayList(Collection<? extends E> c) {    
            elementData = c.toArray();    
            size = elementData.length;    
            if (elementData.getClass() != Object[].class)    
                elementData = Arrays.copyOf(elementData, size, Object[].class);    
        }

    (2) 元素存储

    ArrayList提供了 set(int index,E element)  add(E element) add(int index,E element) addAll(int index,Collection<? extends  E> c)

    // 用指定的元素替代此列表中指定位置上的元素,并返回以前位于该位置上的元素。  
    public E set(int index, E element) {  
       RangeCheck(index);  
    
       E oldValue = (E) elementData[index];  
       elementData[index] = element;  
       return oldValue;  
    }    
    
    // 将指定的元素添加到此列表的==尾部==。  
    public boolean add(E e) {  
       ensureCapacity(size + 1);   
       elementData[size++] = e;  
       return true;  
    }    
    
    // 将指定的元素插入此列表中的指定位置。  
    // 如果当前位置有元素,则向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。  
    public void add(int index, E element) {  
       if (index > size || index < 0)  
           throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  
       // 如果数组长度不足,将进行扩容。  
       ensureCapacity(size+1);  // Increments modCount!!  
       // 将 elementData中从Index位置开始、长度为size-index的元素,  
       // 拷贝到从下标为index+1位置开始的新的elementData数组中。  
       // 即将当前位于该位置的元素以及所有后续元素右移一个位置。  
       System.arraycopy(elementData, index, elementData, index + 1, size - index);  
       elementData[index] = element;  
       size++;  
    }    
    
    // 按照指定collection的迭代器所返回的元素顺序,将该collection中的所有元素添加到此列表的尾部。  
    public boolean addAll(Collection<? extends E> c) {  
       Object[] a = c.toArray();  
       int numNew = a.length;  
       ensureCapacity(size + numNew);  // Increments modCount  
       System.arraycopy(a, 0, elementData, size, numNew);  
       size += numNew;  
       return numNew != 0;  
    }    
    // 从指定的位置开始,将指定collection中的所有元素插入到此列表中。  
    public boolean addAll(int index, Collection<? extends E> c) {  
       if (index > size || index < 0)  
           throw new IndexOutOfBoundsException(  
               "Index: " + index + ", Size: " + size);  
    
       Object[] a = c.toArray();  
       int numNew = a.length;  
       ensureCapacity(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;  
       }

    常用的方法有add( E e) add(int index,E element) 注意set集合中add方法的不同,Set集合中元素不重复,因此执行add方法时,只有元素不存在的情况下才会添加,如果添加重复的就会把之前的替换掉。

    (3) 元素读取

    // 返回此列表中指定位置上的元素。  
      public E get(int index) {  
        RangeCheck(index);  
    
        return (E) elementData[index];  
      }

    (4) 截取字符串

    subList(int fromIndex, int  toIndex)是根据索引fromIndex和toIndex来获取父List的一个试图,注意,这里并不是创建了一个新的List,而只是原来的List的部分数据的一个试图,subList的任何操作都不会影响到原来的父List。

    public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }
    
    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
    }

    SubList是一个ArrayList内部的private类,构造函数如下

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

    这个SubList的任何操作都是基于ArrayList这个类的elementData这个数组来实现的。所以只是父类的一个试图。

    (5) 元素删除

    ArrayList提供了根据下标或指定对象两种方式的删除功能。如下:

    romove(int index)

    // 移除此列表中指定位置上的元素。  
     public E remove(int index) {  
     //检查index范围
        RangeCheck(index);  
    
      //修改modCount
        modCount++;  
        E oldValue = (E) elementData[index];  
       //保留将要被移除的元素,将移除位置之后的元素向前挪动一个位置,将list末尾元素置空(null),返回被移除的元素。
        int numMoved = size - index - 1;  
        if (numMoved > 0)  
            System.arraycopy(elementData, index+1, elementData, index, numMoved);  
        elementData[--size] = null; // Let gc do its work  
    
        return oldValue;  
     }

    remove(Object o)

    // 移除此列表中首次出现的指定元素(如果存在)。这是应为ArrayList中允许存放重复的元素。  
     public boolean remove(Object o) {  
        // 由于ArrayList中允许存放null,因此下面通过两种情况来分别处理。  
        if (o == null) {  
            for (int index = 0; index < size; index++)  
                if (elementData[index] == null) {  
                    // 类似remove(int index),移除列表中指定位置上的元素。  
                    fastRemove(index);  
                    return true;  
                }  
        } else {  
            for (int index = 0; index < size; index++)  
                if (o.equals(elementData[index])) {  
                    fastRemove(index);  
                    return true;  
                }  
            }  
            return false;  
        } 
    }
    
    private void fastRemove(int index) {  
             modCount++;  
             int numMoved = size - index - 1;  
             if (numMoved > 0)  
                 System.arraycopy(elementData, index+1, elementData, index,  
                                  numMoved);  
             elementData[--size] = null; // Let gc do its work  
     }

    removeRange(int fromIndex ,  int toIndex)

    protected void removeRange(int fromIndex, int toIndex) {  
         modCount++;  
         int numMoved = size - toIndex;  
             System.arraycopy(elementData, toIndex, elementData, fromIndex,  
                              numMoved);  
    
         // Let gc do its work  
         int newSize = size - (toIndex-fromIndex);  
         while (size != newSize)  
             elementData[--size] = null;  
    }

    执行过程是将elementData从toIndex位置开始的元素向前移动到fromIndex,然后将toIndex位置之后的元素全部置空顺便修改size。

    补充:

    一、ArrayList,优势在于随机访问元素,但是在List的中间插入和移除元素时较慢;LinkedList,通过代价较低的在List中间进行的插入和删除操作,提高了优化的顺序访问,而在随机访问方面相对比较慢。

    二、注意扩充容量的方法ensureCapacity。ArrayList在每次增加元素(可能是1个,也可能是一组)时,都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时,就设置新的容量为旧的容量的1.5倍加1,如果设置后的新容量还不够,则直接新容量设置为传入的参数(也就是所需的容量),而后用Arrays.copyof()方法将元素拷贝到新的数组。可以看出,当容量不够时,每次增加元素,都要将原来的元素拷贝到一个新的数组中,非常之耗时,也因此建议在事先能确定元素数量的情况下,才使用ArrayList,否则建议使用LinkedList。

    三、LinkedList的基本概述

           前面我们已经学了ArrayList,接下来我们学习LinkedList。

           LinkedList和ArrayList一样,都实现了List接口,和学习ArrayList一样,我们先对LinkedList有一个整体的认识。

     

    1. LinkedList的基本概述

    LinkedList 是一个继承于AbstractSequentialList的双向链表。实现了List、Deque、Cloneable、Java.io.serializable接口,它也可以被当作堆栈、队列或双端队列进行操作,。
    LinkedList 实现 List 接口,能对它进行队列操作。
    LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
    LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
    LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。

    由上面可以得到:LinkedList 是非线程安全的,集合中的元素允许为空,保存的元素为有序的,实现了List接口,则允许集合中的元素是可以重复的。

    面试易考点:

    关注点结论
    集合的底层数据结构双向链表
    集合中的元素是否可以重复可以重复
    集合中的元素是否有序有序
    集合中的元素是否可以为空  可以为空
    是否线程安全非安全(不同步的)

    2. LinkedList的数据结构

    LinkedList中定义了两个属性

    private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;
    
    private static class Entry<E> {
          E element;
          Entry<E> next;
          Entry<E> previous;
    
          Entry(E element, Entry<E> next, Entry<E> previous) {
              this.element = element;
              this.next = next;
              this.previous = previous;
         }
    }
    size:LinkedList对象中存储的元素个数。
    header:LinkedList是基于链表实现的,那么这个header肯定就是链表的头结点了,Entry就是节点对象了。

    Entry类中只定义了存储的元素、前一个元素、后一个元素,这就是双向链表的节点的定义,每个节点只知道自己的前一个节点和后一个节点。

    3. LinkedList的常用API

    (1) LinkedList的构造方法

    public LinkedList() {
        header.next = header.previous = header;
    }
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    第一个构造方法不接受参数,只是将header节点的前一节点和后一节点都设置为自身(注意,这是一个双向循环链表,如果不是循环链表,空链表的情况应该是header节点的前一节点和后一节点均为null),这样整个链表其实就只有header一个节点,用于表示一个空的链表。第二个构造方法接收一个Collection参数c,调用第一个构造方法构造一个空的链表,之后通过addAll将c中的元素全部添加到链表中。接下来看addAll类的具体内容。

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    // index参数指定collection中插入的第一个元素的位置
    public boolean addAll(int index, Collection<? extends E> c) {
        // 插入位置超过了链表的长度或小于0,会报IndexOutOfBoundsException异常
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+size);
        Object[] a = c.toArray();
        int numNew = a.length;
        // 若需要插入的节点个数为0则返回false,表示没有插入元素
        if(numNew==0)
            return false;
        modCount++;
        // 保存index处的节点。插入位置如果是size,则在头结点前面插入,否则获取index处的节         点
        Entry<E> successor = (index==size ? header : entry(index));
        // 获取前一个节点,插入时需要修改这个节点的next引用
        Entry<E> predecessor = successor.previous;
        // 按顺序将a数组中的第一个元素插入到index处,将之后的元素插在这个元素后面
        for (int i=0; i<numNew; i++) {
        // 结合Entry的构造方法,这条语句是插入操作,相当于C语言中链表中插入节点并修改指针
        Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
        // 插入节点后将前一节点的next指向当前节点,相当于修改前一节点的next指针
        predecessor.next = e;
        // 相当于C语言中成功插入元素后将指针向后移动一个位置以实现循环的功能
        predecessor = e;
        }
        // 插入元素前index处的元素链接到插入的Collection的最后一个节点
        successor.previous = predecessor;
        // 修改size
        size += numNew;
        return true;
    }

    构造方法中的调用了addAll(Collection

    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 {
         // 可以通过header节点向前遍历,说明这是一个循环双向链表,header的previous指向链表的最后一个节
        //点,这也验证了构造方法中对于header节点的前后节点均指向自己的解释
                for (int i = size; i > index; i--)
                    e = e.previous;
            }
            return e;
        }

    从上面的分析中以及双向循环链表的知识,相对比较容易理解LinkedList构造方法所涉及的内容。下面开始分析LinkedList的其他方法。

    (2) 元素存储

    LinkedList添加了add(E e)、addBefore(E e,Entry entry)、 add(int index,E e)、addFirst(E e)、 addLast(E e)等添加元素的方法。

    public boolean add(E e) {
         addBefore(e, header);
        return true;
    }

    add(E e)方法只是调用了addBefore(E e,Entry entry)方法,并且返回true

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

    addBefore(E e,Entryentry)方法是个私有方法,所以无法在外部程序中调用(当然,这是一般情况,你可以通过反射上面的还是能调用到的)。

    addBefore(E e,Entryentry)先通过Entry的构造方法创建e的节点newEntry(包含了将其下一个节点设置为entry,上一个节点设置为entry.previous的操作,相当于修改newEntry的“指针”),之后修改插入位置后newEntry的前一节点的next引用和后一节点的previous引用,使链表节点间的引用关系保持正确。之后修改和size大小和记录modCount,然后返回新插入的节点。
    则有,addBefore(E e,Entry entry)实现在entry之前插入由e构造的新节点。而add(E e)实现在header节点之前插入由e构造的新节点。

    add(int index, E element)

    public void add(int index, E element) {
         addBefore(element, (index==size ? header : entry(index)));
     }

    也是调用了addBefore(E e,Entry entry)方法,只是entry节点由index的值决定。

    addFirst(E e)

    public void addFirst(E e) {
         addBefore(e, header.next);
     }

    结合addBefore(E e,Entry entry)方法,很容易理解addFirst(E e)只需实现在header元素的下一个元素之前插入。addLast(E e)只需在实现在header节点前(因为是循环链表,所以header的前一个节点就是链表的最后一个节点)插入节点。

    (3) 元素读取

    set(int index,E element)

    public E set(int index, E element) {
        Entry<E> e = entry(index);
        E oldVal = e.element;
        e.element = element;
        return oldVal;
    }
    由上面的代码可以得到,先获取指定索引的节点,之后保留原来的元素,然后用element进行替换,之后返回原来的元素。

    get(int Index)

    public E get(int index) {
         return entry(index).element;
     }

    get(int index)方法用于获得指定索引位置的节点的元素。它通过entry(int index)方法获取节点。entry(int index)方法遍历链表并获取节点,entry的方法也是根据索引值,一步步开始遍历的。

    getFirst()

     public E getFirst() {
        if (size==0)
             throw new NoSuchElementException();
         return header.next.element;
     }
    element()
    public E element() {
     return getFirst();
     }

    element()方法调用了getFirst()返回链表的第一个节点的元素。从代码上看,两者并没有什么不同,像是包装了一下名字,其实这只是为了在不同的上下文“语境”中能通过更贴切的方法名调用罢了。

    getLast()

    public E getLast()  {
        if (size==0)
            throw new NoSuchElementException();
        return header.previous.element;
     }

    getLast()方法和getFirst()方法类似,只是获取的是header节点的前一个节点的元素。因为是循环链表,所以header节点的前一节点就是链表的最后一个节点。

    (4) 元素删除

    remove()

    public E remove() {
        return removeFirst();
    }

    remove(int Index)

    public E remove(int index) {
        return remove(entry(index));
    }

    remove(Object object)

    public boolean remove(Object o) {
        if (o==null) {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Entry<E> e = header.next; e != header; e = e.next) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }

    removeFirst()

    public E removeFirst() {
         return remove(header.next);
    }

    removeLast()

    public E removeLast() {
       return remove(header.previous);
    }

    从上面代码中,可以看到几个remove方法最终都是调用了私有方法:remove(Entry e),其中的简单逻辑稍有区别。下面分析remove(Entry e)方法。

    private E remove(Entry<E> e) {
        if (e == header)
            throw new NoSuchElementException();
        // 保留将被移除的节点e的内容
        E result = e.element;
        // 将前一节点的next引用赋值为e的下一节点
        e.previous.next = e.next;
        // 将e的下一节点的previous赋值为e的上一节点
        e.next.previous = e.previous;
        // 上面两条语句的执行已经导致了无法在链表中访问到e节点,而下面解除了e节点对前后    节点的引用
        e.next = e.previous = null;
        // 将被移除的节点的内容设为null
        e.element = null;
        // 修改size大小
        size--;
        modCount++;
        // 返回移除节点e的内容
        return result;
    }

    有一个clear()类,清空双向列表

    public void clear()  {
           Entry<E> e = header.next;
            // 从表头开始,逐个向后遍历;对遍历到的节点执行一下操作:
           // 设置前一个节点为null 
           //  设置当前节点的内容为null 
           //  设置后一个节点为“新的当前节点”
             while (e != header) {
                 Entry<E> next = e.next;
                e.next = e.previous = null;
                 e.element = null;
                e = next;
            }
            header.next = header.previous = header;
            // 设置大小为0
             size = 0;
            modCount++;
         }

    (5) 元素查找

    indexOf(Object o)

    从前向后查找,返回“值为对象(o)的节点对应的索引”,不存在就返回-1

    public int indexOf(Object o) {
            int index = 0;
            if (o==null) {
                for (Entry e = header.next; e != header; e = e.next) {
                    if (e.element==null)
                        return index;
                    index++;
                 }
           } else {
                for (Entry e = header.next; e != header; e = e.next) {
                     if (o.equals(e.element))
                         return index;
                     index++;
                 }
             }
             return -1;
         }

    lastIndexOf(Object o)

    从后向前查找,返回值“为对象(o)的节点对应的索引”, 不存在就返回-1
    查找的是last index,即最后一次出现的位置,所以采用由后向前的遍历方式。因为采用了由后向前的遍历,所以index被赋值为size,并且循环体内执行时都进行减操作。分两种情况判断是否存在,分别是null和不为空。

    public int lastIndexOf(Object o) {
        int index = size;
        if (o==null) {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (e.element==null)
                    return index;
            }
        } else {
            for (Entry e = header.previous; e != header; e = e.previous) {
                index--;
                if (o.equals(e.element))
                    return index;
            }
        }
        return -1;
    }

    (6) 元素包含

    判断LinkedList是否包含元素(o)

    public boolean contains(Object o) {
            return indexOf(o) != -1;
      }
    }
    

    (7) 返回静态数组toArray

    // 返回LinkedList的Object[]数组
         public Object[] toArray() {
        // 新建Object[]数组
         Object[] result = new Object[size];
            int i = 0;
            // 将链表中所有节点的数据都添加到Object[]数组中
            for (Entry<E> e = header.next; e != header; e = e.next)
                result[i++] = e.element;
         return result;
        }
    
         // 返回LinkedList的模板数组。所谓模板数组,即可以将T设为任意的数据类型
        public <T> T[] toArray(T[] a) {
             // 若数组a的大小 < LinkedList的元素个数(意味着数组a不能容纳LinkedList中全部元素)
             // 则新建一个T[]数组,T[]的大小为LinkedList大小,并将该T[]赋值给a。
             if (a.length < size)
                a = (T[])java.lang.reflect.Array.newInstance(
                                    a.getClass().getComponentType(), size);
            // 将链表中所有节点的数据都添加到数组a中
             int i = 0;
            Object[] result = a;
             for (Entry<E> e = header.next; e != header; e = e.next)
                 result[i++] = e.element;
    
            if (a.length > size)
                a[size] = null;
    
             return a;
        }

    (8) 其它API

    // 是否存在下一个元素
           public boolean hasNext() {
                // 通过元素索引是否等于“双向链表大小”来判断是否达到最后。
                return nextIndex != size;
            }
            // 获取下一个元素
            public E next() {
                 checkForComodification();
                 if (nextIndex == size)
                     throw new NoSuchElementException();
    
                 lastReturned = next;
                 // next指向链表的下一个元素
                next = next.next;
                nextIndex++;
                 return lastReturned.element;
            }
    
             // 是否存在上一个元素
            public boolean hasPrevious() {
                 // 通过元素索引是否等于0,来判断是否达到开头。
                return nextIndex != 0;
             }
    
             // 获取上一个元素
             public E previous() {
                 if (nextIndex == 0)
                throw new NoSuchElementException();
                // next指向链表的上一个元素
                 lastReturned = next = next.previous;
                 nextIndex--;
                 checkForComodification();
                 return lastReturned.element;
             }
    
        // 双向链表的节点所对应的数据结构。
         // 包含3部分:上一节点,下一节点,当前节点值。
         private static class Entry<E> {
             // 当前节点所包含的值
             E element;
            // 下一个节点
             Entry<E> next;
             // 上一个节点
             Entry<E> previous;
    
             /**
              * 链表节点的构造函数。
              * 参数说明:
              *   element  —— 节点所包含的数据
              *   next      —— 下一个节点
              *   previous —— 上一个节点
              */
             Entry(E element, Entry<E> next, Entry<E> previous) {
                 this.element = element;
                 this.next = next;
                 this.previous = previous;
             }
         }

    4. LinkedList的遍历方式

        (1) 第一种 通过迭代器遍历。即通过Iterator去遍历

    for(Iterator iter = list.iterator(); iter.hasNext();)
        iter.next();
    
    

       (2) 通过快速随机访问遍历LinkedList

    int size = list.size();
    for (int i=0; i<size; i++) {
        list.get(i);        
    }

        (3) 使用增强for

    for (Integer integ:list) {
        System.out.println(integ);  
    }

    遍历的方式有很多种,这就就暂时列举几个

    补充:

    此实现不是同步的,当多个线程同时访问一个LinkedList列表时,而其中至少一个想变成修改了此列表,则他必须保持同步。如果在多线的情况下,可以使用collections.synchronizedList()方法来 “包装”列表,比如:

    List list = Collections.synchronizedList(new LinkedList(...));



    展开全文
  • java常用集合

    2017-08-23 17:13:56
    java常用集合java语言中常用的集合类List、Set、Map三种,三种数据类型都实现了collection接口,三种集合类的使用各不同,本文做一下简单的说明List(列表)List允许元素重复、放入顺序 List集合类三种:...

    java常用集合类

    java语言中常用的集合类有List、Set、Map三种,三种数据类型都实现了collection接口,三种集合类的使用各有不同,本文做一下简单的说明

    List(列表)

    List允许元素重复、有放入顺序
    List集合类有三种:LinkedList、ArrayList、Vector

    1. LinkedList
      LikedList是基于链表实现的一种列表类,允许元素重复,有放入顺序,增删较为快捷,查找需要遍历全部元素,时间复杂度为O(n)。
    2. ArrayList
      ArrayList也就是动态数组,以数组实现的列表类,允许元素重复,有放入顺序。
    3. Vector
      Vector跟ArrayList的实现原理一致。两者最大的区别在于线程安全的问题,ArrayList是非线程安全的,不包含访问加锁机制,效率较高;Vector是线程安全的,同一时间只允许一个线程访问,效率较低。

    Set(集)

    Set不允许元素重复、无放入顺序,但是位置由Hashcode决定
    Set主要有两种形式的实现:HashSet、TreeSet

    1. HashSet
      HashSet是无序的集合,可以保存null

    2. TreeSet
      TreeSet是无序集合,但是有排序的功能,不可以保存null

    Map(映射)

    Map无放入顺序,按键值对存储,关键字不允许重复
    Map主要实现有HashMap、TreeMap

    1. HashMap
      可以存储null
    2. TreeMap
      不可以存储null,可以根据关键字排序
    展开全文
  • java 有哪些常用容器(集合)?

    万次阅读 多人点赞 2019-04-29 10:52:47
    java 有哪些常用容器(集合)? java 容器都有哪些? Collection | ├AbstractCollection 对Collection接口的最小化抽象实现 | │ | ├List 有序集合 | │-├AbstractList 有序集合的最小化抽象实现 | │...

    java 有哪些常用容器(集合)?

    java 容器都有哪些?

    Collection

    |  ├AbstractCollection  对Collection接口的最小化抽象实现

    |  │ 

    |  ├List  有序集合

    |  │-├AbstractList  有序集合的最小化抽象实现 

    |  │-├ArrayList  基于数组实现的有序集合

    |  │-├LinkedList  基于链表实现的有序集合

    |  │-└Vector  矢量队列

    |  │ └Stack  栈,先进后出

    |  │

    |  ├Set  不重复集合

    |  │├AbstractSet  不重复集合的最小化抽象实现

    |  │├HashSet  基于hash实现的不重复集合,无序

    |  │├LinkedHashSet  基于hash实现的不重复集合,有序

    |  │└SortedSet  可排序不重复集合

    |  │   └NavigableSet  可导航搜索的不重复集合

    |  │     └TreeSet  基于红黑树实现的可排序不重复集合

    |  │

    |  ├Queue  队列

    |  │├AbstractQueue  队列的核心实现

    |  │├BlockingQueue  阻塞队列

    |  │└Deque  可两端操作线性集合

     

    Map  键值映射集合

    |  ├AbstractMap  键值映射集合最小化抽象实现

    |  ├Hashtable  基于哈希表实现的键值映射集合,key、value均不可为null

    |  ├HashMap  类似Hashtable,但方法不同步,key、value可为null

    |     └LinkedHashMap  根据插入顺序实现的键值映射集合

    |  ├IdentityHashMap  基于哈希表实现的键值映射集合,两个key引用相等==,认为是同一个key

    |  ├SortedMap   可排序键值映射集合

    |     └NavigableMap  可导航搜索的键值映射集合

    |    └WeakHashMap  弱引用建,不阻塞被垃圾回收器回收,key回收后自动移除键值对

     

    可以比较的点:

    • 有序、无序
    • 可重复、不可重复
    • 键、值是否可为null
    • 底层实现的数据结构(数组、链表、哈希...)
    • 线程安全性

     


    【Java面试题与答案】整理推荐

     

    展开全文
  • Java常用集合框架图

    2018-01-09 21:59:34
    Java常用集合框架图

    Java常用集合框架图

    Java常用集合框架图

    展开全文
  • java常用集合及集合框架总结

    千次阅读 2018-06-04 23:33:27
    今天这篇文章我们重点总结一下java中常用集合,及他们的特性和适用的场合。常见集合框架结构如下图(不是全部,只包含常用的) 1、List 1.1、ArrayList1.2、LinkedList1.3、Vector1.4、List接口下各种接口实现...
  • 工作中常用Java集合有哪些

    千次阅读 多人点赞 2020-03-26 13:46:40
    初学者最疑惑的应该是学了这项技术,在工作是怎么使用的。
  • Java中常用集合&线程安全的集合

    千次阅读 2020-09-25 17:42:28
    Java中常用集合 (图中忽略中间接口) Collection接口族下的对象都是存的单一值的元素,而Map接口族下存的是key-value结构的数据。其中Set集合需借助Map对象来实现。 线程安全的List ArrayList和LinkedList都不是线程...
  • Java常用集合类总结

    千次阅读 2018-01-20 12:43:31
    Java常用集合类总结 作者:麦田里的码农 目录: Java常用集合类总结 集合类Collection的由来 集合和数组的区别 如何着手学习集合类 Collection 接口 1 测试一Collection基本功能 2 测试二Collection遍历 ...
  • java并发集合有哪些

    千次阅读 2017-11-13 10:39:45
    java API提供了包含接口、类和算法的java集合框架,它实现了可用在程序的大量数据结构。  当需要在并发程序使用数据集合时,必须要谨慎地选择相应的实现方式。大多数集合类并不能直接用于并发应用,因为他们...
  • 集合框架,java中常用集合类和接口,帮助大家快速掌握java的常用接口和类
  • Java集合有哪些

    千次阅读 2020-07-04 09:47:14
    Java集合有哪些java集合分三种,List、Set、Map,这三种集合适用于不同的场景 List:适用于有序,可重复的集合 Set:适用于不可重复集合 Map:适用于键值对的存储 注:通常List与Map最为常用 每个集合常用的...
  • Java常用集合总结笔记

    千次阅读 2017-07-14 08:52:04
    常用集合Collection、Map以及其子类集合的学习总结
  • Java常见集合有哪些

    千次阅读 2018-10-25 23:17:14
    说说常见的集合有哪些吧? 答: Map接口和Collection接口是所有集合框架的父接口 Collection接口的子接口包括:Set接口和List接口。Set不能包含重复的元素。List是一个有序的集合,可以包含重复的元素,提供了按...
  • 集合的结构如下图所示: ...Collection下两个比较常用的接口分别是List(列表)和Set(集),其中List可以存储重复元素,元素是有序的(存取顺序一致),可以通过List脚标来获取指定元素;而S
  • Java常用集合实现原理

    千次阅读 2019-02-18 15:55:51
    1. JDK常用集合类型 列表:List 栈:Stack,链表的扩展 队列:Queue 集合:Set 2. List 列表,List接口,常用实现原理及特点 ArrayList:命名已经很明显体现了其特点,Array:数组,其底层实现原理就是数组,达到...
  • Java常用集合体系以及相互区别 集合体系各个集合特点:Collection,list,set ,map
  • 秒懂Java中常用集合
  • Java中常用集合效率比较

    千次阅读 2019-01-11 12:00:00
    HashSet,常用的set实现类, LinkedHashSet,具有 HashSet 的查询速度,且内部使用链表维护元素的顺序 ( 插入的次序 ) 。于是在使用迭代器遍历 Set 时,结果会按元素插入的次序显示。 TreeSet,保存次序的 Set, ...
  • Java常用集合类详解

    千次阅读 2013-06-27 16:13:30
    Java中有一套设计优良的接口和类组成了Java集合框架,使程序员操作成批的数据或对象元素极为方便。所有的Java集合都在java.util包中。  在编写程序的过程中,使用到集合类,要根据不同的需求,来决定使用哪种...
  • Java中常用的List集合的排序方法 List< Map >是Java中常用集合,难免会遇到需要给它进行排序的时候,下面介绍我经常使用的排序方法。 整型排序: 1、定义一个整型数组(一般都是用sql查的数据,这里道理相同...
  • Java集合容器面试题(2020最新版)

    万次阅读 多人点赞 2020-03-01 11:08:34
    文章目录集合容器概述什么是集合集合的特点集合和数组的区别使用集合框架的好处常用集合有哪些?List,Set,Map三者的区别?List、Set、Map 是否继承自 Collection 接口?List、Map、Set 三个接口存取元素时,各...
  • Java中常用集合类 对于集合,大家都不陌生了,常见的集合接口Set、List、Map等,其中Set和List继承自Collection。 Collection是一组对象的集合,而Map存储的方式不一样,他是以键值对的形式存放多个对象的。 ...
  • java中常用集合区别

    千次阅读 2018-08-31 15:15:36
    Java平台包括集合框架。 集合框架是用于表示和操作集合的统一体系结构,使集合可以独立于实现细节进行操作。集合框架主要具有以下优势: 1、通过提供数据结构和算法减少编程工作 2、提供高性能实现的数据结构和...
  • java 常用集合类总结

    千次阅读 2017-05-06 14:24:01
    在平常的代码开发中,集合类是经常会使用到的,比如用于列表缓存的... java中集合,不管是List,Set,还是Map,都是继承自collection接口,这个接口主要定义了集合类的一些公关方法,比如isEmpty(), remove(),
  • Java 中常用集合的三大接口 一、Java.util.Set Set接口是Collection接口的子接口,它是没有重复元素的元素集合,也不能在其中加入相同的元素,而且各元素在该集合中不按特定的方式排序,总的说来就是一个无序无...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 317,490
精华内容 126,996
关键字:

java常用的集合有哪些

java 订阅