企业官网建设流程全解析

集合体系

Collection集合系统

Map集合体系

准备工作

根据体系和要实现的功能搭建文件结构

Collection接口

List接口

(提供了很多与索引相关的方法)

MyArrayList

基于数组实现

基本属性及初始化

private Object[] arr; int capacity; int size; { capacity=10; arr=new Object[10]; size=0; }

• Object实现泛型，因为T不能new T()创建对象

方法重写实现

void add(T element)

@Override public void add(T element) { if(size==capacity){ autoExpend(capacity*2); } arr[size]=element; size++; }

简单的有序添加

void add(int index,T element)

@Override public void add(int index, T element) { if(index<0||index>size){ throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size); } if(size==capacity){ autoExpend(capacity*2); } for(int i=size;i>index;i--){ arr[i]=arr[i-1]; } arr[index]=element; size++; }

• 以索引添加的元素必须在(0,size)范围内，如果不在就抛出OutBounds异常(实现了按顺序向后添加，插入只能在索引对应位置有元素时实现)
• 当元素个数达到最大容量时时，触发自动扩容
• 当索引位置有元素时，for循环向后移实现插入。当索引
• 位置处没元素时，此时size==index，不会进入循环

boolean remove(T t)

@Override public boolean remove(T t) { for(int i=0;i<size;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(index<0||index>=size){ throw new IndexOutOfBoundsException(); } Object temp=arr[index]; for(int i=index;i<size-1;i++){ arr[i]=arr[i+1]; } arr[size - 1] = null; size--; return (T)temp; }

• remove后别忘了把最后一个元素赋值为null

T get(int index)

@Override public T get(int index) { if(index<0||index>=size){ throw new IndexOutOfBoundsException(); } return (T) arr[index]; }

T set(int index, T element)

@Override public T set(int index, T element) { if(index<0||index>=size){ throw new IndexOutOfBoundsException(); } Object temp=arr[index]; arr[index]=element; return (T) temp; }

• 以索引添加的元素必须在(0,size)范围内
• (T)来进行转换为特定数据类型

boolean contains(T t)

@Override public boolean contains(T t) { for(int i=0;i<size;i++){ if((t == null && arr[i] == null) || (t != null && t.equals(arr[i]))){ return true; } } return false; }

注意这里的判断是否相等

boolean isEmpty()

@Override public boolean isEmpty() { return size<=0; }

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[] result=new Object[size]; for(int i=0;i<size;i++){ result[i]=arr[i]; } return result; }

• for循环条件为i<size,复制实际内容

void autoExpend(int newCapacity)

private void autoExpend(int newCapacity){ Object[] newArr=new Object[newCapacity]; for(int i=0;i<capacity;i++){ newArr[i]=arr[i]; } capacity=newCapacity; arr=newArr; }

• 同时更新容量和数组

MyLinkedList

基于双向链表实现

基本属性及初始化

• 静态内部类节点类(属于链表)
• 前一个节点——值——后一个节点

方法重写实现

void addFirst(T t)

public void addFirst(T t){ Node<T> f=first; Node<T> newNode=new Node<>(null,t,f); first=newNode; if(f==null) last=newNode; else f.prev=newNode; size++; }

• 头插法新节点的prev为null

void addLast(T t)

public void addLast(T t){ Node<T> l=last; Node<T> newNode=new Node(l,t,null); last=newNode; if(l==null) first=newNode; else l.next=newNode; size++; }

• 尾插法新节点的next为null

void insertAfter(Node node,T t)

public void insertAfter(Node<T> node,T t){ Node<T> nextNode=node.next; Node<T> newNode=new Node<>(node,t,nextNode); node.next=newNode; if(nextNode!=null){ nextNode.prev=newNode; } if(node==last){ last=newNode; } size++; }

• 正确更新首尾节点指针

T removeFirst()

public T removeFirst(){ Node<T> f=first; if (f == null) { throw new NoSuchElementException(); } first=f.next; T value=f.item; if(first==null){ last=null;//空链表 } else{ f.next.prev=null; } f.item=null; f.prev=null; size--; return value; }

• 判断链表为空的情况
• 正确更新首尾节点

T removeLast()

public T removeLast(){
Node l=last;
if (l == null) {
throw new NoSuchElementException();
}
last=l.prev;
T value=l.item;

if(last==null){ first=null;//链表为空 } else{ l.prev.next=null; } l.item=null; l.next=null; size--; return value; }

T remove(T t)

public T remove(T t){ Node<T> current=first; while(current!=null){ if((current.item==null&&t==null)||(current.item!=null&&current.item.equals(t))){ Node<T> prev=current.prev; Node<T> next=current.next; //删除的是头节点 if(prev==null){ first=next; }else{ prev.next=next; current.prev=null; } //删除的是尾节点 if(next==null){ last=prev; }else{ next.prev=prev; current.next=null; } current.item=null; size--; return t; } current=current.next; } return null; }

• 正确更新首尾节点

T getFirst()

public T getFirst(){ Node<T> f=first; if(first==null) throw new NoSuchElementException(); return f.item; }

T getLast()

public T getLast(){
Node l=last;
if(l==null){
throw new NoSuchElementException();
}
return l.item;
}

contains(T t)

@Override public boolean contains(T t) { Node<T> current=first; while(current!=null){ if((current.item==null&&t==null)||(current.item!=null&&current.item.equals(t))){ return true; } current=current.next; } return false; }

• 链表的遍历

boolean isEmpty()

@Override public boolean isEmpty() { return size==0; }

int size()

@Override public int size() { return size; }

Object[] toArray()

@Override public Object[] toArray() { Node<T> current=first; Object[] arr=new Object[size]; int i=0; while(current!=null){ arr[i]=current.item; i++; current=current.next; } return arr; }

总结

MyArrayList：

• 查找快，增删慢
• 用Object代替泛型(可以创建对象)
• 跟索引有关的方法是有限制的,(0,size)之间
• 进行插入/删除时，元素平移需要考虑并发异常
• 判断是否相等方法需要考虑多种情况
• 自动扩容的实现

MyLinkedList：

• 增删快，查找慢
• 注意构建节点内部类(prev,item,next)
• 注意更新首尾指针的指向
• 注意考虑头插法新节点的prev是null，尾插法新节点的next是null 链 表遍历的实现