如何在链表中随机访问?

Question

正如我们所说，我们必须按顺序访问链表中的元素。

cout<<"Enter size of linked list : ";
int n;
cin>>n;
node *ll[n];
cout<<endl<<"enter elements : ";
for(int i=0;i<n;i++)
{
ll[i]=new node();
ll[i]->next=NULL;
cin>>ll[i]->data;
}
for(int i=0;i<n-1;i++)
{
ll[i]->next=ll[i+1];
}
cout<<endl<<ll[1]->data;

cout<<endl<<ll[1]->data;我可以用这行访问一个随机元素，对吧?

Answer 1

正如Jonathan Leffler在评论中指出的那样，您创建了一个节点数组并将它们链接在一起，但是您没有将它们用作链表，而是用作数组。

您可以保存指向给定节点的指针，并使用它来稍微加快访问速度，但不能保证指针在列表发生其他变化时仍然有用。

链表访问本质上不是恒定时间的。