集合（容器）和泛型

集合上下实现图

存储在java.util包，理解集合需要在基础是理解泛型，因为调用的全是形参的集合。
集合（容器）和泛型

泛型

泛型是JDK1.5以后增加的，可以建立类型安全的集合。本质是“”数据类型的参数化“，可以理解为数据类型的占位符，类似形参，就是告诉编译器，调用的时候需要传入实际类型。

   import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TestGeneric {
    public static void main(String[] args) {
        MyCollection<String> myCollection=new MyCollection<>();
        myCollection.set("lsd",1);
        myCollection.set("999",2);
        String a= myCollection.get(2);
        //强制转型
        String s=myCollection.get(1);
        System.out.println(a);
        System.out.println(s);

        //底层也是泛型
        List list=new ArrayList();
        Map map=new HashMap<>();

    }
}
//泛型为后面定义的类型
class MyCollection<E>{
    Object[] objects=new Object[5];
    public void set(E obj,int index){
        objects[index]=obj;
    }
    public E get(int index){
        return (E)objects[index];
    }
}

Collection 是下属LIst和set父接口，所有的集合基本都实现了Collection的方法，可以直接调用。
• Collection 接口存储一组不唯一，无序的对象
• List 接口存储一组不唯一，有序（索引顺序）的对象
• Set 接口存储一组唯一，无序的对象
• Map接口存储一组键值对象，提供key到value的映射
• Key 唯一无序
• value 不唯一无序

import java.util.ArrayList;
import java.util.Collection;

public class TestList {
    public static void main(String[] args) {
        Collection<String> c=new ArrayList<String>();
        System.out.println(c.isEmpty());
        ((ArrayList<String>) c).add("高老大");
        ((ArrayList<String>) c).add("高老二");
        System.out.println(c);
        System.out.println(c.size());

        System.out.println(c.contains("高老二"));
        System.out.println(((ArrayList<String>) c).indexOf("高老二"));
        System.out.println(c.contains("高老三"));
        Object[] objs=c.toArray();
        System.out.println(objs.toString());

        c.remove("高老二");
        System.out.println(c);
    }
}

常用方法：

import java.util.ArrayList;
import java.util.List;

public class TestList1 {
    public static void main(String[] args) {
        test02();
    }
    public static void test02(){
        List<String> list1=new ArrayList<>();
        list1.add("aa");
        list1.add("bb");
        list1.add("cc");
        List<String> list2=new ArrayList<>();
        list2.add("aa");
        list2.add("bb");
        list2.add("eee");
        System.out.println("list1:"+list1);
        System.out.println("list2:"+list2);
        //添加全部列表
        list1.addAll(list2);
        System.out.println("list1:"+list1);
        //删除全部数据
        list1.removeAll(list2);
        System.out.println("list1:"+list1);
        //取交集
        list1.retainAll(list2);
        System.out.println("list1:"+list1);
        //是否包含
        System.out.println(list1.contains(list2));
    }
}

List :有序可重复的容器。

有序：List每个元素都有index即索引标记，可以根据索引来访问元素，从而精确的控制元素
可重复：允许加入重复的元素。
常用实现类：ArrayLIst,LinkedList和Vector.‘’
ArrayList: 线性表中的顺序表
• 在内存中分配连续的空间，实现了长度可变的数组
• 初始长度为10，初始扩容为5，每次扩容为一般
• 优点：遍历元素和随机访问元素的效率比较高
• 缺点：添加和删除需大量移动元素效率低，按照内容查询效率低
自定义ArrayList:

import java.util.Arrays;

/**
- 手工实现ArrayList
  */
  public class LsdArrayList {
  private Object[] elementData;
  private int size;
  //初始化大小
  private static final int DEFALT_CAPACITY=10;
  
  public LsdArrayList() {
  elementData=new Object[DEFALT_CAPACITY];
  }
  public LsdArrayList(int capacity) {
  if(capacity<0){
  throw new RuntimeException(“容器的容量不能为负数”);
  }else if(capacity0){
  elementData=new Object[DEFALT_CAPACITY];
  }else{
  elementData=new Object[capacity];
  }
  }
  public void add(E element){
  if(sizeelementData.length){
  //扩容操作
  Object[] newArray=new Object[elementData.length+(elementData.length>>1)];
  // newArray=Arrays.copyOf(elementData,0);
  System.arraycopy(elementData,0,newArray,0,elementData.length);
  elementData=newArray;
  }
  elementData[size++]=element;
  }
  
  public E get(int index){
  checkRange(index);
  return (E)elementData[index];
  }
  
  public void set(int index,E e){
  checkRange(index);
  elementData[index]=e;
  }
  
  public void remove(E e){
  //与所有元素进行比较，获得第一个为true的，返回
  for(int i=0;i<size;i++){
  if(e.equals(elementData[i])){
  //容器中所有对的比较操作都是equals犯法
  //将钙元素从此处移除
  remove1(i);
  }
  }
  }
  public void remove1(int index){
  int num=elementData.length-index-1;
  if(num>0){
  System.arraycopy(elementData,index+1,elementData,index,num);
  }
  elementData[–size]=null;
  }
  
  public void checkRange(int index){
  if(index<0 || index>size-1){
  throw new ArrayIndexOutOfBoundsException(“索引越界：”+index);
  }
  }
  
  @Override
  public String toString() {
  StringBuilder sb=new StringBuilder();
  sb.append("[");
  for(int i=0;i<size;i++){
  sb.append(elementData[i]+",");
  }
  sb.setCharAt(sb.length()-1,’]’);
  return sb.toString();
  }
  public int size(){
  return size;
  }
  public boolean isEmpty(){
  return size==0?true:false;
  }
  
  public static void main(String[] args) {
  LsdArrayList s1=new LsdArrayList<>();
  s1.add(“aa”);
  s1.add(“bb”);
  s1.add(“bb”);
  s1.add(“bb”);
  s1.add(“bb”);
  s1.add(“bb”);
  s1.add(“bb”);
  s1.add(“bb”);
  s1.add(“bb”);
  s1.add(“bb”);
  s1.add(“bb”);
  System.out.println(s1);
  System.out.println(s1.get(0));
  s1.set(0,“lsd”);
  System.out.println(s1.get(0));
  s1.remove(“lsd”);
  System.out.println(s1);
  }
  }

LinkedList:底层是链表，查询效率低。增删效率搞
• 采用双向链表存储方式。
• 缺点：遍历和随机访问元素效率低下
• 优点：插入、删除元素效率比较高（但是前提也是必须先低效率查询才可。如果插入删除发生在头尾可以减少查询次数；
集合（容器）和泛型

public class TestLinkedList1<E> {
    private Node first;
    private Node last;
    private int size;

    public void add(E object){
        Node node=new Node(object);
        if(first==null){
            first=node;
            last=node;
        }else{
            node.previous=last;
            node.next=null;
            last.next=node;
            last=node;
        }
        size++;
    }
    public Object get(int index){
        checkRange(index);
        Node temp=getNode(index);
        return temp.element;
    }
    private void checkRange(int index){
        if(index<0 || index>size-1){
            throw new NullPointerException("索引数字不合法");
        }
    }
    public void remove(int index){
        checkRange(index);
        Node temp=getNode(index);
        if(temp!=null){
            Node up=temp.previous;
            Node down=temp.next;
            if(up!=null){
                up.next=down;
            }
            if(down!=null){
                down.previous=up;
            }
            //被删除元素为第一个
            if(index==0){
                first=down;
            }
            //被删除元素为最后一个
            if(index==size-1){
                last=up;
            }
        }
        size--;
    }
    public void add(int index,E obj){
        Node node=new Node(obj);
        Node temp=getNode(index);
        if(temp!=null){
            System.out.println("1111");
            Node up=temp.previous;
            up.next=node;
            node.previous=up;
            node.next=temp;
            temp.previous=node;
        }
        size++;
    }

    private Node getNode(int index){
        checkRange(index);
        Node temp=null;
        if(index<=(size>>1)){
            temp=first;
            for(int i=0;i<index;i++){
                temp=temp.next;
            }
        }else{
            temp=last;
            for(int i=size-1;i>index;i--){
                temp=temp.previous;
            }
        }
        return temp;
    }
    @Override
    public String toString() {
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        Node temp=first;
        while(temp!=null){
            sb.append(temp.element+",");
            temp=temp.next;
        }
        sb.setCharAt(sb.length()-1,']');
        return sb.toString();
    }

    public static void main(String[] args) {
        TestLinkedList1 list=new TestLinkedList1();
        list.add("a");
        list.add("b");
        list.add("c");
        System.out.println(list);
        System.out.println(list.get(2));
        list.remove(2);
        System.out.println(list);
        list.add(1,"ccc");
        System.out.println(list);
        System.out.println(list.size);
    }
}

集合（容器）和泛型

集合上下实现图

泛型

相关推荐