I am reading Data Structures and Algorithms by Alfred Aho, Jeffrey Ullman, et al. In the section about lists it's said:

We should note that a position in a linked-list implementation of a list behaves differently from a position in an array implementation. Suppose we have a list with three elements a, b, c and a variable p, of type position, which currently has position 3 as its value; i.e., it points to the cell holding b, and thus represents the position of c. If we execute a command to insert x at position 2, the list becomes a, x, b, c, and element b now occupies position 3. If we use the array implementation of lists described earlier, b and c would be moved down the array, so b would indeed occupy the third position.
However, if the linked-list implementation is used, the value of p, which is a pointer to the cell containing b, does not change because of the insertion, so afterward, the value of p is "position 4," not 3. This position variable must be updated, if it is to be used subsequently as the position of b.†

I don't understand how do position works? It's said that position works differently in pointer implementation that that of array but, the result seems to be the same on both. In both implementation position (pointer) moves forward. Then, what's the difference? I appreciate your answers.


1 Answer 1


First of all, let me strongly recommend avoiding outdated textbooks such as Aho, Hopcroft and Ullman.

Let me also replace Aho, Hopcroft and Ullman's use of "position" with the more common notion of pointer. In a linked list, each cell consists of a value and pointer to the following cell (if any). The linked list itself is represented as a pointer to its first cell (if any). Therefore, if we consider the list $a,b,c$, then a pointer which is pointing at the third element will be pointing at the cell containing $c$.

(This is also a good place to mention that unless you're programming in Fortran or in Excel, then your arrays are zero-based; that is, the first element is element number 0.)

Now suppose that $p$ is a pointer which currently points at the cell containing $c$. If you insert $x$ between $a$ and $b$, then $p$ will still be pointing at $c$. However, $c$ is now the fourth element rather than the third element.

In contrast, if the list were implemented as an array, then $p$ will be a pointer to the third element of the array. Therefore, after inserting $x$ between $a$ and $b$, the pointer $p$ will be pointing at $b$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.