A Textbook of Data Structures and Algorithms, Volume 1

6Linked Lists

In Chapters 3–5 we dealt with arrays, stacks and queues, which are linear sequential data structures (among the three, stacks and queues have a linked representation as well, which will be discussed in Chapter 7).

In this chapter, we detail linear data structures with a linked representation. We first list the demerits of the sequential data structure before introducing the need for a linked representation. Next, the linked data structures of singly linked list, circularly linked list, doubly linked list, multiply linked list, unrolled linked list and self-organizing linked list are elaborately presented. Finally, two problems, namely, polynomial addition and sparse matrix representation, demonstrating the application of linked lists are discussed.

6.1. Introduction

6.1.1. Drawbacks of sequential data structures

Arrays are fundamental sequential data structures. Even stacks and queues rely on arrays for their representation and implementation. However, arrays or sequential data structures in general suffer from the following drawbacks:

1. inefficient implementation of insertion and deletion operations;
2. inefficient use of storage memory.

Let us consider an array A[1: 20]. This means a contiguous set of 20 memory locations have been made available to accommodate the data elements of A. As shown in Figure 6.1(a), let us suppose the array is partially full. Now, to insert a new element 108 in the position indicated, it is not possible to do so without affecting the ...