（全网首发）新一代可以直接访问的链表（1.0）

是的，链表也可以直接访问，非常河里，这是我推出的第一代可以直接

O(1)查询，O(1)修改

的全新链表。

思路：对于一个类型为T的数组a，数组名a实际上是指向数组第一个元素的指针。如果每个元素的大小为sizeof(T)，那么第i个元素（索引从0开始）的地址可以通过以下公式计算：

这就是为什么数组可以直接访问的原因，因为数组可以通过这种方式，能直接根据索引（i）计算出元素的地址，然后直接从地址中读入数据。

既然数组可以这样，为什么链表不可以，于是我们明显想到可以通过强行纂改内存达到目的，哈哈哈哈哈。

对了，此代码是干这个的：
有n个节点，q个询问，每次询问第x个节点。

CPP

5(n) 3(q)
2 4 1 3 5
1
4
3

上代码

CPP

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int value;
    Node* next;
};
int main() {
    int n,q;
	scanf("%d%d",&n,&q);
//-------------------------------
    void *memory=malloc(n*sizeof(Node));//分配内存
    Node *head=nullptr;
    Node *prev=nullptr;
//-------------------------------
    for (int i=1;i<=n;i++) {//转换类型
        int x;
        scanf("%d",&x);
        Node *n=reinterpret_cast<Node*>(static_cast<char*>(memory)+x*sizeof(Node));
        n->value=x;
        n->next=nullptr;
        if (head==nullptr){
            head=n;
        } 
		else{
            prev->next=n;
        }
        prev=n;
    }
//-------------------------------
    //计算地址
    for(int i=1;i<=q;i++){
		int index;
		scanf("%d",&index);
	    Node* inquire=reinterpret_cast<Node*>(static_cast<char*>(memory)+index*sizeof(Node));
	    printf("%d\n",inquire->value);
	}
    return 0;
}

（全网首发）新一代可以直接访问的链表（1.0）

讨论操作

回复

相关推荐

（全网首发）新一代可以直接访问的链表（1.0）