Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition

Why Linked Lists?

The simplicity of linked list questions appeals to interviewers who want to present at least two or three problems over the course of a 1-hour interview, because they must give you problems that you can be reasonably expected to answer in only 20 to 30 minutes. You can write a relatively complete implementation of a linked list in less than 10 minutes, leaving you plenty of time to solve the problem. In contrast, it might take you most of the interview period to implement a more complex data structure such as a hash table.

Also, little variation exists in linked list implementations, which means that an interviewer can simply say “linked list” and not waste time discussing and clarifying implementation details.

Perhaps the strongest reason is that linked lists are useful to determine whether a candidate understands how pointers and references work, particularly in C and C++. If you’re not a C or C++ programmer, you may find the linked list problems in this chapter challenging. Still, linked lists are so basic that you need to be familiar with them before moving to more complicated data structures found in the chapters that follow.

NOTE In real-world development, you don’t usually write your own linked lists; you use the implementation in your language’s standard library. In a programming interview, you’re expected to be able to create your own implementation to demonstrate that you fully understand linked lists.