链表如何实现随机访问？通过指针数组下标访问节点是否属于随机访问？

结论 #

你并没有实现链表的随机访问，能直接通过ll[1]->data读取节点值，依赖的是额外定义的指针数组的能力，和链表本身的结构特性无关。

核心逻辑说明 #

我们常说「链表必须按顺序访问」，指的是仅持有链表头节点指针的前提下，无法直接定位到第k个节点，必须从头节点开始沿着next指针顺次遍历k次才能拿到目标节点，访问操作的时间复杂度是O(k)，这是链表本身的结构决定的。

你的代码里额外定义了node *ll[n];这个存储所有节点指针的数组，相当于你提前给所有节点的内存地址建了索引，你调用ll[1]本质是在使用数组的随机访问能力，而非通过链表本身的结构查找节点。

验证方法 #

你可以在链表拼接完成后，销毁这个指针数组，仅保留头节点指针：

node* head = ll[0];
// 假设此处释放ll数组的内存

这时候你如果要读取第2个节点的值，就只能通过head->next->data的方式顺次访问，要读取第10个节点就需要连续访问9次next指针，这才是链表本身的真实访问能力。

额外说明 #

你当前的实现还存在两个可优化点：

• 代码中使用的变长数组node *ll[n]不属于标准C++语法，属于编译器扩展功能，可移植性较差
• 额外维护节点指针数组的前提下，链表插入、删除节点时都需要同步更新数组内容，反而会丢失链表本身插入、删除操作时间复杂度低的优势

内容的提问来源于stack exchange，提问作者Shashwat pandey