Appendix: Data Structures in C

Diomidis Spinellis
Department of Management Science and Technology
Athens University of Economics and Business
Athens, Greece


Asymmetric Bounds

#define MAX_ADS 5
struct dr {            /* accumulated advertisements */
    n_long  dr_pref;   /* preference adjusted by metric */
} *cur_drp, drs[MAX_ADS];
    struct dr *drp;
    for (drp = drs; drp < &drs[MAX_ADS]; drp++) {
        drp->dr_recv_pref = 0;
        drp->dr_life = 0;
In the code above drs (the lower bound) is the first element of the array; drs[MAX_ADS] (the upper bound) the first element outside the array.

When using asymmetric bounds:






Hash Tables


Singly Linked Lists

Singly linked list

Doubly Linked Lists

Doubly linked list

Circular Linked Lists

Circular linked list


Binary tree

Further Reading

Exercises and Discussion Topics

  1. Select a large software system, locate where arrays are used, and categorize their uses.
  2. Fixed-length arrays notoriously impose arbitrary limits to program elements. Locate 20 instances of such limits in existing code and check whether these are documented in the respective system's documentation.
  3. For the RDBMS of your choice locate documentation regarding cursors. Compare the functionality offered by cursors to the functionality offered by pointers to structures.
  4. A number of linear algebra and matrix libraries are available on the Web in open-source form. Download two such packages and identify how matrices are stored.
  5. Examine the stack operations performed on implementations based on explicit code. Identify those operations that do not fit into the model we described. Propose function names and code for implementing them.
  6. Locate code where explicit control structures can be substituted by an array lookup mechanism. Explain how the code would be implemented.
  7. Do you envisage any difficulties in implementing a hash-based map as an abstract data type? Suggest a way to overcome them.
  8. Locate instances in the course's reference source code where sets are being used. Suggest other implementation strategies for each particular problem. Comment on whether a set data-type is used partly, because it is easy to create an efficient implementation for it.
  9. Locate five instances of singly and doubly-linked lists in the course's reference source code and explain the function they perform.
  10. Draw a binary tree containing the host names in your email address book. Add the names in a random order; not alphabetically. Systematically walk through the tree to derive a sorted listing of the host names. Construct a new tree adding the host names in the order they appear in the listing you constructed. Comment on the efficiency of searching data in the two trees.