1. 概念
学习数据结构一般都是从数组开始，以为相对来说简单，而且也最常用。
Array
数组是我们在编程中最常用的数据结构，它是线性的数据结构，即在内存中是连续的，所以可以很方便的进行遍历，只要有首地址，就可以根据角标计算出所要拿到的元素的地址：
arr[i] = arr[0] + K * i;
K是一个元素所占的字节数，例如在java中，一个 int 元素占有 4 个字节；
实际上，学到 c 语言的知道，数组也是指针，意思是数组元素的首地址对应于指针。在java中虽然没有指针，但是使用的引用，底层应该也是指针。同时 java 中提供了很多的数据结构，ArrayList 比较常见，是对数组的一种封装，而且提供了很多方法，开发中我们一般直接使用 ArrayList，不使用数组。但是在有些场景下，使用数组会更加高效，对于这两种的选择可以参考下面的几点：
- Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。
- 如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。
- 当要表示多维数组时，用数组往往会更加直观(个人观点)。比如 Object[][] array；而用容器的话则需要这样定义：ArrayList<ArrayList > array。
总结一下，对于业务开发，直接使用容器就足够，省时省力。毕竟损耗一些性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能优化需要做到极致，这个时候数组就会优于容器，成为首选。
2. ArrayList
在 java 中既然是最常用的，那么也需要了解下其原理，自己动手练习一下。最基本 的也就是增删改查这些方法，再加上它的一些特性，动态扩容，迭代器等。下面我们就来练习一下。
定义 接口：
public interface RList<T> {
int size();
boolean isEmpty();
boolean contains(T o);
T[] toArray();
boolean add(T o);
boolean remove(T o);
void clear();
T get(int index);
T set(int index, T element);
void add(int index, T element);
T removeByIndex(int index);
int indexOf(T o);
RIterator<T> iterator();
}
定义迭代器：
public interface RIterator<T> {
boolean hasNext();
T next();
}
具体实现：
public class RArrayList<T> implements RList<T> {
private static final int DEFAULT_CAPACITY = 20;
private T[] items;
private int capacity;
private int count;
public RArrayList() {
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public RArrayList(int capacity) {
this.capacity = capacity;
Object[] objects = new Object[capacity];
items = (T[]) objects;
}
@Override
public int size() {
return count;
}
@Override
public boolean isEmpty() {
return count < 1;
}
@Override
public boolean contains(T o) {
return indexOf(o) > -1;
}
@Override
public T[] toArray() {
if (isEmpty()) {
return null;
}
@SuppressWarnings("unchecked")
T[] arrayItems = (T[]) new Object[count];
System.arraycopy(items, 0, arrayItems, 0, count);
return arrayItems;
}
@Override
public boolean add(T o) {
ensureCapacity();
items[count++] = o;
return true;
}
@Override
public boolean remove(T o) {
if (isEmpty()) {
return false;
}
int index = indexOf(o);
if (index < 0) {
return false;
}
for (int i = index; i < count - 1; i++) {
items[i] = items[i + 1];
count--;
}
return true;
}
@Override
public void clear() {
if (isEmpty()) {
return;
}
for (int i = 0; i < count; i++) {
items[i] = null;
}
count = 0;
}
@Override
public T get(int index) {
checkIndex(index);
if (isEmpty()) {
return null;
}
return items[index];
}
@Override
public T set(int index, T element) {
checkIndex(index);
T oldItem = items[index];
items[index] = element;
return oldItem;
}
@Override
public void add(int index, T element) {
checkIndex(index);
ensureCapacity();
for (int i = count; i > index; i--) {
items[i] = items[i-1];
}
items[index] = element;
count++;
}
@Override
public T removeByIndex(int index) {
checkIndex(index);
T oldItem = items[index];
for (int i = index; i < count - 1; i++) {
items[i] = items[i + 1];
}
items[count - 1] = null;
count--;
return oldItem;
}
@Override
public int indexOf(T o) {
if (isEmpty()) {
return -1;
}
int index = -1;
for (int i = 0; i < count; i++) {
T item = items[i];
if (Objects.equals(item, o)) {
index = i;
break;
}
}
return index;
}
@SuppressWarnings("unchecked")
private void ensureCapacity() {
if (count == capacity) {
capacity = capacity * 3 / 2;
T[] newItems = (T[]) new Object[capacity];
System.arraycopy(items, 0, newItems, 0, count);
items = newItems;
}
}
private void checkIndex(int index) {
if (index < 0 || index >= capacity) {
throw new IndexOutOfBoundsException("index is invalid");
}
}
@Override
public RIterator<T> iterator() {
return new RArrayListIterator();
}
private class RArrayListIterator implements RIterator<T> {
private int index = 0;
RArrayListIterator() {
}
@Override
public boolean hasNext() {
return index < size();
}
@Override
public T next() {
if (hasNext()) {
return items[index++];
}
return null;
}
}
}
这样就自己简单实现了ArrayList，对于它的基本原理也有了一定的认识，之后再看看源码。这种数据结构也就掌握了，其实，最重要的还是学习源码中的思想，能够指引我们自己写代码的思路和方式。
除了实现，还写了测试的代码，当然测试的代码测试的并不全面，可能还存在一定的漏洞，像边界部分的处理。
public class RArrayListTest {
RList<Integer> list;
@Before
public void init() {
list = new RArrayList<>(10);
for (int i = 0; i < 10; i++) {
list.add(i);
}
}
@Test
public void size() {
Assert.assertEquals(10, list.size());
}
@Test
public void isEmpty() {
Assert.assertFalse(list.isEmpty());
RList<Integer> tempList = new RArrayList<>();
Assert.assertTrue(tempList.isEmpty());
}
@Test
public void contain() {
Assert.assertTrue(list.contains(5));
Assert.assertFalse(list.contains(10));
}
@Test
public void toArray() {
Object[] integers = list.toArray();
Assert.assertEquals(10, integers.length);
for (int i = 0; i < integers.length; i++) {
Assert.assertEquals(i, integers[i]);
}
}
@Test
public void get() {
for (int i = 0; i < list.size(); i++) {
Assert.assertEquals(i, list.indexOf(i));
}
for (int i = 0; i < list.size(); i++) {
Assert.assertEquals(i, list.get(i).intValue());
}
}
@Test
public void add() {
Assert.assertTrue(list.add(10));
Object[] integers = list.toArray();
for (int i = 0; i < integers.length; i++) {
Assert.assertEquals(i, integers[i]);
}
Assert.assertTrue(list.contains(10));
Assert.assertEquals(11, list.size());
list.add(3, 30);
integers = list.toArray();
for (int i = 0; i < integers.length; i++) {
if (i == 3) {
Assert.assertEquals(30, integers[i]);
} else if (i > 3) {
Assert.assertEquals(i - 1, integers[i]);
} else {
Assert.assertEquals(i, integers[i]);
}
}
}
@Test
public void remove() {
for (int i = 0; i < 3; i++) {
list.removeByIndex(0);
}
Assert.assertEquals(7, list.size());
for (int i = 0; i < list.size(); i++) {
Assert.assertEquals(i + 3, list.get(i).intValue());
}
Assert.assertTrue(list.remove(8));
Assert.assertEquals(6, list.size());
Assert.assertEquals(9, list.get(5).intValue());
}
@Test
public void set() {
for (int i = 0; i < list.size(); i++) {
list.set(i, i + 1);
Assert.assertEquals(i + 1, list.get(i).intValue());
}
}
@Test
public void clear() {
list.clear();
Assert.assertTrue(list.isEmpty());
}
@Test
public void iterator() {
RIterator<Integer> iterator = list.iterator();
int i = 0;
while (iterator.hasNext()) {
Assert.assertEquals(i++, iterator.next().intValue());
}
}
}
以上就是对 ArrayList 的简单实现，另外也写了一部分的 C 代码的实现，C 代码部分没有实现迭代器等方法，主要实现了利用数组实现一个list，能够增删改查，能够扩容等操作。有兴趣的可以自己试试，模仿 vector。
网友评论