目录

基本概念

API 接口

ArrayList&LinkedList

主要方法

实现ArrayList&LinkedList

基本概念

• Collection表示一组对象，它是集中，收集的意思，就是把一些数据收集起来
• Collection函数库是在 java.util包下的一些接口和类，类是用来产生对象存放数据用的，而接口是访问数据的方式
• Collection函数库与数组的两点不同：
  • 1.数组的容量是有限制的，而 Collection库没有这样的限制，它容量可以自动的调节
  • 2.Collection函数库只能用来存放对象，而数组没有这样的限制
• Collection接口是 Collection层次结构中的根接口，它定义了一些最基本的访问方法，让我们能用统一的方式通过它或它的子接口来访问数据
• 区别：Collection代表一组对象， Collection函数库就是java的集合框架， Collection接口，是这个集合框架中的根接口
• 存放在 Collection库中的数据，被称为元素（ element）

API 接口

• Collection接口：定义了存取一组对象的方法，其子接口Set和List分别定义了存储方式。
  • List:列表，有序可重复
  • Set:集合，无序不可重复
• Map:字典，定义了存储“键—值映射对”的方法

ArrayList&LinkedList

ArrayList（数组列表）、LinkedList（链表）是list的子类

主要方法

• 在末尾添加一个元素：void add(E e)
• 在指定索引添加一个元素：void add(int index, E e)
• 更改指定索引的一个元素：void set(int index, E e)
• 删除指定索引的元素：int remove(int index)
• 删除某个元素：int remove(Object e)
• 获取指定索引的元素：E get(int index)
• 获取链表大小（包含元素的个数）：int size()

LinkedList的内部每个元素都指向下一个元素

通常情况下优先使用ArrayList

实现ArrayList&LinkedList

/*** 实现ArrayList，理解ArrayList的底层结构* @author qiao39gs**/
public class MyArrayList {private Object[] elementData;	//初始化元素对象private int size;public int size(){return size;}public boolean isEmpty(){return size==0;}public MyArrayList(){this(10);}public MyArrayList(int initialCapacity){elementData = new Object[initialCapacity];}public void add(Object obj){ensureCapacity();elementData[size++] = obj;}public void add(int index,Object obj){rangeCheck(index);ensureCapacity();	System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = obj;size++;}public Object get(int index){rangeCheck(index);return elementData[index];}public void remove(int index){//删除指定位置的对象rangeCheck(index);int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; }public void remove(Object obj){//删掉指定对象for(int i=0;i<size;i++){if(get(i).equals(obj)){remove(i);}}}public Object set(int index,Object obj){rangeCheck(index);Object oldValue = elementData[index];elementData[index] = obj;return oldValue;}private void rangeCheck(int index){if(index<0||index>=size){try {throw new Exception();} catch (Exception e) {e.printStackTrace();}}}private void ensureCapacity(){	//数组扩容和数据的拷贝if(size==elementData.length){Object[] newArray = new Object[size*2+1];//System.arraycopy(elementData, 0, newArray, 0, elementData.length);for(int i=0;i<elementData.length;i++){newArray[i] = elementData[i];}elementData = newArray;}}public static void main(String[] args) {MyArrayList list = new MyArrayList(2);list.add("aaa");list.add(1234);		list.add("bbb");list.add(23);		list.add("ppp");System.out.println("list.size():"+list.size());list.add(2,"ccc");System.out.println("list.get(2):"+list.get(2));list.remove(0);for(int i=0;i<list.size();i++){System.out.print(list.get(i)+"  ");}System.out.println("\nlist.get(0):"+list.get(0));list.remove("ccc");for(int i=0;i<list.size();i++){System.out.print(list.get(i)+"  ");}list.set(1,"14");System.out.print("\n");for(int i=0;i<list.size();i++){System.out.print(list.get(i)+"  ");}}
}

部分实现LinkedList 

public class MyLinkedList {private Node first;private Node last;private int size;public void add(Object obj){if(first==null){Node n = new Node();n.setPrevious(null);n.setObj(obj);n.setNext(null);first = n;last = n;}else{//直接往last节点后增加新的节点Node n = new Node();n.setPrevious(last);n.setObj(obj);last.setNext(n);last = n;}size++;}public void add(int index,Object obj){Node temp = node(index);Node newNode = new Node();newNode.obj = obj;if(temp!=null){Node up = temp.previous;up.next = newNode;newNode.previous = up;newNode.next = temp;temp.previous = newNode;size++;}}public int size(){return size;}public Object get(int index){rangeCheck(index);Node temp = node(index);if(temp!=null){return temp.obj;}return temp.obj;}public void remove(int index){Node temp = node(index);if(temp!=null){Node up = temp.previous;Node down = temp.next;up.next = down;down.previous = up;temp = null;size--;}}public Node node(int index){Node temp = null;	//当前位置if(first!=null){temp = first;for(int i=0;i<index;i++){temp = temp.next;}}return temp;}private void rangeCheck(int index){if(index<0||index>=size){try {throw new Exception();} catch (Exception e) {e.printStackTrace();}}}public static void main(String[] args) {MyLinkedList list = new MyLinkedList();list.add("aaa");list.add("bbb");list.add("ccc");list.remove(1);list.add(1,"EEE");System.out.println(list.size());System.out.println(list.get(0));System.out.println(list.get(1));System.out.println(list.get(2));}
}