Data Structures and Algorithms with JavaScript

Chapter 6. Linked Lists

In Chapter 3 we discussed the use of lists for storing data. The underlying data storage mechanism we use for lists is the array. In this chapter we’ll discuss a different type of list, the linked list. We’ll explain why linked lists are sometimes preferred to arrays, and we’ll develop an object-based, linked-list implementation. We’ll end the chapter with several examples of how linked lists can solve many programming problems you will encounter.

Shortcomings of Arrays

There are several reasons arrays are not always the best data structure to use for organizing data. In many programming languages, arrays are fixed in length, so it is hard to add new data when the last element of the array is reached. Adding and removing data from an array is also difficult because you have to move array elements up or down to reflect either an addition or a deletion. However, these problems do not come up with JavaScript arrays, since we can use the split() function without having to perform additional array element accesses.

The main problem with using JavaScript arrays, however, is that arrays in JavaScript are implemented as objects, causing them to be less efficient than arrays built in languages such as C++ and Java (see Crockford, Chapter 6).

When you determine that the operations performed on an array are too slow for practical use, you can consider using the linked list as an alternative data structure. The linked list can be used in almost every situation ...