chap lists and arrays revisited cols rows figure the orthogonal list sparse matrix representation one approach to representing sparse matrix is to concatenate (or otherwise combinethe row and column coordinates into single value and use this as key in hash table thusif we want to know the value of particular position in the matrixwe search the hash table for the appropriate key if value for this position is not foundit is assumed to be zero this is an ideal approach when all queries to the matrix are in terms of access by specified position howeverif we wish to find the first non-zero element in given rowor the next non-zero element below the current one in given columnthen the hash table requires us to check sequentially through all possible positions in some row or column another approach is to implement the matrix as an orthogonal listas illustrated in figure here we have list of row headerseach of which contains pointer to list of matrix records second list of column headers also contains pointers to matrix records each non-zero matrix element stores pointers to its non-zero neighbors in the rowboth following and preceding it each non-zero