Java基础：手动实现双向链表与ArrayList的区别

本篇Java基础笔记详细探讨了LinkedList（链表）的数据结构实现，与ArrayList（数组列表）相比，LinkedList在底层设计上有显著区别。LinkedList底层采用双向链表结构，这使得它具有独特的插入和删除操作性能优势。 首先，我们了解到LinkedList类的定义包含三个核心成员变量：`Node first`表示链表的头节点，`Node last`代表链表的尾节点，以及`int size`记录链表中元素的数量。这个类提供了两个关键方法： 1. `public boolean add(Object o)`：用于在链表尾部添加新的元素。当链表为空时，创建一个新的节点并设置`first`和`last`为该节点。如果链表不为空，创建一个新的节点并将其`next`属性指向当前`last`节点，然后更新`last`为新节点。最后，`size`增加1，返回`true`表示成功添加。 2. `public boolean add(int index, Object o)`：这个方法允许在指定索引位置插入元素。首先检查索引是否有效，避免越界异常。若索引为0，表示在头部添加，通过找到`first`节点的前一个节点，并更新其`next`指向新节点，同时将新节点设置为新的`first`。如果索引等于`size`，则调用`add(o)`方法直接在尾部添加。对于其他索引，获取相应索引的节点及其前一个节点，然后创建新节点，`pre`指向前一个节点，`next`指向当前节点，更新它们的链接关系。 这种链表设计使得插入和删除操作的时间复杂度通常为O(1)，因为只需修改几个指针即可完成，而ArrayList在插入或删除元素时，由于需要移动大量元素，时间复杂度为O(n)。了解并掌握LinkedList的工作原理对于编写高效数据结构和算法至关重要，特别是在需要频繁插入和删除元素的应用场景中。