Reading: Linked Lists

Reading: Examples/LinkedLists.

Please submit a question by 9 p.m. on Sunday, 24 April 2011.

There are so many files, what does this whole thing do??

There are a few implementations of lists and tests of those implementations.

I read the files through and I have no idea what the purpose of these is. I'm also hoping you could re-explain flags in makefiles. Would it be possible to write one file for utests for a large project and then use the flags to determine which ones are run?"

I will try to rexplain the key points.

Can you represent an element in a list the way you can an element in an array (eg. strings[5])? In other words, does an item stored in a list have an index?

Since lists are not a built-in type, you can't use the special array syntax for them. Items stored in lists do have indices relative to the start of the list, but you can iterate through them until you get to the element that you want.

In expt.h and utest.h, we are able to write files that just define things for other procedures? If so, how does that work?

They work the same way as any header (or included file) works. When you include it, the code gets shoved into your file. If the included file defines a macro, the including file gets to use those macros.

Why is it expt.h? Can we use this everywhere else? I don't see it being used anywhere else.

The intent is that we can use the functions anywhere.

What is stderr? It appears multiple times through fprintf's

What is stderr?

Where we send error messages. By using stderr rather than stdout, we distinguish error message (stdderr) from regular program output (stdout).

Why do you use fprintf instead of printf in the code for PRINT_STR?

define PRINT_STR(VAR) fprintf (stderr, VAR_PREFIX ""%s = %s\n"", #VAR, VAR)

Because I want the output to go to stderr (for error messages) rather than stdout for regular output.

What are the backslashes for in the #define PRINT_LIST(LIST) code?

They let a macro contine onto multiple lies.

What does -> do again?

Gives us one field of a structure. (We use . when we have the actual structure and -> when we have a pointer to the structure.

What does the double arrow, as in return lst->head->data; do?

If lst->head is a pointer to a struct, and that struct contains a field called data, this gives you the field. (Basically, it's getting a field of a field.)

Is it right to say that each element in a list is stored in a different place in memory, and we can only get from one element to the next using pointers?

Yes, that is correct.

I am curious as to what you meant by Real C in this line of list1.c:

return (um != NULL); // Real C: return um;

Real C programmers don't do unnecessary tests. um != NULL returns 0 when um is NULL (aka 0) and a non-zero number when um is not NULL (aka a non-zero number).

Why are vectors not as mutable as lists are? it appears as though lists can be easily changed, which seems nice.

It's a speed/mutability tradeoff. Finding the nth element of a vector is fast. Finding the nth elemtn of a list is slow.

In the code for cons in node.c, I don't understand why it creates a newlst and immediately tests to see if it's NULL - wouldnt it always be NULL/filled with random characters that aren't important?

NULL means that it effectively points nowhere. The malloc procedure is supposed to allocate new memory. But sometimes you run out of memory on the computer. In those cases, malloc returns NULL.

What does malloc do?

Allocates memory. We use it when we want to build something new in memory, such as a new cons cell.

What exactly does free do? It's fairly clear that it deletes things but how is this accomplished? Does it just allow that particular area of memory that a pointer points to, to be rewritten and set the pointer to null? Or am I missing the point (haha)?

Wow, that was even less funny than my typical joke. Essentially, the memory allocator has a list of available chunks of memory. When you malloc something, it gives you one of those chunks (or a piece of one of those chunks). When you free something, it adds it to the list of availble chunks.

BLOCK

What's the use of BLOCK?

This is the comment and definition of BLOCK:

// Turn CODE into a block that you can legally nest.
#define BLOCK(CODE) do { CODE } while (0)

What does this mean/what is it's purpose? I suppose if you want to have multiple statements executed by an if statement, but isn't that what curly brackets are for? ({} is 2 characters, BLOCK is 5 (you need to hold down the shift key for both))

We use BLOCK when defining macros that have more than one statement. Let's think about the C code you might write.

  for (i = 0; i < 10; i++)
    WHATEVER (i);

However, if you simply put braces around the code in the macro definition, you'll get an expansion that looks like

  for (i = 0; i < 10; i++)
    {
      ...
    };

You'll notice that there's a misplaced semicolon there. The BLOCK operation lets us avoid the misplaced semicolon.

What does BLOCK(CODE) do? I don't really understand what Turn CODE into a block that you can legally nest means.

The example above might be explanatory. The idea is that we want to be able to put a macro anywhere we might put a function call, including in the body of a loop or conditional (nesting). The BLOCK wraps the sequence of operations so that they can be treated like a single statement.

Questions on Code for the Future

Sam accidentally left list1.c and list2.c in the directory. Those are for discussion over the next few days. Since some of you saw that code, you asked questions on it. I'll answer some of them.

What is the functional difference between a linked list and a doubly linked list?

Linked lists and doubly linked lists provide the same interface. Doubly linked lists provide a more efficient implementation of some operations.

In list1.c, they use static. What is static?

The static modifier is used for variables and functions that we want to keep local to a file. That is, they should be accessible by the functions within the file, but not by functions outside of the file.

What does -> mean when it is being used? For example, it is used in list2.c:

   if (lst->tail == NULL)
    return NULL;

It's the operation for extracting an element of a structure (or a pointer to a structure).

What are the differences between list_append and np_append?

Both append to the end of a list. They deal with two different representations of lists.

Tangential Questions

All of our assignments lately have concerned strings. Is there a way to find the length of an array that is not a string? An array of numbers doesn't have a '\0' right? Doesn't this mean that most of the functions we've made for strings can't be made for arrays of numbers? What if we want to reverse an array of numbers? It seems impossible that there isn't a good way to do things with arrays that aren't strings. What's the secret?

There is essential no way to find the length of an array that is passed as a parameter to a function. That's why we always pass along the length of the array.

However, at the point that the array is declared, we can easily find the length by taking the size of the array and dividing by the size of the individual element.

  char *strings[] = { "Hello", "Goodbye", "Dag" };
  int num_strings = sizeof(strings) / sizeof(char *);

Questions Sam Did Not, Will Not, or Can Not Answer Well

I'm confused about how these are Linked Lists versus normally structured lists.

I'm confused by what you mean by normally structured lists. We haven't done lists in C before this, so there should not be a sense of normal. These lists have links between the elements (just like the implicit links in Scheme lists). It turns out that there are other ways to design list-like structures.

I can see in list-expt.c, it uses the EXPERIMENT function from the expt.h, so when it says give a command, does it mean like anything from making a list or just adding things?

Another question I have trouble parsing. The idea of the EXPERIMENT macro is that it prints out its parameter and then executes it. Such printing makes it easier to trace what the program is doing.

In node.c, EXPERIMENT is redefined in the head. Although the library it is called in is also defined, why would we need to call an ifdef statement for that particular function?

I'm not quite sure what you're asking. No where in node.c is EXPERIMENT defined. There is a check to see whether the EXPERIMENTS flag (slightly different) is defined. The idea is that when we compile the code with the EXPERIMENTS flag, we get the version of node.c intended for doing a simple experiment.

What does the code in prob7.c do?

Ah! That's for your to figure out in the lab.