This section will document any updates applied to the project since original release:

• revision #: <description> (DATESTAMP)

In this project, we start conceptualizing aspects of the program we wrote in last week's project (with the arrays), and start looking at each unit of information as an arbitrary node unit, connected to its immediate proceeding neighbor via a link.

This gets us into a central theme of the course which we'll be running with from now until the end- the idea of a linked nodes, or in our current case: singly-linked nodes.

For this project, we will explore a variation of C-like pseudo-code and drawings.

The pseudocode can easily be in a file you can submit using the submit tool.

As for the drawings- I will take submission of these as actually handing me sheets of paper; or, you may digitize your work and submit it in an archive along with the pseudocode.

Please, do NOT put any drawings or pseudocode related to your solutions to this project's problems on your Opus. I don't want it to be a temptation to others.

A node is an arbitrary unit of information we will be using this semester in our study of algorithms and organization of data. We will be creating it, and then using it much as we would any of the existing data types and variables we make use of in C.

For starters, our “node” will contain two items:

• a data field called info
• an arrow pointing to the next neighboring node to our immediate right, called after

If we do not have another node to point an arrow at, we'll want to point it at a specific value indicating nothing. In our case, that value is NULL (must be all caps).

As such, if we were to have a solitary node containing a 17, and pointing at nothing (NULL), it could be drawn as follows:

PICTURE OF NODE

Now, it is important to keep tabs on our nodes, in some form. A node can exist, but if we have no means of getting to it, it is lost in space, unavailable to us.

For this reason, we often assign names to some of our nodes. Especially as a means of identifying the starting node in a group of nodes.

If we were planning to have a group of nodes (we might call it a list), we'd more than likely want (at least) to identify the first node in that group by a name, say: start

So here is a picture of what that same node would look like, while also associating a variable known as start with it.

PICTURE OF NAMED NODE

We may also wish to assign additional names to certain nodes, to be used in on-going transactions on the group. As these variables are destined to change frequently, we may think of them more as “temporary” variables, and we'd assign a name fitting of such a role, say: tmp

To assign a tmp variable to point at our existing node (which can be referenced by our start variable), we'd use the following pseudocode:

tmp = start;
</code
 
And that would produce the following result:
 
**IMAGE of node with tmp and start**
 
Note that **tmp** does **NOT** point to **start**, which points to the node-- instead, **tmp** points to what **start** points to. This is very important.
 
===altering the contents of a node===
 
To change the value in the node (to, say 57), we'd use the following pseudocode logic (note that, in order to access the node, it needs to have a name):
 
<code c>
tmp -> info = 57

That would leave us with the following image:

IMAGE of updated node

If we had a second node, tmp2, containing a 37 and pointing at nothing, we'd have a scenario like this:

IMAGE of two nodes

If we wanted start's node to point to tmp2's node, we'd want to do something like this:

start -> next = tmp2

(as tmp was also pointing to the same node, we could just as easily have said “tmp → next = tmp2”, and we may have wanted to use that approach instead, as the idea behind start is to use it as an anchoring reference point only).

The result of that assignment results in the following:

IMAGE of two connected nodes

What if we were to add a third node to our scenario (containing a 48):

IMAGE of our nodes

We have our existing two connected nodes, and our new node, currently identified by tmp3.

Now, what if we wanted tmp3 to be the left-most node in our group? How would we connect it?

Like this:

tmp3 -> next = start

IMAGE of result

BUT: the intention of having start is to always have it pointing at the FIRST node in our list. So, as a result of that assignment, we need to re-assign start.

We do so as follows:

start = tmp3

That results in the following:

IMAGE of list of 3 nodes

Note that, at any point, the tmp/tmp2/tmp3 variables can go away, yet we'd still have control over our nodes (via start):

tmp = tmp2 = tmp3 = NULL

IMAGE of 3 nodes

If it hasn't become obvious yet, drawing pictures like this (especially in a step-by-step manner) will be invaluable in aiding you through both debugging and solving these various tasks you'll face this semester.

To create a node, in pseudo-code, we call a special “mknode()” function. As a parameter, it takes the value we wish to initially be present in the node (the info field).

mknode() returns the location of this new node, so in order to prevent it from getting lost, we need to assign a variable to it (much as our start, tmp, tmp2, tmp3 variables do).

In this case, let us assign our variable tmp to this newly created node containing a 12:

tmp = mknode(12)

The picture drawn should resemble:

IMAGE

We also have the ability to copy an existing node. This will duplicate the node and its contents (two copies).

If we wanted tmp2 to be a copy of tmp, we'd say:

tmp2 = cpnode(tmp)

Which would give us:

IMAGE

Note that assigning a variable to an existing node is NOT the same as copying. If we were to say:

tmp3 = tmp

Does this create another copy? NO. It merely creates a scenario where two variables reference one node:

IMAGE

We also have the ability to remove (de-allocate) a node. If we are all done with it, we should be sure we remove it so it is no longer using any resources.

This will de-allocate the node referenced by tmp2:

tmp2 = rmnode(tmp2)

The result will be this:

IMAGE

We can run into interesting situations when we remove a node that has multiple variables pointing at it. For instance– tmp and tmp3. If we were to say:

tmp3 = rmnode(tmp3)

We'd potentially end up with the following scenario:

IMAGE

That's because when we de-allocate, it doesn't immediately go away, but is merely marked for removal. We should not rely on that data being there, even though it may still be accessible.

This is an example of what may result in undefined behavior, and could certainly lead to unexpected run-time errors, typically of the form segmentation fault.

So, in the case of nodes with multiple variable references, if we care about those variables, we should take care to properly set them.

To be successful in this project, the following criteria must be met:

• Project must be submit on time, by the posted deadline.
  • Late submissions will lose 25% credit per day, with the submission window closing on the 4th day following the deadline.
• All code must compile cleanly (no warnings or errors)
  • all requested functions must be implemented in the related library or program
  • all requested functionality must conform to stated requirements (either on this project page or in comment banner in source code files themselves).
• Executed programs must display in a manner similar to provided output
  • output formatted, where applicable, must match that of project requirements
• Processing must be correct based on input given and output requested
• Output, if applicable, must be correct based on values input
• Code must be nicely and consistently indented (you may use the indent tool)
• Code must be commented
  • Any “to be implemented” comments MUST be removed
    • these “to be implemented” comments, if still present at evaluation time, will result in points being deducted.
  • Sufficient comments explaining the point of provided logic MUST be present
• Track/version the source code in your lab46 repository
• Submit a copy of your source code to me using the submit tool (make submit will do this) by the deadline.

Let's say you have completed work on the project, and are ready to submit, you would do the following (assuming you have a program called arraylist.c):

lab46:~/src/data/sln0$ submit data sln0 arraylist.c
Submitting data project "sln0":
    -> arraylist.c(OK) 

SUCCESSFULLY SUBMITTED
lab46:~/src/data/sln0$