Editing 2483: Linked List Interview Problem

In computer programming, a {{w|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.

In computer programming, a {{w|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.

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 {{w|Big O notation|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 systems 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.

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 {{w|Big O notation|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 systems 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.