0.1 Pointers, memory, and structs

CSCI2520 does not require you to love C as a language, but it does require you to read C examples accurately. The course uses C because pointers, heap allocation, and low-level data layout make data-structure behavior visible in a way that high-level languages often hide.

This note therefore has one narrow purpose: make the core C toolkit readable enough that later stack, queue, and hash-table code does not feel like magic.

Motivation

The local tutorial material says the course does not emphasize any one programming language. That is true at the assessment level. But the lecture and tutorial slides still rely on C examples to explain:

• what a pointer stores,
• how a node is allocated,
• how a structure groups fields,
• why ADT implementations hide representation details.

If you misread any of those, you do not merely get a syntax error. You lose the ability to see what the data structure is doing in memory.

Pointers store addresses, not values

The tutorial review distinguishes two operators:

• &x means “the address of x”;
• *p means “the value stored at the address inside p”.

Those two ideas must not be blurred together. A pointer is not the same thing as the object it points to.

int firstvalue = 5, secondvalue = 15;
int *p1, *p2;

p1 = &firstvalue;
p2 = &secondvalue;
*p1 = 10;
*p2 = *p1;
p1 = p2;
*p1 = 20;

int firstvalue = ...; int secondvalue = ...; int *p1, *p2;

The key discipline is to separate two questions:

• what address is each pointer holding?
• what value lives at that address right now?

Dereferencing changes the pointed-to object

Once a pointer has been assigned a valid address, dereferencing it lets you read or modify the object stored there.

int x = 7;
int *p = &x;
*p = 12;

After the final line, x is 12. The statement *p = 12 does not create a new integer. It writes through the pointer into the existing object.

Local objects and dynamically allocated objects have different lifetimes

An address is useful only while the object at that address is still alive. A local object declared inside a block normally has automatic storage duration: its lifetime ends when execution leaves that block. Returning its address therefore creates a pointer that remembers a location but no longer designates a live object.

int *bad_address(void) {
   int local = 7;
   return &local;             /* dangling as soon as the function returns */
}

Storage obtained from malloc has allocated storage duration. It remains allocated across function returns until the program passes that allocation to free. This longer lifetime is why linked structures can keep nodes created by earlier operations. It is not permission to use the node forever: after free(x), x and every alias of x are dangling pointers. Scope answers “where can this pointer variable be named?”; lifetime answers “does the pointed- to object still exist?” These are different questions.

malloc allocates storage on the heap

The tutorial review also emphasizes malloc, because many data structures create nodes dynamically rather than in fixed-size arrays.

In C, the usual pattern is:

struct node *x = malloc(sizeof *x);
if (x == NULL) {
   /* report or propagate allocation failure */
}

On the success path, x points to newly allocated memory large enough to store one struct node. Writing sizeof *x keeps the allocation tied to the declared pointer type without repeating that type name. In C, <stdlib.h> declares malloc, and its returned void * need not be cast.

Two follow-up rules matter immediately:

• check x != NULL before any dereference;
• initialize every field before code relies on its value;
• state which part of the program owns the node and must eventually free it.

Even when a short classroom example omits free, a real implementation cannot ignore ownership forever.

Ownership gives allocation a complete story

For each allocation, ask three questions: who creates it, which pointers may borrow access to it, and who frees it? The owner is responsible for ending the allocation exactly once. A borrowed pointer may inspect or update the live object under the owner's rules, but it must not outlive the object or free it without transferring ownership.

If the last usable pointer to a live allocation is overwritten, the allocation becomes unreachable and is leaked. If code uses an alias after the owner frees the allocation, the alias is dangling. If two paths both believe they own the same node, a double free can result. C does not prevent these mistakes, so an ADT implementation must make the ownership contract visible in its operations.

typedef shortens repeated types

The tutorial review also includes typedef, because data-structure interfaces often hide long pointer types behind short aliases.

typedef struct node *nodePtr;
typedef int stackElementT;

This does not create a new runtime object. It creates a new type name for the compiler and for human readers.

The gain is clarity:

• function prototypes become shorter,
• interface files become easier to scan,
• the ADT boundary becomes more readable.

When the course writes stackADT, the name itself is part of the abstraction. It tells you that the client should think in terms of “a stack object,” not “a pointer to some particular structure layout.”

The alias alone does not make a representation private. True representation hiding comes from declaring an incomplete structure type in the interface and placing its field definition in the implementation file. typedef then gives clients a readable handle while preventing direct field access.

struct groups related fields into one record

For example:

struct node {
   int data;
   struct node *next;
};

This is the standard shape for a linked-list node. One field stores the current payload, and one field stores the address of the next node.

The definition is self-referential without containing an entire second node. While the compiler is still reading struct node, the tag can already be used to declare struct node *next, because every object pointer has a known size. Writing struct node next; instead would demand a complete node inside every node and would make the type's size impossible to finish.

For a node pointer p, p->next is shorthand for (*p).next. Updating that field changes an edge in the linked structure's memory graph. It does not move the nodes themselves; it changes which node can be reached next from p.

The point is not only syntactic grouping. A struct lets you model the exact pieces of state that an ADT implementation must preserve.

struct cellT {
   queueElementT element;
   struct cellT *next;
};

Theorem/Proposition

Proof sketch or proof idea

For the first proposition, dereferencing means accessing the object designated by a pointer. If no suitably typed live object is designated, there is no valid object on which C can perform that access; the behavior is undefined. Merely retaining the old numeric address after a block return or free does not extend the object's lifetime.

For the second proposition, view each node as a vertex and each pointer field as a directed edge. Overwriting the only edge to a still-needed sublist makes that sublist unreachable, while reading old->next after free(old) violates the first proposition. Saving the successor before freeing during dequeue, or linking a fresh node before advancing tail during enqueue, preserves a path from the ADT roots at every step. The empty and one-node cases require explicit root updates because their head and tail aliases coincide.

How this feeds directly into ADT design

The earlier C lecture and the ADT lecture fit together tightly.

• Pointers let one object refer to another.
• malloc lets nodes be created when the operation needs them.
• struct lets the implementation store several related fields together.
• typedef helps the interface hide representation details.

So when the course says an ADT should expose the “what” and hide the “how,” the language tools above are exactly what make that separation possible in C.

Common mistakes

Quick checks

A fuller struct trace

The student example is worth reading one level more slowly, because it combines pointer setup, struct field access, file input, and ownership in one short trace. A safety-complete version makes the success and cleanup boundaries explicit:

Sdata *p = malloc(sizeof *p);
if (p == NULL) return EXIT_FAILURE;

FILE *fp = fopen("example.txt", "r");
if (fp == NULL) {
   free(p);
   return EXIT_FAILURE;
}

int fields = fscanf(fp, "%49s %d %49s",
                    p->name, &p->age, p->address);
fclose(fp);
if (fields != 3) {
   free(p);
   return EXIT_FAILURE;
}

/* use the initialized record */
free(p);
p = NULL;

There are four separate questions hidden in those lines:

1. what object does p point to after malloc?
2. which buffers receive the strings read into p->name and p->address?
3. why does p->age need an address operator while the array fields do not?
4. after the input is done, which resources must still be released?

On a successful allocation, p designates one live Sdata object. The two array fields provide pointers to their first elements when passed to fscanf, whereas the integer conversion requires &p->age. The width limits protect 50-element arrays from oversized tokens, and the return value confirms that all three conversions succeeded. This format reads three whitespace-delimited tokens; it is not a parser for an address containing spaces. fclose releases the file resource and free ends the allocated object's lifetime. Reading the code this way turns isolated syntax into one ownership-and-state trace.

Summary

• A pointer records an address; dereferencing accesses the live object at that address, subject to type and access rules.
• Automatic local objects die when their block finishes, while dynamically allocated objects live until free; neither scope nor a remembered address extends an object's lifetime.
• Every allocation needs a checked failure path, initialized fields, a clear owner, and exactly one eventual release.
• A self-referential node stores links as pointers. Linked-structure operations are graph updates whose order must preserve reachability from the ADT roots.
• typedef improves interface vocabulary, while an incomplete type and a separate implementation are what actually hide a representation.

Exercises