This is an old revision of the document!
Corning Community College
CSCS2320 Data Structures
~~TOC~~
This section will document any updates applied to the project since original release:
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:
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:
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$