Craig Rodrigues!

Learning to Code: Week 16 - Linked Lists

TOTAL POMODOROS THIS WEEK: 18

August 25, 2016 Part 2

August 26, 2016

  • Installed a Pomodoro app on my phone and Macbook Pro for more focused blocks and being able to keep better track of how much I’ve worked. Every 25 minute block will be marked with a 🍅 under the date.
    • I should start a blog like this one.

image04

Probably the same for any college degree. It was for my Marketing one.

August 27, 2016

Pomodoros: 🍅🍅🍅

  • And it’s gone —The true cost of interruptions
  • Continuing on with Pointers and Memory: http://cslibrary.stanford.edu/102/PointersAndMemory.pdf
  • Went to the Code Newbie meetup this weekend and it was great. Ran from 12:00PM - 3:00PM
    • The meetup was in a cooler format with two speakers I got to chat with afterwards.
    • I met one manager for Big Nerd Ranch (Chris Aquino) and a UX designer who teaches a bit now after leaving Big Nerd Ranch (Brandy Porter)
    • Kim who runs the Code Newbie meetups is a great networker. She suggested I go to this conference here: CONNECT.TECH
      • Problem is that all the panels seem way above me and it costs $350.
      • I think I might be able to volunteer for it however and still meet cool people without the big cost?
    • I met a few more cool people there that I hope to keep in touch with. I wish there was a good way to keep track of my personal network without going insane...

August 28, 2016

Pomodoros: 🍅🍅

  • Essential C: http://cslibrary.stanford.edu/101
    • Have a mental picture (or a real drawing) of how your C code is using memory. That's good advice in any language, but in C it's critical.
    • Comments should describe what the code accomplishes which is much more interesting than a translation of what each statement does. Comments should also narrate what is tricky or non-obvious about a section of code.
    • Making a drawing is an excellent way to think about the variables in a program. Draw each variable as box with the current value inside the box. This may seem like a "beginner" technique, but when I'm buried in some horribly complex programming problem, I invariably resort to making a drawing to help think the problem through.
    • I don’t really know the difference between stuff done at “run time” and stuff done at “compile time”
    • Relying on the difference between the pre and post variations of these operators is a classic area of C programmer ego showmanship. The syntax is a little tricky. It makes the code a little shorter. These qualities drive some C programmers to show off how clever they are. C invites this sort of thing since the language has many areas (this is just one example) where the programmer can get a complex effect using a code which is short and dense.
    • Code is "portable" if with no programmer intervention it compiles and runs correctly on different types of computers.
    • When using a break, it's nice to write the enclosing loop to iterate in the most straightforward, obvious, normal way, and then use the break to explicitly catch the exceptional, weird cases.

image03

August 29, 2016

Pomodoros: 🍅🍅🍅🍅🍅

  • Continuing with Essential C: http://cslibrary.stanford.edu/101
    • Array out of bounds references are an extremely common form of C run-time error. You can use the assert() function to sprinkle your code with your own bounds checks. A few seconds putting in assert statements can save you hours of debugging.
    • Wish I could extract all my notes and highlights, but I can’t. Go figure.

image01

{
	// Allocate the pointers
	struct Node* x;
	struct Node* y;
	struct Node* z;

	// Allocate the pointees
	x = malloc(sizeof(Node));
	y = malloc(sizeof(Node));
	z = malloc(sizeof(Node));

	// Put the numbers in the pointees
	x->value = 1;
	y->value = 2;
	z->value = 3;

	// Put the pointers in the pointees
	x->next = y;
	y->next = z;
	z->next = x;
}

 

image02

/*
 Takes a list and a data value.
 Creates a new link with the given data and pushes
 it onto the front of the list.
 The list is not passed in by its head pointer.
 Instead the list is passed in as a "reference" pointer
 to the head pointer -- this allows us
 to modify the caller's memory.
*/

void Push(struct node** headRef, int data) {
   struct node* newNode = malloc(sizeof(struct node));
   newNode->data = data;
   newNode->next = *headRef;  // The '*' to dereferences back to the real head
   *headRef = newNode;        // ditto
}
void PushTest() {
   struct node* head = BuildTwoThree();// suppose this returns the list {2, 3}
   Push(&head, 1);      // note the &
   Push(&head, 13);
   // head is now the list {13, 1, 2, 3}
}

 

August 30, 2016

Pomodoros: 🍅🍅🍅🍅

int Count(struct node* head, int searchFor) {
    int count = 0;

    struct node* current = head;

    while (current != NULL) {
        if (current->data == searchFor)
            count++;
        current = current->next;
    }

    return count;
}

 

    • Write a GetNth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position. GetNth() uses the C numbering convention that the first node is index 0, the second is index 1, ... and so on. So for the list {42, 13, 666} GetNth() with index 1 should return 13. The index should be in the range [0..length- 1]. If it is not, GetNth() should assert() fail (or you could implement some other error case strategy).
int GetNth(struct node* head, int index) {

    int position = 0;

    struct node* current = head;

    while (current != NULL) {
        if (position == index)
            return current->data;
        else {
            position++;
            current = current->next;
        }

    }
    assert(0); //error check if index cannot be found.
}

 

    • Write a function DeleteList() that takes a list, deallocates all of its memory and sets its head pointer to NULL (the empty list).
      • This requires a variable to track the current position in the linked list and also a variable to store the next address since it won’t be available after we free it.
      • Then after the node has been freed we set the current to our temp next variable to move to the next one until they are all freed.
      • Once they are all gone then we can set the head of the list to NULL.
void DeleteList (struct node** headRef) {
    struct node* current = *headRef;
    struct node* next;

    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }

    *headRef = NULL;
}
    • Write a Pop() function that is the inverse of Push(). Pop() takes a non-empty list, deletes the head node, and returns the head node's data. Pop() should assert() fail if there is not a node to pop.
      • The order in which I do things here is the key.
      • 1) Store the data in a temp variable? 2) Move the *head to the 2nd node. 3) Free the first node. 4) Return temp variable’s data.
int Pop(struct node** headRef) {
    struct node* current = *headRef;
    int temp;

    if (current != NULL) {
        temp = current->data;
        *headRef = current->next;
        free(current);
        return temp;
    }

    assert(0);
}

 

    • A more difficult problem is to write a function InsertNth() which can insert a new node at any index within a list. Push() is similar, but can only insert a node at the head end of the list (index 0). The caller may specify any index in the range [0..length], and the new node should be inserted so as to be at that index.
      • I made a function that works, except it iterates over the entire list, instead of stopping after the node is inserted. Can’t quite figure out how to stop it rather than using a break?

August 31, 2016

Pomodoros: 🍅🍅🍅🍅

void InsertNth(struct node** headRef, int index, int data) {

    // special case if index is 0
    if (index == 0)
        Push(headRef, data);
    else {
        // traverse to index - 1
        struct node* current = *headRef;

        for (int i = 0; i < index-1; i++) {
            assert(current != NULL);
            current = current->next;
        }

        assert(current != NULL); // need to check here one more time or Push below won't work

        // using Push to make a new node at the current index instead of the head as usual
        Push(&(current->next), data);
    }
}

 

    • I decided to make a function to print out a linked list called PrintList(). It was getting annoying to checking what was in my list quickly.
void PrintList(struct node* head) {
    struct node* current = head;

    while (current != NULL) {
        printf("%i ", current->data);
        current = current->next;
    }
    printf("\n");
}

 

    • Write a SortedInsert() function which given a list that is sorted in increasing order, and a single node, inserts the node into the correct sorted position in the list. While Push() allocates a new node to add to the list, SortedInsert() takes an existing node, and just rearranges pointers to insert it into the list. There are many possible solutions to this problem.
      • I think I have the logic down here, except right now I traverse to the proper node but my node gets inserted AFTER that node when I want it to be inserted in FRONT not AFTER since the check is if the current node I’m at is >= the one I’m trying to insert.
      • Oh fuck I figured it out on a hunch. I can make a pointer to a pointer with two arrows! So I can check the data in a node that I’m not actually AT but just follow the pointer forward to check so I can insert a node right BEFORE. Holy shit.
      • However the above doesn’t work for the very first item in the list. Shit.
      • Okay so I made an exception to check if the first element is >= the node I’m trying to put in so that works. However if the new node I’m putting in is higher than the last one it’s not working just yet. I’m sure that has something to do with my last NULL checker.
      • Ok I finally figured it out. I needed my while loop to check if current->next was NULL not if the current node I was on is NULL or not. My loop would run out of bounds and cause a seg fault because of it.
      • I’m sure the solutions are way better than mine, but this is what I came up with.
void SortedInsert(struct node** headRef, struct node* newNode) {
    struct node* current = *headRef;

    if (current != NULL && current->data >= newNode->data) {
        newNode->next = *headRef;
        *headRef = newNode;
    }
    else {
        while (current->next != NULL) {
            // checking the next node BEFORE I am actually at it.
            if (current->next->data >= newNode->data) {
                newNode->next = current->next;
                current->next = newNode;
                break;
            }
            current = current->next;
        }
        // at the end of the list at this point. Just add the new node here.
        current->next = newNode;
    }
}

 

        • The solution they have didn’t use a cursor until after they checked the head. It isn’t needed until after that. Can just use the headRef pointer and see if it’s NULL or not.
        • And damn I see that their while loop also includes the condition I have in my if-statement. That removes the need for a break; in there since once you hit the second condition the while loop ends. Not sure how I didn’t see that.
        • Also putting my conditions only into the while loop takes care of the multiple same values problems.
  • Drawing out the graphs really helped figure out how the pointers are working. I won’t spend too much more time on this since Shawn says I won’t really need to have in-depth knowledge of pointers in other languages.
      • Their solution below:
// Uses special case code for the head end
void SortedInsert(struct node** headRef, struct node* newNode) {
   // Special case for the head end
   if (*headRef == NULL || (*headRef)->data >= newNode->data) {
      newNode->next = *headRef;
      *headRef = newNode;
   }
   else {
      // Locate the node before the point of insertion
      struct node* current = *headRef;
      while (current->next!=NULL && current->next->data<newNode->data) {
         current = current->next;
      }
      newNode->next = current->next;
      current->next = newNode;
   }
}

 

Learning to Code: Week 17 - Problem Set 5 "Mispellings"

Learning to Code: Week 15 - Data Structures