开篇
近日由于出了一场意外受伤赋闲在家养伤，由于非科班出身，关于素有程序员的“易筋经”---数据结构与算法这块，都是在闲散的业余时间学习的，没有拿出整块的时间进行系统的研究与总结，也许这次伤病就是老天让我好好学习总结这块的知识，修炼内功吧！网上讲数据结构与算法的博客一堆，我也看了不少，最喜欢这位吴泽坚大神的专栏:https://my.csdn.net/javazejian，这里向大家安利一下，这个系列博客的准备工作也是基于他的数据结构专题的，目的也仅仅在于在拜读大神的文章的基础上，加点自己的理解，进行学习总结，个人建议优先看他的文章吧，写的棒棒哒！今天就从最简单的顺序表开始学习，在实现顺序表的过程中，我参考了JDK的部分源码，不过原理都是一样的。
顺序表的特点
1.它是线性表的一种，原理采用数组实现；
2.存储结构为一片连续的内存；
3.由于是线性存储结构，所以读写效率高，增删效率低。
接口定义
仿照JDK，定义的最顶层的接口是集合接口:
public interface Collection<T> {
int size();//大小
boolean isEmpty();//是否为空
void clear();//清空
boolean contains(T item);//是否包含元素
boolean add(T item);//添加
boolean remove(T item);//删除
}
由于列表有元素索引和迭代器的概念，所以与集合相比，列表接口定义多了一下方法声明:
public interface List<T> extends Collection<T>{
T get(int index);//读
T set(int index, T item);//写
void add(int index, T item);//增
T remove(int index);//删
Iterator<T> iterator();//迭代器
}
顺序表实现List接口，下面分别说明其实现
顺序表实现
成员变量:
public class ArrayList<T> implements List<T>{
private static final int DEFAULT_SIZE = 64;//数组默认大小
private int mSize;//当前元素
private T[] mItems;//元素数组空间
.....
}
1.增加元素逻辑:如果没有超出当前容量，则直接赋值，否则扩容。扩容逻辑分两步:开辟内存和数组内容拷贝。
/**
* 扩容操作
* @param newCapacity 目标容量
*/
private void ensureCapacity(int newCapacity) {
if (newCapacity < mSize) {
return;
}
//申请新空间
mItems = (T[]) new Object[newCapacity];
T[] oldItems = mItems;
//迁移数组
for (int i = 0; i < size(); i++) {
mItems[i] = oldItems[i];
}
}
增加元素:
@Override
public boolean add(T item) {
add(size(), item);
return true;
}
@Override
public void add(int index, T item) {
//边界条件判断
if (item == null) {
return;
}
//插入下标的容错判断,插入在最前面
if (index < 0) {
index = 0;
}
//插入下标的容错判断,插入在最后面
if (index > size()) {
index = size();
}
if (mItems.length == size()) {//当前容量已达上限,扩容
ensureCapacity(size() * 2);
}
//index后的元素后移
for (int i = mSize; i > index; i--) {
mItems[i] = mItems[i - 1];
}
//目标位置设置值
mItems[index] = item;
mSize++;//size++
}
2.删除元素逻辑:和增加逻辑相似，从插入位置往后到结尾，元素前移。
@Override
public T remove(int index) {
//边界条件判断
if (index < 0 || index >= size()) {
throw new ArrayIndexOutOfBoundsException();
}
T toRemoveItem = mItems[index];
//删除位置后面的元素前移
for (int i = index; i < size() - 1; i++) {
mItems[i] = mItems[i + 1];
}
mSize--;
return toRemoveItem;
}
3.改动和读取元素
@Override
public T set(int index, T item) {
if (index < 0 || index >= size()) {
throw new ArrayIndexOutOfBoundsException();
}
T oldItem = mItems[index];
mItems[index] = item;
return oldItem;
}
@Override
public T get(int index) {
if (index < 0 || index >= size()) {
throw new ArrayIndexOutOfBoundsException();
}
return mItems[index];
}
4.迭代器实现。
以上代码实现了顺序表的基本操作,下面说说线性表的迭代器。参照JDK源码，迭代器保存了当前遍历的元素位置，根据这个位置来读取和删除元素，接口定义:
public interface Iterator<T> {
boolean hasNext();//有无下一元素
T next();//读元素
void remove();//删除当前元素
}
迭代器原理.png
private class ArrayListIterator implements Iterator<T> {
private int mCurrentPos;
@Override
public boolean hasNext() {
return mCurrentPos < size();
}
@Override
public T next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
//读完当前元素后,位置后移
return mItems[mCurrentPos++];
}
@Override
public void remove() {
//位置回退，删除当前元素
ArrayList.this.remove(--mCurrentPos);
}
}
5.其他方法实现:
@Override
public boolean contains(T item) {
Iterator<T> iterator = iterator();
while (iterator.hasNext()) {
T obj = iterator.next();
if (obj.equals(item)) {
return true;
}
}
return false;
}
@Override
public boolean remove(T item) {
Iterator<T> iterator = iterator();
while (iterator.hasNext()) {
T obj = iterator.next();
if (obj.equals(item)) {
iterator.remove();
}
}
return false;
}
6.完整代码地址:数据结构与算法学习JAVA描述GayHub地址
