Random access of a linked list element

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

To clear your confusion we probably should add the example of an array

Say we have an array

[1,2,3,4,5]

and a linkedlist

1->2->3->4->5

now if you want to access the 5th element in both the data structure what can you do

for array you just have to access the array[4] to get the element which is a O(1) operation to get the element

but for linkedList this doesn't happen

for accessing the 5th element of the linkedList you ll have to iterate in a manner like this

int element = 5;
while(element--){
   head = head->next;
}
and when the loop ends you ll get your element