参考书籍《大话数据结构》，实现参考JDK1.8
线性表：
Java实现类有ArrayList，LinkedList
ArrayList：
动态容量数组的列表，扩展类有序数组
int size;//数据大小
Object[] data;//容量数组
默认数组是空数组，容量为0，默认增加容量值是10，DEFAULT_CAPACITY
扩容规则：传入扩容值为minCapacity，若当前数组是空数组，扩容值为max(minCapacity,DEFAULT_CAPACITY)，否则判断minCapacity - size，若大于0默认将当前容量 + 当前容量扩大2倍为newCapacity，newCapacity若小于minCapacity，容量值为minCapacity，否则为newCapacity，然后进行数组拷贝生成新数组。
添加/插入：添加时先检查是否需要扩容，然后给size+1赋值，插入操作是检查插入位置是否在范围，不在范围就抛异常，在范围进行检查是否需要扩容，然后进行数据移动拷贝arraycopy（data,index,data,index+1,size - index），data[size++] = o，底层C实现，时间复杂度O(n)
删除：检查删除位置是否在范围，然后再进行数据移动拷贝(data,index + 1,data,index - 1, size - index - 1)，data[--size] = null
查找/搜索：指定位置查找，O(1)，对象查找indexOf(Object) 顺序查找O(n)，
排序：冒泡排序O(n^2)
优缺点：顺序储存，索引查找快，增删慢
LinkedList（实现了Deque双端队列接口）：
链表：动态容量的双向链式列表，扩展类有单向链表，循环链表，双向链表，静态链表
int size;//数据大小
Node<E> first;//头节点
Node<E> last;//尾节点
class Node<E>{
E item;//数据元素
Node<E> prev;//节点前驱
Node<E> next;//节点后驱
}
默认是空链表，容量为0
扩容规则：无数量限制，添加多少元素增加多少节点，数量为size
添加/插入：
//默认添加是从尾部插入
Node l = last;
Node newNode = (l,o,null);
last = newMode;
if(l== null) first = newNode;
else l.next = newMode;
size++;
//头部插入
Node l = first；
Node newNode = (null,o,l);
first = newMode;
if(l == null) last = newMode;
else l.prev = newMode;size++;
查找/搜索：双向链表通过传入的index/2判断从头部还是尾部遍历搜索，查找到节点E，次数为n/2，O(n)
删除：remove()方法默认删除头部，传入obj进行删除的话，步骤是先查找到节点S，然后进行链接清除
Node prev = s.prev;Node next = s.next;
if(prev != null){prev.next = next;s.prev=null;}else{first=next};
if(next != null){next.prev = prev;s.next=null;}else{last=next};
s.item = null;
size--;
具有Collection的操作方法
add();
remove();
具有队列Queue的操作方法
peek(),element();
offer();
poll();
E remove();
peek()方法取出队列头部元素时候，不删除该元素，而poll()方法取出元素时会删除元素。如果遇到队列为空的情况是，两者都会返回null，element()会抛出异常
双端队列Deque(继承队列接口，具有栈)的操作方法：
所有的操作方法peekFirst,peekLast.....
push()无空间会抛异常
pop()无元素会抛异常
优缺点：不受固定的存储空间限制，快速的插入和删除操作，整块集合插入为O(1)，查询效率比顺序列表低，O(n)
栈和队列：
栈是限定仅在表尾进行插入和删除操作的线性表
队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表
栈/队列的二种实现：数组实现栈，队列，链表实现简述（见上面LinkedList）
ArrayDeque
object[] elements;//元素数组
int head;//头部数据的位置索引
int tail;//尾部数据的位置索引
扩容规则：默认长度16，传入值会转换成2^n，当头部head == tail时，说明没有位置可以储存数据，进行扩容2倍，然后将数据拷贝到新数组头部，head重新赋值0，tail赋值为原来的数组长度n
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
添加/插入：设置后检测是否需要扩容
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
删除：删除前后元素时间复杂度为O(1)，然后修改head或者tail，删除对象会遍历数组O(n)，找到相应下标，然后移动拷贝整个数组
查找/搜索：获取前后元素为O(1)
排序：无
优缺点：查找元素，删除前后元素效率高，删除其他位置O(n)
栈（LIFO,FILO）常用方法是void push()，E pop()，操作失败抛出异常，默认调用的是addFirst，removeFirst
队列（FIFO）常用方法是boolean offer(E)，E poll()，操作失败返回false，null，默认调用的是addLast，pollFirst
串
零个或多个字符组成的有限序列
String
char[] value;//字符数组
int hash;//hash值
固定长度，构造方法不传如数组或串，默认为空串""，不可变类，操作形成新的String对象
操作方法:
String(char[] arr)
String(String str)
String(byte[] bytes)
length()
getChars(char[] buf,int len)
isEmpty()
charAt(int index)
compareTo
startWith
indexOf
subString
replaceAll
split
concat
startWith，endWitdh
偏移length进行普通匹配算法O(n-m+1)
indexOf
普通匹配算法O(n-m+1)*m，KMP子串匹配算法O(n+m)
replaceAll
正则匹配实现
网友评论