Editing 2483: Linked List Interview Problem
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 8: | Line 8: | ||
==Explanation== | ==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| | + | 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. |
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. | 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 | + | 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 as opposed to reserving memory for a bunch of items in a bulk and then using that memory once an item has to be added. Memory allocation tends to be slow on modern system and adds overhead for managing the information, which byte is allocated for what item, which can be significant, 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. | 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>''" | myId="''<illegible scribbling>''" | ||
authToken="''<illegible>''" | authToken="''<illegible>''" | ||
Line 33: | Line 33: | ||
subj="Item donation?", body="Thought you | subj="Item donation?", body="Thought you | ||
might be interested: "+str(headPointer)) | might be interested: "+str(headPointer)) | ||
− | return | + | 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}} | {{comic discussion}} | ||
[[Category:Comics with color]] | [[Category:Comics with color]] | ||
+ | [[Category:Programming]] | ||
[[Category:Tips]] | [[Category:Tips]] | ||
− | |||
− | |||
− | |||
− |