2
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – D Goyal
    Sep 4, 2021 at 13:11
  • $\begingroup$ @InuyashaYagami I think I understood now what the OP meant. Thanks for this clarification! I will post an answer to that shortly $\endgroup$
    – nir shahar
    Sep 4, 2021 at 15:16
  • $\begingroup$ Ok nvm. I don't actually think I understand what the book wanted to say there... $\endgroup$
    – nir shahar
    Sep 4, 2021 at 15:46

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.