数据结构与算法学习-数组
本文共 8274 字，大约阅读时间需要 27 分钟。
1. 概念
学习数据结构一般都是从数组开始，以为相对来说简单，而且也最常用。
数组是我们在编程中最常用的数据结构，它是线性的数据结构，即在内存中是连续的，所以可以很方便的进行遍历，只要有首地址，就可以根据角标计算出所要拿到的元素的地址：
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 array。
总结一下，对于业务开发，直接使用容器就足够，省时省力。毕竟损耗一些性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能优化需要做到极致，这个时候数组就会优于容器，成为首选。
2. ArrayList
在 java 中既然是最常用的，那么也需要了解下其原理，自己动手练习一下。最基本 的也就是增删改查这些方法，再加上它的一些特性，动态扩容，迭代器等。下面我们就来练习一下。
定义 接口：
public interface RList{ 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 iterator();}
定义迭代器：
public interface RIterator{ boolean hasNext(); T next();}
具体实现：
public class RArrayListimplements RList { 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 iterator() { return new RArrayListIterator(); } private class RArrayListIterator implements RIterator { 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 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 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 iterator = list.iterator(); int i = 0; while (iterator.hasNext()) { Assert.assertEquals(i++, iterator.next().intValue()); } }} 以上就是对 ArrayList 的简单实现，另外也写了一部分的 C 代码的实现，C 代码部分没有实现迭代器等方法，主要实现了利用数组实现一个list，能够增删改查，能够扩容等操作。有兴趣的可以自己试试，模仿 vector。
3. 参考代码
转载地址：http://cidws.baihongyu.com/
你可能感兴趣的文章
浅析 Laravel 官方文档推荐的 Nginx 配置
查看>>
Swagger在Laravel项目中的使用
查看>>
Laravel 的生命周期
查看>>
CentOS Docker 安装
查看>>
Nginx
查看>>
Navicat远程连接云主机数据库
查看>>
Nginx配置文件nginx.conf中文详解（总结）
查看>>
Mysql出现Table 'performance_schema.session_status' doesn't exist
查看>>
MySQL innert join、left join、right join等理解
查看>>
vivado模块封装ip/edf
查看>>
sdc时序约束
查看>>
Xilinx Jtag Access/svf文件/BSCANE2
查看>>
NoC片上网络
查看>>
开源SoC整理
查看>>
【2020-3-21】Mac安装Homebrew慢，解决办法
查看>>
influxdb 命令行输出时间为 yyyy-MM-dd HH:mm:ss(年月日时分秒)的方法
查看>>
已知子网掩码，确定ip地址范围
查看>>
判断时间或者数字是否连续
查看>>
docker-daemon.json各配置详解
查看>>
Mac 下docker路径 /var/lib/docker不存在问题
查看>>