Editing 2483: Linked List Interview Problem

{{comic
| number    = 2483
| date      = June 30, 2021
| title     = Linked List Interview Problem
| image     = linked_list_interview_problem.png
| titletext = I'd traverse it myself, but it's singly linked, so I'm worried that I won't be able to find my way back to 2021.
}}

==Explanation==
{{incomplete|Created by a LINKED LIST. Please mention here why this explanation isn't complete. Do NOT delete this tag too soon.}}

In computer programming, a {{w|Linked_list|Linked list}} is a type of data structure that stores data throughout memory accompanied with memory addresses of the next, and potentially previous data point, establishing a relative ordering for a collection of data. Several common software engineering interview questions involve manipulating or otherwise interacting with linked lists. Possibly because programmers in the current day rarely work with linked lists directly, Randall suggests that such structures belong in a "technology museum," and thinks it would be more beneficial to mankind to email the list to such a museum rather than perform any useful work with it.  Low-level software development is slowly getting replaced by automated code generation, but it is still very important to understand how it works.

A linked list is a way to store sequential data in computer memory. Each piece of data is stored with a pointer to the next piece. This makes it very easy to add new data in the middle, since only one existing pointer must change to point to the new data. The drawback of a naive implementation can be that finding data may require following the entire chain. Technical programming interviewers like to see if applicants are familiar with the structure and the computational complexity concept itself.

Linked lists are, historically, one of the two main data structures that represent sequential data, along with arrays. Unlike arrays, they have the theoretical advantage of O(1) insertions and deletions thanks to not needing to reallocate the entire structure, but have O(n) random access (see {{w|Linked_list#Linked_lists_vs._dynamic_arrays|comparisons}}). However, modern processors' cache structure favors data that are located next to each other, pre-fetching the adjacent items, and modern processors can perform bulk memory moves, making resize operations faster. Finally, using linked lists usually implies dynamic allocation of each list member, which adds overhead, particularly for smaller data items; many small allocations also tend to fragment memory, which can lead to it being wasted and unavailable to the app later, particularly in long-running processes such as web servers. These properties tend to make linked lists poorly suited for most system programming applications in which a programmer might write algorithms to manipulate data structures, instead of using existing libraries.

Modern programming languages usually provide abstractions (often named "array," "vector" or "list") which interact with the sequential data at the memory level, providing access to this data while using arrays, linked lists, hybrids of the aforementioned technologies, or other approaches, and the programmer doesn't necessarily need to care one way or another. Knowing the underlying concepts is still useful, however, when creating fast running code which scales well to large data, avoiding (e.g.) traversing the list over and over again, or performing particularly inefficient operations.

In the title text, a {{w|Linked_list#Singly_linked_list|singly linked list}} contains pointers to traverse the list in only one direction; namely, from the head to the end. By contrast, each element in a {{w|Linked_list#Doubly_linked_list|doubly linked list}} contains pointers to both the "next" and "previous" elements, enabling traversal in either direction. Randall continues the implication that such lists are obsolete by implying that traversing such a list would be akin to time travel to the past. Without the "previous element" pointers, Randall is concerned he would not be able to reverse the time travel, as he could not traverse the list in the reverse direction.

==Transcript==
{{incomplete transcript|Do NOT delete this tag too soon.}}

[Cueball is seen writing on a whiteboard, Ponytail is standing next to him. Above it, a piece of code is written, which apparently is what Cueball is writing on the whiteboard. The text reads:]

    define traverseLinkedList(headPointer):
       myId="''<illegible scribbling probably containing a user ID>''"
       authToken="''<illegible scribbling containing an auth token>''"
       museumAddress="''<illegible address>''@''<illegible domain>''.''<illegible tld>''"
       client=mailRestClient(myID, authToken)
       client.messages.send(to=museumAddress,
       subj="Item donation?", body="Thought you
       might be interested: "+str(headPointer))
       return

Ponytail: ''Hey.''

[Caption beneath the panel:]
Coding interview tip: Interviewers get really mad when you try to donate their linked lists to a technology museum.

{{comic discussion}}

[[Category:Comics with color]]
[[Category:Programming]]
[[Category:Tips]]