Sparse array representation as a linked list

When implementing a sparse array using a linked list, the first step is to create a structure containing the following elements:

• Cell-stored data
• The logical position of the cell in the array
• References to the previous and next items

Each new structure is placed in the list so that the elements remain ordered by index in the array. Access to the array is made by clicking on the links.

For example, the following structure can be used as a carrier of a sparse array element in a spreadsheet:

  struct cell {
   char cell_name [9];  / * cell name, eg A1, B34 * /
   char formula [128];  / * information, for example, 10 / B2 * /
   struct cell * next;  / * pointer to the next entry * /
   struct cell * prior;  / * pointer to the previous entry * /
 };

The cell_name field contains the string corresponding to the cell name, for example, A1, B34 or Z19. The string field formula stores the formula (data) from the corresponding table cell.

A complete spreadsheet program would be too large ^[1] to use as an example. Instead, this chapter discusses key functions that provide sparse array implementation based on a linked list. It should be remembered that there are so many ways to implement a spreadsheet program. The functions and data structure shown here are just examples of working with sparse arrays.

The following global variables indicate the beginning and end of a linked list:

  struct cell * start = NULL;  / * first list item * /
 struct cell * last = NULL;  / * last list item * /

In most spreadsheets, when a formula is entered into a cell, a new element of a sparse array is created. If the spreadsheet is based on a linked list, this element is inserted into the list using a function similar to the dls_store () function in Chapter 22. Remember that the list is sorted by cell name; for example, A12 precedes A13, etc.

  / * Insert cells into an ordered list.  * /
 void dls_store (struct cell * i, / * pointer to the inserted cell * /
                struct cell ** start, 
                struct cell ** last) 
 {
   struct cell * old, * p;

   if (! * last) {/ * first item in the list * /
     i-> next = NULL;
     i-> prior = NULL;
     * last = i;
     * start = i;
     return;
   }

   p = * start;  / * start at the top of the list * /

   old = NULL;
   while (p) {
     if (strcmp (p-> cell_name, i-> cell_name) <0) {
       old = p;
       p = p-> next;
     }
     else { 
       if (p-> prior) {/ * is an element from the middle * /
         p-> prior-> next = i;
         i-> next = p;
         i-> prior = p-> prior;
         p-> prior = i;
         return;
       }
       i-> next = p;  / * new first item * /
       i-> prior = NULL;
       p-> prior = i;
       * start = i;
       return;
     }
   }
   old-> next = i;  / * insert at the end * /
   i-> next = NULL;
   i-> prior = old;
   * last = i;
   return;
 }

In the above function, the parameter i is a pointer to a new inserted cell. The parameters start and last are respectively pointers to pointers to the beginning and end of the list.

The following deletecell () function deletes a cell from the list whose name is passed as a parameter.

  void deletecell (char * cell_name,
             struct cell ** start,
             struct cell ** last)
 {
   struct cell * info;

   info = find (cell_name, * start);
   if (info) {
     if (* start == info) {
       * start = info-> next;
       if (* start) (* start) -> prior = NULL;
       else * last = NULL;
     }
     else {
       if (info-> prior) info-> prior-> next = info-> next;
       if (info! = * last)
           info-> next-> prior = info-> prior;
       else
         * last = info-> prior;
     }
     free (info);  / * free up system memory * /
   }
 }

The last function you need to implement a sparse array based on a linked list is the find () function that finds the specified cell. To find a cell of this function, you have to perform a linear search, but, as shown in Chapter 21, the average number of comparisons in a linear search is n / 2, where n is the number of items in the list. The following is the text of the find () function:

  struct cell * find (char * cell_name, struct cell * start)
 {
   struct cell * info;

   info = start;
   while (info) {
     if (! strcmp (cell_name, info-> cell_name)) return info;
     info = info-> next;  / * go to the next cell * /
   }
   printf ("Cell not found. \ n");
   return NULL;  / * search failed * /
 }

Analysis of the method of representation in the form of a linked list

The principal advantage of the method of implementing a sparse array using a linked list is that it allows efficient use of memory - space is allocated only for those elements of the array that actually contain information. In addition, it is easy to implement. However, this method has one major drawback: it uses linear search to access cells. Moreover, the cell saving procedure also uses a linear search to find the place to insert a new item. These problems can be solved by building a sparse array based on a binary tree, as shown below.

^[1] Many users joke that Microsoft itself does not know how much Excel it exactly takes. Of course, this is only a joke, but personally I sometimes think that it is 100% true.