基础
-
ArrayList：顺序列表，它是Array的增强版，也称动态数组，提供了动态的增加和减少数组，如果你阅读过它的源码，你会发现它内部就是采用数组来存储数据，并且动态扩容数组的长度，在日常开发中被广泛使用。 -
LinkedList：线性列表，但是和ArrayList不同的是，它采用了双向链表的数据结构，既然是链表的结构，那么就不需要考虑它的容量问题。 - 各自的优缺点：
-
ArrayList采用数组的结构，在添加和删除操作上的效率低，需要大量移动数组中的元素，但是在查找的效率高； -
LinkedList采用了链表的结构，在查找的方面效率极低，添加和删除的方面效率高； -
LinkedList占用内存比ArrayList更高，因为它的结点不仅村粗了数据，并且存储了前一节点和后一节点的引用。
-
制定手写方案：
- 两种列表都需要有：添加、删除、查找、清空、判空、循环遍历和获取大小的共有的方法；
-
LinkedList添加元素的方法需要区分类型：头部添加，尾部添加，指定下标添加；ArrayList也需要有添加整个数组的方法； -
LinkedList在本次的方案中采用的是单向链表而不是双向链表的结构。
手写ArrayList：
import java.util.Arrays;
import java.util.function.Consumer;
class ArrayList<E> {
// 用于保存空列表的引用
private static final Object[] EMPTY_ELEMENTDATA = {};
private Object[] _data;
private int _size;
private int _realLength;
// 列表默认的长度
private static final int LEN = 20;
public ArrayList(int initLen) {
if (initLen == 0) {
this._data = EMPTY_ELEMENTDATA;
} else if (initLen > 0) {
this._data = new Object[initLen];
} else {
throw new IllegalArgumentException("init length is error");
}
this._size = initLen;
this._realLength = 0;
}
public ArrayList() {
this(LEN);
}
/**
* 追加一个元素
*
* @param element 元素
*/
public void add(E element) {
checkLen();
_data[_realLength++] = element;
}
/**
* 指定下标插入
*
* @param index 下标
* @param element 元素
*/
public void add(int index, E element) {
checkIndex(index);
checkLen();
System.arraycopy(_data, index, _data, index + 1, _realLength - index);
_data[index] = element;
_realLength++;
}
/**
* 添加一个数组
*
* @param elements 数组元素
*/
public void addAll(E[] elements) {
for (E e : elements) {
checkLen();
_data[_realLength++] = e;
}
}
/**
* 获取指定下标的元素
*
* @param index 下标
* @return 下标对应的元素
*/
@SuppressWarnings("unchecked")
public E get(int index) {
checkIndex(index);
return (E) _data[index];
}
/**
* 删除指定下标的元素
*
* @param index 下标
* @return 删除的元素
*/
@SuppressWarnings("unchecked")
public E remove(int index) {
checkIndex(index);
Object delete = _data[index];
System.arraycopy(_data, index + 1, _data, index, _realLength - index - 1);
_data[--_realLength] = null;
return (E) delete;
}
/**
* 判断是否包含某个元素
*
* @param element 元素
* @return 包含返回true
*/
public boolean contain(E element) {
if (isEmpty()) return false;
else {
for (Object e : _data) {
if (e == element) {
return true;
}
}
return false;
}
}
/**
* 循环遍历列表
*
* @param consumer Consumer对象
*/
public void forEach(Consumer<E> consumer) {
if (isEmpty()) {
return;
}
for (Object object : _data) {
if (object != null)
consumer.accept((E) object);
}
}
/**
* 清空列表元素
*/
public void clear() {
for (int i = 0; i < _realLength; i++) {
_data[i] = null;
}
_realLength = 0;
}
/**
* 检查下标是否越界
*
* @param index 下标
*/
private void checkIndex(int index) {
if (index < 0 || index > _realLength) {
throw new IndexOutOfBoundsException();
}
}
public boolean isEmpty() {
return _realLength == 0;
}
public int size() {
return _realLength;
}
/**
* 检查是否要扩容数组
*
* @return true 表示需要扩容
*/
private void checkLen() {
if (_realLength >= _size) {
grow();
}
/**
* 数组的扩容，扩容大小为原先的2倍
*/
private void grow() {
// 扩容后size也要变化
_size = _size * 2;
_data = Arrays.copyOf(_data, _size);
}
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(1, 2);
arrayList.add(3);
arrayList.add(1, 4);
System.out.print("原始数据：");
arrayList.forEach(element -> System.out.print(element + " "));
System.out.println();
arrayList.remove(1);
System.out.print("移除index=1的元素：");
arrayList.forEach(element -> System.out.print(element + " "));
System.out.println();
System.out.println("list has {1}: " + arrayList.contain(1));
System.out.println("list has {10}: " + arrayList.contain(10));
}
}
// 原始数据：1 4 2 3
// 移除index=1的元素：1 2 3
// list has {1}: true
// list has {10}: false
如上所述，在组织一个 ArrayList 的过程中，我们特别注意以下几点：
- 既然采用数组，那么就要注意它的容量问题，做好扩容的工作；
- 使用数组的过程中，千万别忘记处理数组越界问题；
- 在删除固定的元素后，别忘记了手动置空下。
实现一个简单的 ArrayList 还是挺简单的，自己动手写一遍会对 ArrayList 有另一番见解，快去动手敲一敲吧。
手写LinkedList：
import java.util.function.Consumer;
class LinkedList<E> {
// 列表的长度
private int _size;
// 头结点
private Node<E> _first;
// 尾结点
private Node<E> _last;
public LinkedList() {
_size = 0;
}
/**
* 在尾巴插入一个结点
*
* @param element 插入的数据
*/
public void addLast(E element) {
final Node<E> l = _last;
final Node<E> newNode = new Node<>(element, null);
_last = newNode;
if (l == null) {
// 如果之前的尾部元素为空，那说明列表为空，插入元素后，首尾应该都是newNode
_first = newNode;
} else {
l.next = newNode;
}
_size++;
}
/**
* 在头部插入元素
*
* @param element 插入的数据
*/
public void addFirst(E element) {
final Node<E> f = _first;
final Node<E> newNode = new Node<>(element, _first);
_first = newNode;
if (f == null) {
// 如果之前的头部元素为空，那说明列表为空，插入元素后，首尾应该都是newNode
_last = newNode;
} else {
newNode.next = f;
}
_size++;
}
/**
* 添加一个元素，默认在尾巴添加
*
* @param element 元素值
*/
public void add(E element) {
addLast(element);
}
/**
* 指定下标插入元素
*
* @param index 下标
* @param element 元素值
*/
public void add(int index, E element) {
// 特殊处理头尾
if (index == 0) {
addFirst(element);
return;
}
if (index == size() - 1) {
addLast(element);
return;
}
Node<E> newNode = new Node<>(element, null);
Node<E> pre = _first;
Node<E> next = _first.next;
for (int i = 1; i < size() - 1; i++) {
if (i == index) {
newNode.next = next;
pre.next = newNode;
_size++;
}
pre = next;
next = next.next;
}
}
/**
* 获取指定下标的元素值
*
* @param index 下标
* @return 值
*/
public E get(int index) {
checkIndex(index);
Node<E> f = _first;
for (int i = 0; i < size(); i++) {
if (i == index) {
return f.data;
} else {
f = f.next;
}
}
return null;
}
/**
* 移除指定下标的元素
*
* @param index 下标
* @return 返回移除的元素
*/
public E remove(int index) {
checkIndex(index);
Node<E> f = _first;
Node<E> l = _first;
// 需特殊处理头结点
if (index == 0) {
E element = f.data;
f = f.next;
_first = f;
_size--;
return element;
}
for (int i = 0; i < size(); i++) {
if (i == index) {
E element = f.data;
l.next = f.next;
_size--;
f.next = null;
f.data = null;
return element;
} else {
l = f;
f = f.next;
}
}
return null;
}
/**
* 检测是否包含某个元素
*
* @param element 包含的对象
* @return 包含返回true
*/
public boolean contain(E element) {
if (!isEmpty()) {
Node<E> f = _first;
for (int i = 0; i < size(); i++) {
if (f.data == element) return true;
f = f.next;
}
return false;
} else {
return false;
}
}
/**
* 遍历整个列表
*
* @param consumer Consumer对象
*/
public void forEach(Consumer<E> consumer) {
if (isEmpty()) {
return;
}
Node<E> f = _first;
while (f != null) {
E e = f.data;
consumer.accept(e);
f = f.next;
}
}
/**
* 清空
*/
public void clear() {
for (Node<E> x = _first; x != null; ) {
Node<E> next = x.next;
x.data = null;
x.next = null;
x = next;
}
_first = _last = null;
_size = 0;
}
/**
* 列表的长度
*
* @return 长度值
*/
public int size() {
return _size;
}
/**
* 判断列表是否为空
*
* @return 为空返回true
*/
public boolean isEmpty() {
return _size == 0;
}
/**
* 检查下标是否越界
*
* @param index 下标
*/
private void checkIndex(int index) {
if (index < 0 || index > _size) {
throw new IndexOutOfBoundsException();
}
}
/**
* 链表节点
*
* @param <E> 数据类型
*/
static class Node<E> {
E data;
Node<E> next;
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.addFirst(0);
linkedList.add(2);
linkedList.add(3);
System.out.print("原始数据： ");
linkedList.forEach(integer -> System.out.print(integer + " "));
System.out.println();
int remove = linkedList.remove(0);
System.out.println("remove data is: " + remove);
System.out.print("删除index为0的数据： ");
linkedList.forEach(integer -> System.out.print(integer + " "));
System.out.println();
linkedList.add(1, 10);
System.out.print("在index=1的地方添加数据10： ");
linkedList.forEach(integer -> System.out.print(integer + " "));
System.out.println();
System.out.println("list has {1}: " + linkedList.contain(1));
System.out.println("list has {100}: " + linkedList.contain(100));
}
}
// 原始数据： 0 1 2 3
// remove data is: 0
// 删除index为0的数据： 1 2 3
// 在index=1的地方添加数据10： 1 10 2 3
// list has {1}: true
// list has {10}: true
LinkedList 的实现过程中，比 ArrayList 要多出了几个操作，毕竟是链表的结构，插入元素可以分别在头部和尾部插入数据，对于熟悉链表结构的大佬来说一点，这点一点不成问题，不熟悉的小佬可以借此机会熟悉一下链表的操作。下面说一下几点注意的地方吧：
- 对于第一次插入数据的时候，无论实在头部还是尾部，一定要注意对
_first和_last的处理； - 在指定位置添加和删除元素的时候，一定要处理好前节点和后结点之间的联系，并且在删除的操作中别忘记了将删除后的节点数据置空。
如果本文章你发现有不正确或者不足之处，欢迎你在下方留言或者扫描下方的二维码留言也可！
网友评论