Talk:2483: Linked List Interview Problem

Assuming not everyone understands O notation: O(1) means that it always takes the same time, no matter how much data is stored. O(n) means the time is proportional to the amount of data stored - if you have 10 times the data, it takes 10 times as long to find the one you want. 108.162.221.84 (talk) (please sign your comments with ~~~~)

This code won't mail the linked list to a museum - it will mail the memory location of the head of the list to a museum. 172.70.130.192 (talk) (please sign your comments with ~~~~)

I think part of the joke might be that the high-level language being used will actually spit out a representation of the entire list when using the str function. So it actually does all the traversing and abstracts it away, again making the interview question seem redundant! 162.158.159.48 10:40, 1 July 2021 (UTC)

The language looks almost like Python -- the only difference being the keyword define instead of def. Lisp is the only family of languages I can think of that automatically converts linked lists to a representation of all the elements, since the linked list is its fundamental data structure. Barmar (talk) 14:06, 1 July 2021 (UTC)

just to make sure I get this right. If I want to save the numbers "1", "2", "3", "4" in an array it could (depending on the programming language) just be "[1,2,3,4]", while a linked list could be "1 (jump to 3rd entry), 4, 2 (jump to 4th entry), 3 (jump to 2nd entry)"? Then entering 2.5 between 2 and 3 would be complicated in the array as you have to move the 3 and 4 to new places, while in the linked list you just change the direction after to to jump to 5th entry, and add 2.5 and the instruction to jump to 4th entry? While it is of course harder to find a specific entry in the linked list. --Lupo (talk) 06:01, 1 July 2021 (UTC)

At the lowest level of access, such an array would be like the sequence "1234" (analogising to a simple string/char-array), asking for the nth-element quickly gets the nth-character by offset plus suitably multiplied memory reference). Inserting ("12a34") or deleting ("124") needs at least partial shuffling and resizing, while switching ("1324") or other internal re-ordering has widely variable overheads.

A linked-list could be thought of as defining as "¹" with ¹="1²", ²="2³", ³="3⁴" and ⁴="4∅", taking up more initial memory, and effort to discover the nth item. But, done right and for the right reasons, additions (²="2⁵", ⁵="a³"), removals (²="2⁴", dump/reuse ³) and switches (either ²="3³", ³="2⁴" or ¹="1³", ³="3²", ²="2⁴") can be as efficient as possible once the splice-and-switch process knows which points to work with.

(A linked-list sorter/editor will probably traverse the list, not worrying what 'offset' it is at, but holding an ⁿ pointer address for at least two adjacent items, ready to alter their ⁿs-as-reference to fulfil the change required, without worrying which ⁿs they were, and when created in whatever the next memory slot is.)

Doubly-linked might be list header "¹" where ¹="∅1²", ²="¹2³", ³="²3⁴" and ⁴="³4∅" and is heavier in storage (though often balanced by the "1234" being much more complex as actual data (e.g. multi-word, possibly variable-length records) than the simple ⁿs, that in an array-accessed form would include far too much padding and wasting storage (or too little, requiring optionally-defined ⁿs at the end of each fixed-length record to direct to an 'overflow' memory location, effectively LLing) thus justifying the potential LL packing overheads.

For further hybrid fun, nothing stops you having a fixed array "¹²³⁴∅∅∅" and define ¹="1", etc, then change the array-of-references accordingly ("¹²⁵³⁴∅∅", "¹²⁴∅∅∅∅", "¹³²⁴∅∅∅" or - if it's sensible - "¹²³⁴³²¹" which actually does something the LL would be hard-pressed to achieve for you without further structural overheads specifically designed for beyond-linear traversal).

That it potentially becomes spaghetti-data should not concern you so long as you don't have spaghetti-code as well which causes some oversight of data-mangling to mess things up. And you'll probably want to maintain a custom data-dumper/collator/formatter capability to keep an eye on things as you're debugging the inevitably miswritten shuffle-function, and/or do battle with the compiler's garbage-handling insertions when you confuse it beyond reasonable limits. (No, wait, did you do full low-level garbage-handling yourself? Did you do it properly? ;) )

...but I must say I'm not overly keen to abandon modern inbuilt splice-functions (for arrays/otherwise) doing all this hard work for me. Only if I'm looking at something of more of a net-/tree-like relationship (esp. non-Euclidean), or something with complicated multi-layered disparity of pointed-at data might I design up from such basic foundations. But I can also be nostalgic about when it was far more necessary! 162.158.159.48 10:18, 1 July 2021 (UTC)

Does anyone know when the last comic was that used colors? Is this something worth mentioning? --162.158.88.42 06:11, 1 July 2021 (UTC)

I found the category: Category:Comics with color. --162.158.93.153 06:17, 1 July 2021 (UTC)

I added some words regarding the title text. Feel free to expand/clarify/correct as necessary. 172.69.35.209 06:57, 1 July 2021 (UTC)

The comic could also be a reference to the British Museum Algorithm. --162.158.88.110 09:09, 1 July 2021 (UTC)

I second a previous comment, the code *does not* send the list to the museum, only the string representation of the head pointer. So the examiner may be rightully pissed off because both can be true: the candidate is trying to make fun of list algorithms and he doesn't know how to deal with a list. (Unsure of what follows: given that the code looks like python, this may also be sarcasm about the style of (not only) python programming that always resorts to some external code module instead of defining new data structures and coding related methods. In this case, the external module is a museum :-) ). Xkcdmax (talk)

Those wondering why linked lists are considered obsolete: insertion and deletion performance is rarely the issue these days. It's the cost of enumerating over all elements in the list. Both arrays and linked lists have O(n) complexity there, but arrays have the lower cost. And that's before we get into stuff like caches liking predictable access patterns (pointer chasing is not predictable) and all those pointers costing precious cache memory space.--Henke37 (talk) 09:45, 1 July 2021 (UTC)