数组和链表（Java & PHP）插入性能比较 - 十七度

PHP8.1 Array VS SplDoublyLinkedList

// 头部插入
$start = microtime(true);
$arr = [];
$loop = 10000;
for ($i = 0; $i < $loop; $i++) {
    array_unshift($arr, $i);
}
echo sprintf('数组消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

$start = microtime(true);
$list = new SplDoublyLinkedList();
for ($i = 0; $i < $loop; $i++) {
    $list->unshift($i);
}
echo sprintf('链表消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

// 运行结果
数组消耗时间: 0.24384785
链表消耗时间: 0.00041199

// 尾部插入
$start = microtime(true);
$arr = [];
$loop = 1000000;
for ($i = 0; $i < $loop; $i++) {
    $arr[] = $i;
}
echo sprintf('数组消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

$start = microtime(true);
$list = new SplDoublyLinkedList();
for ($i = 0; $i < $loop; $i++) {
    $list->push($i);
}
echo sprintf('链表消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

// 运行结果
数组消耗时间: 0.02418399
链表消耗时间: 0.05259395

// 中间插入
$start = microtime(true);
$arr = [];
$loop = 100000;
for ($i = 0; $i < $loop; $i++) {
    $arr[max(0, $i - 1000)] = $i;
}
echo sprintf('数组消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

$start = microtime(true);
$list = new SplDoublyLinkedList();
for ($i = 0; $i < $loop; $i++) {
    $list->add(max(0, $i - 1000), $i);
}
echo sprintf('链表消耗时间: %.8f', microtime(true) - $start) . PHP_EOL;

// 运行结果
数组消耗时间: 0.00508404
链表消耗时间: 8.30184579

Java17 ArrayList VS LinkedList

// 头部插入
long start = System.currentTimeMillis();
List<Integer> arrayList = new ArrayList<>();
int loop = 100000;
for (int i = 0; i < loop; i++) {
        arrayList.add(0, i);
}
System.out.printf("数组消耗时间: %d%n", System.currentTimeMillis() - start);

start = System.currentTimeMillis();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < loop; i++) {
        linkedList.add(0, i);
}
System.out.printf("链表消耗时间: %d%n", System.currentTimeMillis() - start);

// 运行结果
数组消耗时间: 468
链表消耗时间: 6

// 尾部插入
long start = System.currentTimeMillis();
List<Integer> arrayList = new ArrayList<>();
int loop = 1000000;
for (int i = 0; i < loop; i++) {
        arrayList.add(i);
}
System.out.printf("数组消耗时间: %d%n", System.currentTimeMillis() - start);

start = System.currentTimeMillis();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < loop; i++) {
        linkedList.add(i);
}
System.out.printf("链表消耗时间: %d%n", System.currentTimeMillis() - start);

// 运行结果
数组消耗时间: 30
链表消耗时间: 106

// 中间插入
long start = System.currentTimeMillis();
List<Integer> arrayList = new ArrayList<>();
int loop = 100000;
for (int i = 0; i < loop; i++) {
        arrayList.add(Math.max(0, i - 1000), i);
}
System.out.printf("数组消耗时间: %d%n", System.currentTimeMillis() - start);

start = System.currentTimeMillis();
List<Integer> linkedList = new LinkedList<>();
for (int i = 0; i < loop; i++) {
        linkedList.add(Math.max(0, i - 1000), i);
}
System.out.printf("链表消耗时间: %d%n", System.currentTimeMillis() - start);

// 运行结果
数组消耗时间: 17
链表消耗时间: 161

结论

头部插入链表比数组快，尾部插入和中间插入数组比链表快

分析

头部插入，数组每次都需对数组扩容（ArrayList可变数组的特点，如果容量不够，会新建一个容量更大的数组，并把老数组的元素copy过去），链表改变各指针指向
中间插入，数组直接对某个索引设置值，容量不够时才扩容，链表改变各指针指向

尾部插入，数组直接对某个索引设置值，容量不够时才扩容，链表改变各指针指向

/* jdk ArrayList.add源码 */
// 指定索引插入
public void add(int index, E element) {
     rangeCheckForAdd(index);
     modCount++;
     final int s;
     Object[] elementData;
     // 头部插入必定扩容，中间插入容量不够时才扩容
     if ((s = size) == (elementData = this.elementData).length)
         elementData = grow();
     System.arraycopy(elementData, index,
                      elementData, index + 1,
                      s - index);
     elementData[index] = element;
     size = s + 1;
}
// 尾插
public boolean add(E e) {
     modCount++;
     add(e, elementData, size);
     return true;
}
private void add(E e, Object[] elementData, int s) {
     //  尾部插入容量不够时才扩容
     if (s == elementData.length)
         elementData = grow();
     elementData[s] = e;
     size = s + 1;
}

/* jdk LinkedList.add源码 */
// 指定索引插入
public void add(int index, E element) {
     checkPositionIndex(index);

     if (index == size)
         // 头/尾插
         linkLast(element);
     else
         // 中间插，可以看到这里多了查询节点
         linkBefore(element, node(index));
}
void linkLast(E e) {
     final Node<E> l = last;
     final Node<E> newNode = new Node<>(l, e, null);
     last = newNode;
     if (l == null)
         first = newNode;
     else
         l.next = newNode;
     size++;
     modCount++;
}
void linkBefore(E e, Node<E> succ) {
     // assert succ != null;
     final Node<E> pred = succ.prev;
     final Node<E> newNode = new Node<>(pred, e, succ);
     succ.prev = newNode;
     if (pred == null)
         first = newNode;
     else
         pred.next = newNode;
     size++;
     modCount++;
}
Node<E> node(int index) {
     // assert isElementIndex(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;
     }
}
// 尾插
public boolean add(E e) {
     linkLast(e);
     return true;
}

思考

阅读JDK源码对提升自己有很大的帮助，PHP对应的函数实现应该是大同小异的，但是首先要具备阅读C代码的能力
目前的状态是换了Java CURD，有些Javaer写的代码也是shit一样，但是生态真的太强大了
个人渐渐对编程失去了兴趣，后面可能学习前端和python，刺激一下撸码的欲望，另外也好好复习英语，为以后转型做准备吧