CURRENT ISSUE Contests
Feature Article
|
|
Issue #212 March 2008
LESSONS FROM THE TRENCHES
Do You Want to Do a Design?
Linked Lists
by George Martin
Start | Design Challenge | Database Design | Use A Linked List | Design Implementation | Code Review | Sources & PDF
USE A LINKED LIST
Wikipedia describes a linked list as “one of the fundamental data structures, and can be used to implement other data structures. It consists of a sequence of nodes, each containing arbitrary data fields and one or two references (‘links’) pointing to the next and/or previous nodes.”[1] Stanford University has a great tutorial on the subject and a good set of problems with C code solutions. Refer to the Resources section of this article for more information.
We’re going to use a single linked list. Each node will have a number to dial and a linkage pointing to the next number. You will typically see malloc() used in Linked list C examples for claiming memory for the lists. Because we’re dealing with an embedded system, we’re not going to use malloc() to allocate memory for our usage. We’re just going to assign a sufficiently large amount of memory to hold our data structures. If we need more in the future, it’s just one #define to change and recompile. And remember that this memory is EEPROM and it’s valuable, so we’re trying to use it wisely.
First, we’ll build an array for each of the call out groups that contain the first number to try to call. If no number is entered, we’ll use a –1 as an indication of that condition. Because we have only 10 (from the first statement of the problem) or 30 (from the second request) possible numbers to call, we can use 8-bit entities for this array. Table 1 shows the array contents.
Call out group |
First number to call |
|---|---|
0 |
–1 (empty) |
1 |
1 |
2 |
3 |
3 |
–1 (empty) |
— |
— |
29 |
–1 (empty) |
| Table 1—This is an array of the first numbers to try to call. An entry of –1 indicated an empty number. Remember the array indexing in C starts at 0. | |
INT8 CallOutGroup[MAX_GROUPS];
Next, we’ll build a structure containing the digits to dial and a linkage to the next possible number (in this structure) to try to dial. And again a –1 will indicate we’ve come to the end of the numbers to try (see Table 2).
Index |
DialNumb [MAX_DIGITS] |
NextNumb |
|---|---|---|
0 |
–1 (empty) |
–1 (empty) |
1 |
1.8005551212 |
2 |
2 |
1.8005551111 |
3 |
3 |
1.8005552222 |
–1 (empty) |
4 |
–1 (empty) |
–1 (empty) |
— |
— |
— |
39 |
–1 (empty) |
–1 (empty) |
| Table 2—This is the linked list for our call out sequences. –1 indicates an empty entry. | ||
Struct CALL_OUT_NUMBERS { // define
// the structure
INT8 DialNumb[MAX_DIGITS];
INT8 NextNumb;
};
struct CallOutNumbs[MAX_NUMBERS]; // reserve memory
Look at Tables 1 and 2. And remember C arrays start at 0. The first entry DialNumber[0] is empty (–1). The second number 1-800-555-1212 is located at DialNumber[1]. If that number is dialed and we get no response, we should try the number DialNumber[2]. If that number (1-800-555-1111) is dialed and we get no response, we should dial the number DialNumber[3]. If that number (1-800-555-2222) is dialed and we get no response, that is the end of the sequence of numbers and we should start the calling out from the first number.
Hopefully, you can see that an event starts the process by looking up the first number using the CallOutGroup[] array. From then on, the CallOutNumbs[] structure defines the number and the next number if there is one. This is a classic forward-linked list. And you can also see that it is efficient in memory usage. More callout events linearly increase the size of the CallOutGroup[] array. And more numbers to call linearly increase the size of the CallOutNumbs[] structure.
