Page 107 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes
Figure 7.7: Linked List with Two Pointers

Source: http://www.cs.cmu.edu/~ab/15-123S09/lectures/Lecture%2010%20-%20%20Linked%20List%
20Operations.pdf

Example: Another example of multilinked list is a structure that represents a sparse
matrix as shown below. Sparse matrices are widely used in applications. A sparse matrix is a
6
6
large table of data where most are undefined. For example, we may have a 10 x 10 table of
6
6
integers. If we just allocate an array to hold this table, we would require 4 x 10 x 10 bytes of
memory. This is a very large chunk of contiguous memory that most computers don’t have.
Using a table where most entries are undefined to store this matrix is a bad idea. Therefore we
come up with a data structure where only store the defined values. A typical record in the
structure below consists of row and column index of the entry, value of the entry, a pointer to
next row and a pointer to next column.
Figure 7.8: A Sparse Matrix Representation

Source: http://www.andrew.cmu.edu/user/rmemon/121-n11/assignment3/writeup.html

100 LOVELY PROFESSIONAL UNIVERSITY