In an article about linked list, it is said that accessing a random element is not allowed and to access a certain node we need to traverse it from the head node

#include <bits/stdc  .h>
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
};
 
// This function prints contents of linked list
// starting from the given node
void printList(Node* n)
{
    while (n != NULL) {
        cout << n->data << " ";
        n = n->next;
    }
}
 
// Driver code
int main()
{
    Node* head = NULL;
    Node* second = NULL;
    Node* third = NULL;
 
    // allocate 3 nodes in the heap
    head = new Node();
    second = new Node();
    third = new Node();
 
    head->data = 1; // assign data in first node
    head->next = second; // Link first node with second
 
    second->data = 2; // assign data to second node
    second->next = third;
 
    third->data = 3; // assign data to third node
    third->next = NULL;
 
    printList(head);
 
    return 0;
}

This was the example code on traversing a linked list and printing it's values

If i change the argument of printList() to second, it would still work

My question is, did i misinterpret the meaning to "access an element of a linkedlist", what does an element of a linkedlist contain?

CodePudding user response：

I think you overinterpreted the article. You should store in your program only pointer to the first element (head) and in that case, you are not able to access n-th element directly. You need to find it "manually" by jumping to "next" element (n-1) times.

It doesn't mean that you are not able to access n-th element if you have pointer to that element.

CodePudding user response：

accessing a random element is not allowed

That statement isn't quite precise about linked lists.

What is true is that given a linked list (and nothing more), it isn't possible find an element at any given index in constant time.

However, if you have an iterator or a reference to an element of a list, you can access that element in constant time through the iterator / reference.