Chapter 2: Basic Abstract Data Types of the book Data Structures and Algorithms by Aho, Hopcroft & Ullman states the following:

If the list is a1, a2, ... , an, . . . For singly-linked lists, it is convenient to use a definition of position that is somewhat different . . . Here, position i will be a pointer to the cell holding the pointer to ai for i = 2, 3 , ... , n.

There is absolutely no explanation as to why this representation of list position is "convenient".

Why not just have position i directly as the pointer to ai for i = 2, 3 , ... , n?

Any insight would be appreciated.

Suppose the linked list is composed of three elements: $$a$$ $$b$$ $$c$$.

Suppose, we are asked to delete the second element, i.e., $$b$$. Then, to carry out the deletion operation it is convenient to keep the pointer to $$a$$ since the algorithm would need to update its $$next$$ pointer to $$c$$. Keeping the pointer at $$b$$ would not help update $$a$$'s pointer. Therefore, to manipulate the pointers pointing to $$b$$, and from $$b$$, it is always better/convenient to focus on the cell that appears before $$b$$, i.e., cell $$a$$.

Similarly, suppose you want to add an element at second position in the list , i.e., before $$b$$. Then, it is convenient to keep pointer at $$a$$ since its next pointer will be updated to the newly inserted element. Furthermore, from cell $$a$$, you can manipulate $$b$$'s pointer but not vice-versa (unless it is a doubly linked list).

In other words, when we need to manipulate some element $$a_i$$, we might require to make changes to the pointer pointing to it. Therefore, it is convenient to define position $$i$$ as the pointer to the cell before it, i.e., $$a_{i-1}$$.

It means that in practice, the linked list will ve fragmented in the memory, instead of being a contiguous array.

Say, for example, you want to delete an item. Using a regular list implementation, you will need to do $$O(n)$$ work - since you have to "move" all elements in the list so there won't be any "gaps".

However, using a linked list, since it is not contiguous in memory - we can implement the delete operation in $$O(1)$$.

That being said, linked lists aren't that useful, and usually are taught as "intermidiate objects" before teaching more complex structures that build up on the idea of pointers - such as binary trees, heaps, etc.

• Hi Nir Shahar, I think OP is asking why the convention of position $i$ is defined as pointer to the node storing the pointer to node $a_i$? And not simply pointer to the node storing $a_i$. Sep 4, 2021 at 13:11
• @InuyashaYagami I think I understood now what the OP meant. Thanks for this clarification! I will post an answer to that shortly Sep 4, 2021 at 15:16
• Ok nvm. I don't actually think I understand what the book wanted to say there... Sep 4, 2021 at 15:46