8.7. Conclusion

The chosen implementation of an interface can have a large impact on the program in which it is used. Selecting the appropriate implementation is an important decision. In this chapter, we discussed a linked list vs array implementation for the List ADT. The benefits and drawbacks of each approach are summarized in the table below:

	Array Approach	Linked List Approach
Pros	Fast Access to Elements	Easy to Add new Nodes
Cons	Expensive to Resize	Slower access to elements

The main benefit of an array-based List implementation is extremely fast access to List elements. This is because arrays are laid out in a contiguous block of primary memory. The main drawback of an array-based approach is that an array’s size is fixed. Therefore, if you want to increase the size of an array, you are forced to create a new array of the larger size and subsequently copy over the elements of the old array to the new, larger array. As you can imagine, creating an array and copying all elements is an expensive operation for the CPU to perform — especially when the array size is large.