The purpose of a struct that people usually discuss is simply grouping heterogeneous types into a single collection, which may then be referred to collectively.

Another, and at least as important, function of a struct, which isn't usually discussed in the context of procedural languages like C or Pascal, but is a central topic in Object Based languages like Ada, or Object Oriented languages like C++ or Smalltalk or Python, is to create abstract data types (ADT's). C can do ADT's pretty well really, except for the information hiding part (which it has in common with Python, in a sense), and also C doesn't do inheritance well (C++, Smalltalk and Python do - this being the primary distinction between a mere "Object Based" language like Ada, and these "Object Oriented" languages).

The point of an ADT is to, for example, have a single API for a kind of data and the operations performed on that data, but implementing the data representation and operations in different ways, but with different tradeoffs - hence insulating the dependent code from being heavily impacted when the data representation needs to change.

One of the classic examples of why you might want an ADT, is implementing a stack. A stack is where you put items in at one end of a "list" (in the generic sense, not the Computer Science sense), and pull items back out from the same end, just like with a pile of plates at Souplantation.

Two common data representations that might be used internally by a stack ADT (abstract data type) would be an array, or a linked list.

The array implementation of a stack is nice because it's fast, and because it has low memory requirements when the stack is full, but it'll tend to lead to messiness if the array fills up (which C can get around with realloc, but a language like Pascal (the Niklaus Wirth definition - Borland likely extended for this) doesn't have much in the way of an equivalent).

The linked list implementation of a stack is nice because it has no fixed limit on how large the stack can grow (other than available memory, at least on non-segmented architectures), but it'll tend to be a little bit slower, and it'll use more memory than an array implementation when the two stack implementations hold a number of elements near the capacity of the array implementation.

If you implement both of these with identical API's, then you can very quickly and easily change your programs from using the plusses and minuses of one implementation (array) to the other (linked list - or vice versa).

As a further example of an abstract type, say you have a program that uses a singly-linked list (linked only forward, but not back again), and suddenly you find that the changing needs of the program require you to be able to quickly start at the end of the list, and work backward. You could easily approach this with a recursive algorithm (if you aren't worried about the CPU and memory requirements), but often a slight change in data representation is better.

In such a case, you have pretty much three choices:

  1. If you were using a library of C functions that implements both singly-linked lists, as well as doubly-linked lists (forward and back), and the doubly-linked list API is already a superset of the singly-linked list API, then you can just switch to the doubly-linked list implementation, and all of your existing code that required only a singly-linked list should continue functioning just fine (so long as they do not violate the ADT definition by reaching inside the struct's inappropriately), so you can dive right into adding the new functionality, rather rearranging the old singly-linked code first.

  2. If you are implementing your own linked list functions (seldom a good idea anymore, but a lot of CS students are required to do it, since it's a good example of ADT's/Objects), and you've carefully abstracted your singly-linked list implementation, then you can just add another ADT (possibly via inheritance in a fully object oriented language like C++ or Smalltalk or Python, but not C or Ada) that does doubly linked lists, and other than the (perhaps partially) new ADT and the new code for doubly-linked lists, your existing code doesn't need to be modified much, if at all.

  3. If you weren't abstracting your code well, then you could easily end up doing a near-complete rewrite due to what may actually be a relatively small change in the program's requirements.
So by having this typedef/struct with a single element, if there is a well defined set of functions that can look inside the typedef/struct (and only they are allowed to do it - IE the inspection/changing of the struct isn't scattered throughout your program) that opens the door to easy changes - like switching to a doubly-linked list, or adding a field that keeps a count of the members in the list, or even switching to an entirely different kind of data structure behind the scenes, while the rest of your code happily takes an afternoon nap.

Put another way, if you have poorly abstracted code, when you need to change a data representation, you can easily get a sort of "ripple effect", where changes in the code start in one small place, and kind of "ripple outward" (a bit like a single drop into a pool of water) into ever further parts of the code. But if things are well abstracted, then most of the time (some would argue all of the time), the "ripples of change" stop at the ADT boundaries, which can be quite a time-saver in the long run.

Hits: 4751
Timestamp: 2024-11-24 22:07:28 PST

Back to Dan's tech tidbits

You can e-mail the author with questions or comments: