This obviously is the first real week of class, and we're just getting set. Our first couple classes do not cover anything outrageous, but it is interesting all the same. We're all a little rusty from the summer, so the first thing we go over is pointers in general. Basically, we wrote a simple pointer creating program to show how they work and what syntax needs to be used. An & (ampersand) in front of a variable name will give the address in memory for that variable. An * (asterisk) will give the literal value saved in that variable. For example, if there are two int variable initialized, let's say a and b, and b is initialized as a pointer (done like so: “int *b”), then we can have b point to a so that b will hold the address value of a, and will consequently display the actual value held in a when called as *b in a printf (for example). Here's our short code, for reference:

#include<stdio.h>                                                                                                                                                       

//Note may conatin errors for example purposes

// **Pointer Operators** //
//
//      * -- dereferencing operator, "the value at [x]"
//      & -- address of

int main()
{
        int a; //stores 4 bytes for storage for a
        int *b; //pointer, stores the memory address
        char c;
        a=5;
        printf("a is: %d\n", a); 
        b=&a;
        printf("*b is %d\n", *b);
        *b=123; //This sends the value 123 to a.
        printf("b is 0x%x\n", b); // %x displays hexadecimal value
        printf("&b is 0x%x\n", &b);
        printf("*b is %d\n", *b);
        printf("a is %d\n", a); 
        return(0);
}

I'm glad we spent the time on this, actually, as I was still a bit shaky on pointers from C/C++ last semester, but this certainly clarified things.

This week is where things definitely got interesting. We started to learn about an actual data structure. This data structure is called a linked-list. Basically, it is like a super-array. It is created through the use of structs to create nodes.

//This is a node struct for a singly linked list.
//This can only go forward.

struct node {                                                                   
        int value;
        struct node *next;
};
typedef struct node Node;

We can fill the value variable within the node, and move on to another node to add a new value. A simple implementation of a singly linked list is this:

#include <stdio.h>
#include <stdlib.h>

struct node {
        int value;
        struct node *next;
};
typedef struct node Node;
                                                                                                                                                                        
int main()
{
        int input, input2, i = 0;
        Node *start, *tmp, *tmp2;

        start = tmp = NULL;

        printf("Enter a value (-1 to quit): ");
        scanf("%d", &input);

        do {

                if (input == -1) 
                        break;
    
                if (start == NULL)
                {
                        start = (Node *) malloc (sizeof(Node));
                        start -> value = input;
                        start -> next = NULL;
                        tmp = start;
                }
                else
                {
                        tmp -> next = (Node *) malloc (sizeof(Node));
                        tmp -> next -> value = input;
                        tmp -> next -> next = NULL;
                        tmp = tmp -> next;
                }
         printf("Enter a value (-1 to quit): ");
                scanf("%d", &input);

        } while (input != -1);

        tmp = start;

        while(tmp != NULL)
        {
                printf("[%d] value = %d\n", i, tmp -> value);
                tmp = tmp -> next;
                i++;
        }
        return(0);
}

All this program does is accept a numeric value, add it to the current node, adding numbers until a sentinel value is given, and then display the saved value of each node in order. It might seem like a lot of code now, because it may appear to be little more than a glorified array, but there is increased functionality to be had by using this data structure. Right now, all we can do is go forward in our list, but it looks like we'll be able to fix that with a little manipulation. Matt calls it the doubly linked list. In addition to the above code, we also wrote some code that let us insert a node at a give position and delete a node at a given position.

As promised, Matt showed us how to make a doubly linked list this week. More importantly, he showed us why a doubly linked list is important. As you may imagine, this gives us more control over what we can do with our linked list.

You see, a regular singly linked list looks like this:

[Node 0] → [Node 1] → [Node 2]

Where as a doubly linked list looks like this:

[Node 0] ⇔ [Node 1] ⇔ [Node 2]

In case the imagery was not clear: A singly linked list only connects nodes by whatever node comes after the current node. A doubly linked list connects nodes both ways, meaning it is connected by the node before and after it.

Making this happen is easy enough. One of the data fields within our nodes for the singly linked list was for a node called next. Each node had a next, as seen below:

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

To make a doubly linked list, all we need to do is do the following:

struct node {
    int value;
    struct node *next;
    struct node *prev;
};

Just make sure that every initialized node points to an appropriate next and previous node. Doing this lets us manipulate the list in different ways with more control. For example, we can list node values backwards.

This is the week where we really worked on the first project for the course that Matt provided for us. It's a pretty nice project to start with, I think. Simply put, we're supposed to make our own linked list library implementation. In this, we're supposed to have functions that create, append, insert, copy, delete, remove, display, and search for nodes. Once the library is completed, if it is included in a code, we should be able to call these functions to work as we want.

A pointer “points” to a memory location. It represents the data type and address of the variable that it is pointing to.

[Variable] = [Variable's value]

[Pointer to variable] = [Variable's address]

The dereferencing operator (which is the asterisk, *) has to do with pointers. When used, it refers to the literal value of the thing being pointed to with the pointer.

Say that “a” is our variable and is equal to 5, and “*b” is our pointer. When we have the pointer refer to our variable, and then print out the value contained in *b, one will see that the value of a is output. This is what the dereferencing operator does.

This is another pointer operator. This operator refers to the location in memory of a variable.

Suppose variable a is stored in memory location 1 (this wouldn't be so simple in an actual program, but for the sake of a simple example, this is what is being used), and there is a pointer *b. If we wanted to point *b to a, we would have to set b equal to &a (b=&a;), as this would set the value at b to the memory address of a.

A linked list is a data structure that is a series of nodes in a specific order. Each node contains various values. Typically, it holds a value for the nodes surrounding it, making it a “linked list,” and a general value to be held for various uses. Linked lists are created using structs.

A singly linked list is a linked list that only is linked forward. That is to say that each node only contains a general value and a value referencing the node immediately following it.

[Node 0] → [Node 1] → [Node 2]

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

A doubly linked list is a linked list that has nodes that are connected to the nodes immediately preceding and proceeding it. This means each node contains data that references the nodes before and after it.

[Node 0] ⇔ [Node 1] ⇔ [Node 2]

struct node {
    int value;
    struct node *next;
    struct node *prev;
};

A struct is a record type that consists of a set of member objects that make up one object. Instances of a struct can be initialized, and each member object of the instance of the struct can be filled uniquely.

An object file is typically one part of an overall code that is split up by function, each function being put in to its own object code. A compiler takes each piece of object code along with the corresponding given header file to make the executable file. This makes maintaining code or working on a program in groups easier.

Header files are used to declare variables, functions, classes, etc. in a universal scope so that all programs that use the header file can access these globally declared things. Obviously, it must be included at the beginning of a program, hence the name.

malloc is a function declared in the stdlib.h library. Using malloc allows you allocate a given amount of space for an object. Example:

start = (Node *) malloc (sizeof(Node));
 
/*
From the linked list implementation-- 
this gives the node "start" the size of Node 
as it is defined in the program from which this is excerpted.
*/

sizeof is a function defined in the stdio.h library. It determines the size of a given argument data type in bytes. This is useful when allocating memory using malloc.

The free function deallocates memory previously allocated using functions like malloc, so that it may be used again for allocation. It is good practice to use so that segmentation faults are avoided. For example, if you allocated memory to variable “bob” using malloc, and you are done using that memory location at a certain point in your program, all you would have to do to deallocate it is “free(bob);”

Given that the course is all about the various data structures, it should not be out of the realm of expectation for a student at this stage to be able to create and use at least one type of data structure in a program.

To achieve this objective, I will create a program that implements a singly linked list. Each node in the list should hold a value and data that refers to the node next on the list. To observe whether or not the list of nodes is properly linked, the nodes should be output in order.

The program compiles. It accepts values in new nodes until a sentinel value is given. It prints the values of each node in order of node creation.

I feel as though I have a basic grasp of what a data structure is, and that I can effectively use a data structure in a program in a constructive manner. This knowledge will definitely allow me to complete future course objectives effectively as well.

Do I need to assign a set size to an array when I initialize it? What happens when I set the size of the array to a variable that has only been declared and not yet initialized to any value, and then try to fill the array using scanf()?

Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment.

Based on what you've read with respect to your original posed question, what do you think will be the result of your experiment (ie an educated guess based on the facts known). This is done before actually performing the experiment.

State your rationale.

How are you going to test your hypothesis? What is the structure of your experiment?

Perform your experiment, and collect/document the results here.

Based on the data collected:

• was your hypothesis correct?
• was your hypothesis not applicable?
• is there more going on than you originally thought? (shortcomings in hypothesis)
• what shortcomings might there be in your experiment?
• what shortcomings might there be in your data?

What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made.

What is the question you'd like to pose for experimentation? State it here.

Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment.

Based on what you've read with respect to your original posed question, what do you think will be the result of your experiment (ie an educated guess based on the facts known). This is done before actually performing the experiment.

State your rationale.

How are you going to test your hypothesis? What is the structure of your experiment?

Perform your experiment, and collect/document the results here.

Based on the data collected:

• was your hypothesis correct?
• was your hypothesis not applicable?
• is there more going on than you originally thought? (shortcomings in hypothesis)
• what shortcomings might there be in your experiment?
• what shortcomings might there be in your data?

What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made.

What is the question you'd like to pose for experimentation? State it here.

Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment.

Based on what you've read with respect to your original posed question, what do you think will be the result of your experiment (ie an educated guess based on the facts known). This is done before actually performing the experiment.

State your rationale.

How are you going to test your hypothesis? What is the structure of your experiment?

Perform your experiment, and collect/document the results here.

Based on the data collected:

• was your hypothesis correct?
• was your hypothesis not applicable?
• is there more going on than you originally thought? (shortcomings in hypothesis)
• what shortcomings might there be in your experiment?
• what shortcomings might there be in your data?

What can you ascertain based on the experiment performed and data collected? Document your findings here; make a statement as to any discoveries you've made.