在LinkedList有一段小代码,实现的功能是,在链表中间进行插如,所以在插如的过程中会需要找到对应的index位置的node元素;
如果放在平时只为了实现功能而进行遍历查找,很多人会直接使用一个while进行从前到后的查找,也不是说这种有问题,只是在
数据量相当大的情况下,如果还继续这样的查找,那么效率很定是很低的,
所有我们展示一个优秀的底层源码实现:
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
下边附一份自己写的MyArrayList的代码,该代码参考过源码;
public class MyArrayList<E> {
//涉及到的属性
private Object[] array;
private int size = 0;
private int modCount = 0;
private static int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//空参构造函数
MyArrayList()//设置默认大小
{
array = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//指定初始化大小的构造函数
MyArrayList(int initsize)
{
if(initsize < 0)
{
throw new IllegalArgumentException();
}
if(initsize > 0)
{
array = new Object[initsize];
}else //初始化大小为0时 将其设置为空
{
array = EMPTY_ELEMENTDATA;
}
}
private static int hugeCapacity(int minSize)
{
if (minSize < 0) // overflow
throw new OutOfMemoryError();
return (minSize > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
private void grow(int minSize)
{
int oldCapacity = this.array.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); //增长1.5倍
if (newCapacity - minSize < 0)
newCapacity = minSize;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minSize);
this.array = Arrays.copyOf(array, newCapacity);
}
private void ensureExplicitCapacity(int minSize)
{
modCount++;
if (minSize - array.length > 0)
grow(minSize);
}
public boolean ensureCapacityInternal(int minSize)
{
//在创建arraylist实例时,如果无参构造函数,则使用10作为初始大小
if (this.array == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
{
minSize = Math.max(DEFAULT_CAPACITY, minSize);
}
ensureExplicitCapacity(minSize);
return true;
}
public boolean add(E e)
{
//判断是否需要进行扩容
ensureCapacityInternal(size+1);
//在不需要扩容的情况下进行插入操作
array[size] = e;
++size;
return true;
}
public E move(int index)
{
if(index > this.size || index < 0)
{
throw new IllegalArgumentException();
}
E e = (E) this.array[index];
System.arraycopy(array, index+1, array, index, this.size-index);
this.size--;
this.modCount--;
return e;
}
public static void main(String[] args)
{
MyArrayList<String> mal = new MyArrayList<String>(2);
mal.add("a");
mal.add("b");
mal.add("c");
mal.add("d");
mal.add("e");
mal.move(3);
}