文章目录集合体系Collection集合系统Map集合体系准备工作Collection接口List接口MyArrayList基本属性及初始化方法重写实现void add(T element)void add(int index,T element)boolean remove(T t)T remove(int index)T get(int index)T set(int index, T element)boolean contains(T t)boolean isEmpty()int size()void clear()Object[] toArray()void autoExpend(int newCapacity)MyLinkedList基本属性及初始化方法重写实现void addFirst(T t)void addLast(T t)void insertAfter(NodeT node,T t)T removeFirst()T removeLast()T remove(T t)T getFirst()T getLast()contains(T t)boolean isEmpty()int size()Object[] toArray()总结集合体系Collection集合系统Map集合体系准备工作根据体系和要实现的功能搭建文件结构Collection接口List接口(提供了很多与索引相关的方法)MyArrayList基于数组实现基本属性及初始化private Object[] arr; int capacity; int size; { capacity10; arrnew Object[10]; size0; }Object实现泛型因为T不能new T()创建对象方法重写实现void add(T element)Override public void add(T element) { if(sizecapacity){ autoExpend(capacity*2); } arr[size]element; size; }简单的有序添加void add(int index,T element)Override public void add(int index, T element) { if(index0||indexsize){ throw new IndexOutOfBoundsException(Index:index,Size:size); } if(sizecapacity){ autoExpend(capacity*2); } for(int isize;iindex;i--){ arr[i]arr[i-1]; } arr[index]element; size; }以索引添加的元素必须在(0,size)范围内如果不在就抛出OutBounds异常(实现了按顺序向后添加插入只能在索引对应位置有元素时实现)当元素个数达到最大容量时时触发自动扩容当索引位置有元素时for循环向后移实现插入。当索引位置处没元素时此时sizeindex不会进入循环boolean remove(T t)Override public boolean remove(T t) { for(int i0;isize;i){ if((t null arr[i] null) || (t ! null t.equals(arr[i]))){ remove(i); return true; } } return false; }注意这里的判断是否相等(t null arr[i] null) || (t ! null t.equals(arr[i]))T remove(int index)Override public T remove(int index) { if(index0||indexsize){ throw new IndexOutOfBoundsException(); } Object temparr[index]; for(int iindex;isize-1;i){ arr[i]arr[i1]; } arr[size - 1] null; size--; return (T)temp; }remove后别忘了把最后一个元素赋值为nullT get(int index)Override public T get(int index) { if(index0||indexsize){ throw new IndexOutOfBoundsException(); } return (T) arr[index]; }T set(int index, T element)Override public T set(int index, T element) { if(index0||indexsize){ throw new IndexOutOfBoundsException(); } Object temparr[index]; arr[index]element; return (T) temp; }以索引添加的元素必须在(0,size)范围内(T)来进行转换为特定数据类型boolean contains(T t)Override public boolean contains(T t) { for(int i0;isize;i){ if((t null arr[i] null) || (t ! null t.equals(arr[i]))){ return true; } } return false; }注意这里的判断是否相等boolean isEmpty()Override public boolean isEmpty() { return size0; }int size()Override public int size() { return size; }void clear()Override public void clear() { capacity 10; arr new Object[capacity]; size 0; }arr需要重新设置大小否则会出现capacity和数组大小不一致的情况Object[] toArray()Override public Object[] toArray() { Object[] resultnew Object[size]; for(int i0;isize;i){ result[i]arr[i]; } return result; }for循环条件为isize,复制实际内容void autoExpend(int newCapacity)private void autoExpend(int newCapacity){ Object[] newArrnew Object[newCapacity]; for(int i0;icapacity;i){ newArr[i]arr[i]; } capacitynewCapacity; arrnewArr; }同时更新容量和数组MyLinkedList基于双向链表实现基本属性及初始化静态内部类节点类(属于链表)前一个节点——值——后一个节点方法重写实现void addFirst(T t)public void addFirst(T t){ NodeT ffirst; NodeT newNodenew Node(null,t,f); firstnewNode; if(fnull) lastnewNode; else f.prevnewNode; size; }头插法新节点的prev为nullvoid addLast(T t)public void addLast(T t){ NodeT llast; NodeT newNodenew Node(l,t,null); lastnewNode; if(lnull) firstnewNode; else l.nextnewNode; size; }尾插法新节点的next为nullvoid insertAfter(Node node,T t)public void insertAfter(NodeT node,T t){ NodeT nextNodenode.next; NodeT newNodenew Node(node,t,nextNode); node.nextnewNode; if(nextNode!null){ nextNode.prevnewNode; } if(nodelast){ lastnewNode; } size; }正确更新首尾节点指针T removeFirst()public T removeFirst(){ NodeT ffirst; if (f null) { throw new NoSuchElementException(); } firstf.next; T valuef.item; if(firstnull){ lastnull;//空链表 } else{ f.next.prevnull; } f.itemnull; f.prevnull; size--; return value; }判断链表为空的情况正确更新首尾节点T removeLast()public T removeLast(){Node llast;if (l null) {throw new NoSuchElementException();}lastl.prev;T valuel.item;if(lastnull){ firstnull;//链表为空 } else{ l.prev.nextnull; } l.itemnull; l.nextnull; size--; return value; }T remove(T t)public T remove(T t){ NodeT currentfirst; while(current!null){ if((current.itemnulltnull)||(current.item!nullcurrent.item.equals(t))){ NodeT prevcurrent.prev; NodeT nextcurrent.next; //删除的是头节点 if(prevnull){ firstnext; }else{ prev.nextnext; current.prevnull; } //删除的是尾节点 if(nextnull){ lastprev; }else{ next.prevprev; current.nextnull; } current.itemnull; size--; return t; } currentcurrent.next; } return null; }正确更新首尾节点T getFirst()public T getFirst(){ NodeT ffirst; if(firstnull) throw new NoSuchElementException(); return f.item; }T getLast()public T getLast(){Node llast;if(lnull){throw new NoSuchElementException();}return l.item;}contains(T t)Override public boolean contains(T t) { NodeT currentfirst; while(current!null){ if((current.itemnulltnull)||(current.item!nullcurrent.item.equals(t))){ return true; } currentcurrent.next; } return false; }链表的遍历boolean isEmpty()Override public boolean isEmpty() { return size0; }int size()Override public int size() { return size; }Object[] toArray()Override public Object[] toArray() { NodeT currentfirst; Object[] arrnew Object[size]; int i0; while(current!null){ arr[i]current.item; i; currentcurrent.next; } return arr; }总结MyArrayList查找快增删慢用Object代替泛型(可以创建对象)跟索引有关的方法是有限制的,(0,size)之间进行插入/删除时元素平移需要考虑并发异常判断是否相等方法需要考虑多种情况自动扩容的实现MyLinkedList增删快查找慢注意构建节点内部类(prev,item,next)注意更新首尾指针的指向注意考虑头插法新节点的prev是null尾插法新节点的next是null 链 表遍历的实现