0
$\begingroup$

I've been studying closely about the List abstract data type - As I understand it can be implemented with linked-list and/or arrays, and really maybe with any other data types as well.

But to satisfy a list, it means to have methods:

  1. that allow for insertion at desire 'position'.
  2. removal at desired 'position'.
  3. access data at nth position.
  4. prepend on the list
  5. append on the list
  6. size
  7. empty check.
  8. search by value. (necessary or not?)
  9. delete at end (necessary or not?)
  10. delete at front (necessary or not?)

(note: different sources seem to omit some or have additional ones - makes it extra frustrating without some standardization of what is core except assumptions)

I primarily use javascript. What I've noticed is a lot of JS implementation uses front-back nodes for doubly-linked lists to implement List ADT. Their implementation of removal/insertion is done by passing an index. Then iterate with for-loop to get to the that target node. This perplexes me, because it does not use the best features of linked lists, which is getting delete/insertion @ front, back, middle at O(1) given the pointers/reference. For middle, couldn't this be done with Javascript returning that Node Object? Then again I suppose, computational complexity isn't part of the requirement to satisfy an ADT (arguable at least).

To compare against Javascript, I looked at C++ and Java implementations. They have implementation such that it return a pointer when they search by nth item or by value. this pointer can be reused later to pass down on removal/insertion methods, making for-loop iterations not necessary, in other words O(n) => O(1). Surely this is better implementation maybe? again, its beyond just satisfying an ADT's requirement.

However, this all brings the title of the question. Is the pointer actually more preferred or it is actually more of an leaky abstraction and maybe should be discouraged? Javascript's common implementation leading to O(n) doesn't leak any implementation details by always returning value than the reference to Node object.

If I have to answer, maybe it makes sense for Javascript to use the O(n), because its such a high level language - it won't reap more benefit than all the optimization its done under the hood for its applications. Whereas lower language like C++ or Java covers more spaces where application of O(1) matters much more than a bit of leaky abstraction.

Additionally for practice/interviews, these are things I could point out in words.


Sources:

Javascript Implementation: https://www.tutorialspoint.com/The-Doubly-Linked-List-class-in-Javascript

Java Implementation: https://brilliant.org/wiki/linked-lists/

C++ Implementation (last couple pages): https://math.hws.edu/eck/cs327_s04/chapter2.pdf

$\endgroup$

1 Answer 1

1
$\begingroup$

Returning a pointer is not leaky, and is generally prefered, as it always permits more operations: access to the corresponding value, insertion at position and deletion in $\mathcal{O}(1)$.

Considering that a linear complexity is ok because the language is higher level is also wrong: lower complexity is better (unless the leading constant increases, but that is not the case here).

What could change between high level language and low level language is garbage collection and handling memory allocation of dereferenced pointers. However, not returning a pointer will not magically handle memory liberation for you.

My guess (I could not see the implementation for research) is that the tutorial is just that: a tutorial. It does not aim to create a super efficient data structure (which linked lists are not, it is often prefered when possible to use arrays in C or C++) but to teach elementary data structures.

$\endgroup$
1
  • $\begingroup$ Thanks so much, so its preferred ! I agree with your points. I've never worked with lower languages, so I can't say much about garbage collection, but couldn't that be encapsulated as part of the some instance method - so i don't see GC as reason to send pointers outside of its instance, other than using the pointer for insertion/deletion to get O(1) as you pointed out. I also deliberately omitted 'access', because access won't be O(1) - since access is O(n) to get that pointer node by some traversal of other conditions to match the target node. $\endgroup$
    – cozycoder
    Nov 30, 2022 at 7:15

Your Answer

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

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