Hello World

02月10日

一、今日完成情况

• Java完成昨日单链表基本函数的手动封装复习
• Java完成双向链表的基本函数和用法的封装和理解

二、今日感悟

• 核心业务数据​：
  • java语法以及数据结构复习
• ​今日工作总结：​
  • 无
• ​明日工作计划：
  • 快慢指针
  • 二叉树入门
• ​今日学习成长：​
  • 复习而已，没啥成长，最近的内容就是C++语法对Java的映射。

三、备注

• 无

四、Java ArrayList用法

因为即使我手动封装数据结构，未来业务使用的也是Java集合，因此我需要把目前最常用的数据结构用法的–数据，所对应的集合实现上手。

List，默认指的就是 ArrayList，它底层是动态数组。

// 语法：List<类型> 变量名 = new ArrayList<>();
List<Integer> list = new ArrayList<>(); 

// 常用操作
list.add(10);      // 添加元素
list.get(0);       // 获取元素（耗时 $O(1)$，比链表快）
list.size();       // 获取长度
list.isEmpty();    // 判空

List<Integer> sourceList = Arrays.asList(1, 2, 3, 4, 5, 6);

特性	C++ std::vector	Java ArrayList
底层实现	连续内存数组	连续内存数组（存放的是对象的引用）
访问元素	vec[i] 或 vec.at(i)	list.get(i)
添加元素	push_back(val)	add(val)
获取长度	size()	size()
内存管理	开发者手动或析构函数自动	JVM 垃圾回收 (GC)

Arrays.asList(1, 2, 3) 是快速初始化，相当于创建一个固定大小的数组，然后Java容器初始化的时候，会把这个固定数组变化为可变数组的方式：

List<Integer> list = Arrays.asList(1, 2, 3); 
list.add(4); // ❌ 会抛出 UnsupportedOperationException 异常！因为它的长度锁死了。

// 先用 asList 快速生成，再套一层 ArrayList 变成真正的动态数组 
List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3)); 
list.add(4); // ✅ 没问题

Java增删查改：

操作	Java 代码	C++ 对应
创建	List<Integer> list = new ArrayList<>();	vector<int> v;
末尾插入	list.add(100);	v.push_back(100);
插入特定位置	list.add(0, 50); // 在下标 0 插入 50	v.insert(v.begin(), 50);
修改	list.set(0, 99);	v[0] = 99;
删除下标	list.remove(0);	v.erase(v.begin());
查找索引	list.indexOf(100);	std::find(...)

现在快速创建一个链表的方法如下：

public static void main(String[] args) {  
    ListNode newList = createList(Arrays.asList(1, 2, 3, 5));  
    printList(newList);  
}


static ListNode createList(List<Integer> nums) {  
    if (nums == null || nums.isEmpty()) return null;  
    ListNode virtual = new ListNode(-1);  
    ListNode cur = virtual;  
    for (Integer num : nums) {  
        ListNode node = new ListNode(num);  
        cur.next = node;  
        cur = node;  
    }  
    return virtual.next;  
}

五、双向链表任务梳理

// 你需要实现的双向版函数签名
public class MyDoublyLinkedList {
    
    // 1. 批量创建：注意建立 prev 链接
    static ListNode createList(List<Integer> nums) { ... }

    // 2. 插入：注意处理 index 为 0 和 index 为末尾的情况
    static ListNode pushList(ListNode head, int index, int val) { ... }

    // 3. 删除：注意处理删除的是头节点的情况
    static ListNode deleteList(ListNode head, int val) { ... }

    // 4. 正向打印
    static void printList(ListNode head) { ... }

    // 5. 反向打印（用来测试 prev 指针是否正确）
    static void printListBackward(ListNode head) {
        // 先找到尾节点
        ListNode cur = head;
        while (cur != null && cur.next != null) cur = cur.next;
        // 从尾部开始向回走
        while (cur != null) {
            System.out.print(cur.val + " <- ");
            cur = cur.prev;
        }
        System.out.println("null");
    }
}

reverseList(ListNode head)：

• 双向链表的反转其实比单链表简单：本质上就是交换所有节点的 next 和 prev 指针

简单记录一下我的Java文件，今天目前为止完成了Java的双向两边的除了翻转之外的所有函数，明天完成反转链表还有简单的回顾就开始二叉树，或者链表的面试快慢指针的高阶联系，二叉树可以开个头。

package io.github.luduihang.learning.list;  
import java.util.List;  
import java.util.Arrays;  
import java.util.Stack;  
  
class DoubleListNode {  
    int val;  
    DoubleListNode next;  
    DoubleListNode prev;  
    DoubleListNode(int val) {  
        this.val = val;  
    }  
}  
public class MyDoubleLinkedList {  
    public static void main(String[] args) {  
        System.out.println("这是我的测试脚本");  
        DoubleListNode n1 = createList(Arrays.asList(1, 2, 3));  
        printList(n1);  
        n1 = pushList(n1, 3, 0);  
        printList(n1);  
        printListBackward(n1);  
    }  
    // 1. 批量创建：注意建立 prev 链接  
    static DoubleListNode createList(List<Integer> nums) {  
        if (nums == null || nums.isEmpty()) return null;  
        DoubleListNode virtual = new DoubleListNode(-1);  
        DoubleListNode cur = virtual;  
        for (Integer num : nums) {  
            DoubleListNode node = new DoubleListNode(num);  
            node.prev = cur;  
            cur.next = node;  
            cur = cur.next;  
        }  
        return virtual.next;  
    }  
  
    // 2. 插入：注意处理 index 为 0 和 index 为末尾的情况  
    static DoubleListNode pushList(DoubleListNode head, int index, int val) {  
        if (head == null) return null;  
        DoubleListNode virtual = new DoubleListNode(-1);  
        virtual.next = head;  
        head.prev = virtual;  
        int len = GetLen(head);  
        if (index < 0 || index > len) {  
            System.out.print("illegal usage of index");  
            return head;  
        }  
        DoubleListNode cur = virtual;  
        for (int i = 0; i < index; i++) {  
            cur = cur.next;  
        }  
        if (cur.next == null) {  
            DoubleListNode newnode = new DoubleListNode(val);  
            cur.next = newnode;  
            newnode.prev = cur;  
        }  
        else {  
            DoubleListNode buf = cur.next;  
            DoubleListNode newnode = new DoubleListNode(val);  
            cur.next = newnode;  
            newnode.prev = cur;  
            buf.prev = newnode;  
            newnode.next = buf;  
        }  
        DoubleListNode res = virtual.next;  
        res.prev = null;  
        return res;  
    }  
  
    static int GetLen(DoubleListNode head) {  
        int len = 0;  
        while (head != null) {  
            len ++;  
            head = head.next;  
        }  
        return len;  
    }  
//    // 3. 删除：注意处理删除的是头节点的情况  
//    static ListNode deleteList(ListNode head, int val) { ... }  
  
    // 4. 正向打印  
    static void printList(DoubleListNode head) {  
        if (head == null) return;  
        while (head != null) {  
            System.out.print(head.val + " -> ");  
            head = head.next;  
        }  
        System.out.print("null\n");  
    }  
  
    static void printListBackward(DoubleListNode head) {  
        if (head == null) return;  
        while (head.next != null) {  
            head = head.next;  
        }  
        while (head != null) {  
            System.out.print(head.val + " -> ");  
            head = head.prev;  
        }  
        System.out.println("null");  
    }  
  
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 kipleyarch@gmail.com