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

4.3. Linked List Problems

What follows are some typical problems about linked lists that you might encounter during an interview.

4.3.1. Stack Implementation

NOTE

Discuss the stack data structure. Implement a stack in C using either a linked list or a dynamic array, and justify your decision. Design the interface to your stack to be complete, consistent, and easy to use.

This problem is aimed at determining three things:

1. Your knowledge of basic data structures

2. Your ability to write routines to manipulate these structures

3. Your ability to design consistent interfaces to a group of routines

A stack is a last-in-first-out (LIFO) data structure: Elements are always removed in the reverse order in which they were added. The add element and remove element operations are conventionally called push and pop, respectively. Stacks are useful data structures for tasks that are divided into multiple subtasks. Tracking return addresses, parameters, and local variables for subroutines is one example of stack use; tracking tokens when parsing a programming language is another.

One of the ways to implement a stack is by using a dynamic array, an array that changes size as needed when elements are added. (See Chapter 6, "Arrays and Strings," for a more complete discussion of arrays.) The main advantage of dynamic arrays over linked lists is that arrays offer random access to the array elements — you can immediately access any element in the array simply by knowing its index. However, operations ...