Project: SLN0

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:

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.

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;

And that would produce the following result:

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.

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):

tmp -> info = 57

That would leave us with the following image:

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

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

start -> after = tmp2

(as tmp was also pointing to the same node, we could just as easily have said “tmp → after = 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:

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

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 -> after = start

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:

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

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:

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:

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:

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:

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:

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.

Last week's project used an array to perform various transactions on a collection of items. What was the array will become a set of nodes, linked together in the fashion described in this project.

We used nodes in a productive manner- under the guise of a list, which is merely a way of organizing nodes.

It is important to note, with a list, that any anchoring variables (such as start) MUST point to their respective part of the list. If a change results in the invalidation or alteration of that variable's position, it MUST be adjusted so that it can retain its value as a list marker.

Temporary variables come and go.. feel free to make use of them as needed; just make sure you don't overcomplicate a problem by using too many.

For this project, I would like for you to write me the necessary pseudocode and draw the necessary step-by-step pictures to correctly accomplish the following. The pseudocode should go in a file called sln0.text to be submitted, and pictures drawn can be submitted electronically (even uploaded to lab46 and submitted using the submit tool).

Do this for the following:

Let's say we had a list generated with the following:

start = tmp = mknode(2)
tmp -> after = mknode(4)
tmp = tmp -> after
start -> after -> after = mknode(8)
tmp = tmp -> after
tmp -> after = mknode(16)

What does the resulting list look like? Where are the start and tmp variables pointing?

Write the code and draw the pictures to show the steps necessary for putting a new node (containing a 6) BEFORE the node containing an 8

Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for putting a new node (containing a 0) BEFORE the node containing a 2

Assuming you do not know the composition of the list, write the code to display the list contents from start to end (end is defined as when after becomes NULL)

Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for putting a new node (containing a 1) after the node containing a 0

Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for taking the node containing 6 and disconnecting it from the list. You may deallocate the node once properly disconnected.

Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for putting a new node (containing a 12) after the node containing an 8

Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for taking the existing list (as referenced by start), and make a copy of that list, where the copied list is referenced by a variable called start2.

Assuming you do not know the composition of the list, write the code and draw the pictures to show the steps necessary for taking the node containing 0 (from the copied list) and disconnecting it from that list. You may deallocate the node once properly disconnected.

Draw pictures showing the final states of both lists, with respective variables pointing to nodes (or NULL, as appropriate).

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 list.txt):

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

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