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$.

  • $\begingroup$ thanks for this answer, now understand whey they want to say. Secondly, can you recommend me some books on data structures and algorithm? $\endgroup$
    – user127304
    Commented Nov 14, 2020 at 15:30
  • $\begingroup$ The standard textbook is Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms. $\endgroup$ Commented Nov 14, 2020 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.