ESC190 Lecture Notes: Part 2
Data Structures and Basic Algorithms

See all lecture notes here.

L11: Sorting

qsort

1. The array to be sorted
2. The number of elements in the array
3. The size of each element in the array
4. A function that compares two elements in the array. It should return
• A negative number if the first element is smaller than the second element
• 0 if the two elements are equal
• A positive number if the first element is larger than the second element

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
    
int compare_ints(const void *p_a, const void *p_b)
{
  int *p_a_i = (int *)p_a;
  int *p_b_i = (int *)p_b;
  return *p_a_i - *p_b_i;
}
    
int main()
{
  int arr[] = {6, 5, 10, 2};
  qsort(arr, 4, sizeof(int), compare_ints);
}

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

typedef struct student1{
  char name[20];
  int age;
} student1;

int compare_student1s(const void *p_a, const void *p_b)
{
  // Want to sort student1's by name
  // If students have the same age, sort by name

  student1 *p_a_s = (student1 *)p_a;
  student1 *p_b_s = (student1 *)p_b;
  int age_diff = p_a_s->age - p_b_s->age;
  if(age_diff != 0)
  {
    return age_diff;
  }else{
    return strcmp(p_a_s->name, p_b_s->name);
  }
}

int main()
{
  student1 s1_arr[] = {{"John", 20}, {"Jill", 21}, {"Jack", 21}};

  qsort(s1_arr, 3, sizeof(student1), compare_student1s);

  for (int i = 0; i < 3; i++)
    printf("%s %d\n", s1_arr[i].name, s1_arr[i].age);
}

• We can use curly braces to initialize a struct
• The strcmp function compares two strings and returns a negative number if the first string is smaller than the second string, 0 if the two strings are equal, and a positive number if the first string is larger than the second string

Reading Files

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

int main()
{
  FILE *fp = fopen("cities.txt", "r");
  char line[200];
  fgets(line, 200, fp);
  line[strlen(line) - 1] = '\0';
  int num_items = atoi(line);

  return 0;
}

1. Within main, a file pointer fp is created and is assigned the result of opening the file cities.txt in read mode. If the file doesn't exist, fopen returns NULL.
2. A character array line with a maximum size of 200 characters is declared.
3. The function fgets is called, which reads a line of text from the file pointed to by fp and stores it in the line array. The maximum number of characters to be read is specified as 200, the second argument to fgets.
4. The last character of line, which is the newline character, is replaced with a null terminator ('\0') to end the string.
5. The function atoi is called with line as its argument, which converts the string representation of a number to its integer value. This is 93827 for the project, the total number of cities.

L12: Bubble Sort

Bubble Sort

function bubbleSort(L)
    n = length(L)
    repeat
        swapped = false
        for i=1 to n-1 inclusive do
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap(A[i-1], A[i])
                swapped = true
            end if
        end for
    until not swapped
end function

5, 2, 10, 56, 15
    

5, 2, 10, 56, 8
2, 5, 10, 56, 8 // 2 and 5 swapped
2, 5, 10, 56, 8 // 5 and 10 in order
2, 5, 10, 56, 8 // 10 and 56 in order
2, 5, 10, 8, 56 // 56 and 8 swapped
// Go back to beginning
2, 5, 10, 8, 56 // 2 and 8 in order
2, 5, 10, 8, 56 // 5 and 10 in order
2, 5, 8, 10, 56 // 8 and 10 swapped
2, 5, 8, 10, 56 // 10 and 56 in order
// Go back to beginning
2, 5, 8, 10, 56 // 2 and 5 in order
2, 5, 8, 10, 56 // 5 and 8 in order
2, 5, 8, 10, 56 // 8 and 10 in order
2, 5, 8, 10, 56 // 10 and 56 in order

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

void bubble_sort(void *arr, int num_items, int item_size,
                 int (*compare)(const void *, const void *))
{
  int i, j;
  void *temp = malloc(item_size);

  for (i = 0; i < num_items - 1; i++){
    for (j = 0; j < num_items - i - 1; j++){
      // compare arr[j] and arr[j + 1], swap if necessary
      // arr[j] only makes sense if array is of type int*, float*, etc.
      void *p_j = arr + j * item_size;
      void *p_j1 = arr + (j + 1) * item_size;

      // Now can compute compare(p_j, p_j1)
      if (compare(p_j, p_j1) > 0){
        // kind of want to swap *p_j and *p_j1
        memcpy(temp, p_j, item_size); // temp = *p_j
        memcpy(p_j, p_j1, item_size);
        memcpy(p_j1, temp, item_size);
      }
    }
  }
  free(temp);
}

int compare_int(const void *p_a, const void *p_b)
{
  const int *x = (const int *)p_a;
  const int *y = (const int *)p_b;
  return *x - *y;
}

int main()
{
  int arr[] = {64, 34, 25, 12, 22, 11, 90};
  int num_items = sizeof(arr) / sizeof(arr[0]);
  bubble_sort(arr, num_items, sizeof(int), compare_int);

  for (int i = 0; i < num_items; i++)
    printf("%d ", arr[i]);

  return 0;
}

• void *arr: This is a pointer to the array to be sorted. The data type of the array is not specified, so the function can be used with arrays of any data type.
• int (*compare)(const void *, const void *) is a pointer to a comparison function. The comparison function takes two pointers to void as arguments and returns an integer less than, equal to, or greater than zero, depending on the result of the comparison. This allows the function to be used with arrays of any data type and to sort the array in any order.

Optimizing Bubble Sort

void bubble_sort(void *arr, int num_items, int item_size,
                 int (*compare)(const void *, const void *))
{
  int i, j;
  void *temp = malloc(item_size);

  for (i = 0; i < num_items - 1; i++)
  {
    int swapped = 0;
    for (j = 0; j < num_items - i - 1; j++)
    {
      // compare arr[j] and arr[j + 1], swap if necessary
      // arr[j] only makes sense if array is of type int*, float*, etc.
      void *p_j = arr + j * item_size;
      void *p_j1 = arr + (j + 1) * item_size;

      // Now can compute compare(p_j, p_j1)
      if (compare(p_j, p_j1) > 0)
      {
        // kind of want to swap *p_j and *p_j1
        memcpy(temp, p_j, item_size); // temp = *p_j
        memcpy(p_j, p_j1, item_size);
        memcpy(p_j1, temp, item_size);
        swapped = 1;
      }
    }
    if (!swapped){
      break; // return could cause a memory leak
             // could go free(temp) and return
    }
  }
  free(temp);
}

L13: Patch

Using GDB

gdb patch

layout asm

Changing a Function

int f(int a, int b, int c)
{
    return a + b;
}

int g(int a, int b, int c)
{
    return a + c;
}

│   0x1189 <f>              endbr64
│   0x118d <f+4>            push   %rbp
│   0x118e <f+5>            mov    %rsp,%rbp
│   0x1191 <f+8>            mov    %edi,-0x4(%rbp)
│   0x1194 <f+11>           mov    %esi,-0x8(%rbp)
│   0x1197 <f+14>           mov    %edx,-0xc(%rbp)
│   0x119a <f+17>           mov    -0x4(%rbp),%edx
│   0x119d <f+20>           mov    -0x8(%rbp),%eax
│   0x11a0 <f+23>           add    %edx,%eax
│   0x11a2 <f+25>           pop    %rbp
│   0x11a3 <f+26>           retq
│   0x11a4 <g>              endbr64
│   0x11a8 <g+4>            push   %rbp
│   0x11a9 <g+5>            mov    %rsp,%rbp
│   0x11ac <g+8>            mov    %edi,-0x4(%rbp)
│   0x11af <g+11>           mov    %esi,-0x8(%rbp)
│   0x11b2 <g+14>           mov    %edx,-0xc(%rbp)
│   0x11b5 <g+17>           mov    -0x4(%rbp),%edx
│   0x11b8 <g+20>           mov    -0xc(%rbp),%eax
│   0x11bb <g+23>           add    %edx,%eax
│   0x11bd <g+25>           pop    %rbp
│   0x11be <g+26>           retq 

• Each line is an instruction. Each byte of instruction is stored in a different location in memory. The first set of characters represent the memory in hexadecimal.
• The mov command moves data from one location to another. The first argument is the destination, the second argument is the source.
• In GDB, we can display the value at an address with the command x 0x119d, which in this particular example gives 0x119d <f+20>: 0x01f8458b. The hexadecimal number 0x01f8458b encodes the instructions for that line. We can display it as a decimal if we do x/d 0x119d which outputs 0x119d <f+20>: 33047947

void patch(int (*h)(int, int, int))
{
    *(int *)((void*)h + 20 )  = 33047947; //0x01f8458b;
}

1. It takes in the pointer to a function. Recall that if we want to modify int a = 5; inside a function, we need to pass in the address. The same goes here if we want to modify a function.
2. We cast the pointer to a void pointer (i.e. not associated with any data type) using (void*)h.
3. Note that (void*)h is the address of the start of the function. To get to the part of the function or instructions we actually want to change, we need to increment the address by 20 bytes (which we said earlier was the only place that it differed from f).
4. (void*)h + 20 is a void pointer that points to the line of instruction we want to change. But we've seen that instructions are encoded by a number, so we need to cast this to an int pointer via (int *)((void*)h + 20).
5. We've seen that the instruction we want to change this to can be represented as an integer as 33047947, so we write this into memory at this address.
   • Clarification: Note that an integer is 4 bytes but the instruction at 0x11b8 <g+20> is 3 bytes, since the next instruction is at 0x11b8 <g+20>. The reason this still works is because the instruction at 0x11bb <g+23> and 0x11a0 <f+23> is the same, so the 4th byte will be overwritten with a byte that is equal to it.

Python Memory Model Weirdness

import ctypes

def change_float(x):
    # Go to the memory address of x and change the value there
    pointer = ctypes.c_void_p(id(x))
    float_pointer = ctypes.cast(pointer, ctypes.POINTER(ctypes.c_double))
    float_pointer[2] = 12.0



if __name__ == '__main__':
    x = 11.0
    change_float(x)
    print(x) # 12.0
    print(x == 11.0) # True
    print(11.0 == 12.0) # True
    print(10+1.0 < 10+2.0) # False

12.0
True
True

1. Inside the function, the id function is used to get the memory address of the object, and uses the ctypes module to cast that memory address to a pointer to a ctypes.c_double type. There is some nomenclature confusions here,
   • In C, a double is a double-precision floating point number (usually 64 bits) while a float is a single-precision floating point number (usually 32 bits)
   • In Python, a float is the same as a double in C.
2. The line float_pointer[2] = 12.0 is setting the value stored at the memory location pointed to by float_pointer to be 12.0.
3. This line of code modifies the memory of the float object that was passed to the change_float function, so that the address at which the values x and 12.0 are stored, is the same, so x == 12.0 and their values are equal. However, the object x and 11.0 are identical (i.e. they have the same id so Python doesn't both checking their actual values), so we also have x == 11.0 and 11.0 == 12.0 (since 11.0 is the same object as x).
   
   Note that the memory representation of an object is the way that the value of the object is stored in computer memory, while the id is a unique identifer that is assigned to each object. Two objects could have different ids but the same memory representation. The reason this is allowed is because the ctypes module is allowing the user to bypass Python's memory management and directly access memory, which is not typically recommended or necessary.
4. The reason the last three lines work is that the 11.0 literal is mapped to refer to a single id address since it appears in the code several times. So print(10+1.0 < 10+2.0) will still print False.

• Know: Python and C memory model
• Don't Know: Machine Code and how to use ctypes in Python

L14: Python Memory Model and Valgrind

Python Memory Model

-----------
Variable Table
x | @1032
-----------
Memory Table
%1032 | 11.0
-----------

-----------
Variable Table
x | @1032
-----------
Memory Table
%1032 | 12.0
-----------

x = 5
y = 7
x1 = 6
print(x + y == x1 + y)

Valgrind

• Linux: Can be installed
• Windows: Install Windows Subsystem for Linux (WSL): See here.
• Any computer: Connect to the ECF Linux machines
• Gradescope: There is a "test" assignment on gradescope which will run Valgrind for you.

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

int main(){
    char a[6] = "EngSci";
    printf("%c", a[1000000]);
}

#include <stdio.h>
#include <stdlib.h>
  
int main(){
    char *p = malloc(1000000);
    return 0;
}

• Undefined behaviour: The program tries to access a memory location that is out of bounds. The array a has a size of 6, and accessing an index that is out of bounds leads to undefined behavior, and in this case, it results in a segmentation fault.
• Memory leak: The program allocates memory using the malloc function but does not free it, leading to a memory leak.

valgrind ./file_name

==3274== Memcheck, a memory error detector
==3274== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3274== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==3274== Command: ./test_valgrind
==3274== 
==3274== Invalid read of size 1
==3274==    at 0x109191: main (in /home/xueqilin/esc190_notes/test_valgrind)
==3274==  Address 0x1fff0f3862 is not stack'd, malloc'd or (recently) free'd
==3274== 
==3274== 
==3274== Process terminating with default action of signal 11 (SIGSEGV)
==3274==  Access not within mapped region at address 0x1FFF0F3862
==3274==    at 0x109191: main (in /home/xueqilin/esc190_notes/test_valgrind)
==3274==  If you believe this happened as a result of a stack
==3274==  overflow in your program's main thread (unlikely but
==3274==  possible), you can try to increase the size of the
==3274==  main thread stack using the --main-stacksize= flag.
==3274==  The main thread stack size used in this run was 8388608.
==3274== 
==3274== HEAP SUMMARY:
==3274==     in use at exit: 0 bytes in 0 blocks
==3274==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==3274== 
==3274== All heap blocks were freed -- no leaks are possible
==3274== 
==3274== For lists of detected and suppressed errors, rerun with: -s
==3274== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault

==3471== Memcheck, a memory error detector
==3471== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3471== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==3471== Command: ./test_valgrind
==3471== 
==3471== 
==3471== HEAP SUMMARY:
==3471==     in use at exit: 1,000,000 bytes in 1 blocks
==3471==   total heap usage: 1 allocs, 0 frees, 1,000,000 bytes allocated
==3471== 
==3471== LEAK SUMMARY:
==3471==    definitely lost: 1,000,000 bytes in 1 blocks
==3471==    indirectly lost: 0 bytes in 0 blocks
==3471==      possibly lost: 0 bytes in 0 blocks
==3471==    still reachable: 0 bytes in 0 blocks
==3471==         suppressed: 0 bytes in 0 blocks
==3471== Rerun with --leak-check=full to see details of leaked memory
==3471== 
==3471== For lists of detected and suppressed errors, rerun with: -s
==3471== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

L16: Best Practices

• Break down each task into smaller sub-tasks
• Test frequently WHILE you are writing the program
• When debugging, debug line by line.

Walkthrough of Lab Question

1. g = 9.8
2. e = 2.728
3.

1. Task 1: First, we need to be able to extract the appropriate number from each line.
   
   We can write a function with signature const char* get_double_str(const char* line) where the const is optional, but is a good practice because it tells us that we should not be changing the contents of the string.
   
   It is important to note that const char* is different from char* const. The first gives us a pointer to a const char (in this case), while the second gives us a constant pointer to a char (where the value being pointed to can change but the pointer can't).
   
   There are several ways to approach this:
   1. Using strtok(). This works, but is a bit complicated in figuring out how it works.
   2. Finding the equal sign and then skipping a space.
   3. Finding the first digit.
   We will choose this last approach because it is more robust (and avoids issues where there is no space after the equal sign). We do this by creating other subtasks:
   
   Subtask: Checking if a character is a digit. We can do this via,

   int is_digit(char c)
   {
       return c >= '0' && c <= '9';
   }
   

   which works because the ASCII values of the digits are in order. Before we move on, we can test this:
   
   

   int main()
   {
       for(int c = '0'; c <= '9'; c++)
       {
           printf("%c is digit: %d. Another way to
           compute the value: %d\n", c, (int)c, c-'0');
       }
       printf("Is 'a' a digit? %d\n", is_digit('a'));
       printf("Is '0' a digit? %d\n", is_digit('0'));
       printf("Is '9' a digit? %d\n", is_digit('9'));
       printf("Is ' ' a digit? %d\n", is_digit(' '));
       printf("Is '4' a digit? %d\n", is_digit('4'));
   }
   

   which gives us the output:
   
   

   0 is digit: 48. Another way to compute the value: 0
   1 is digit: 49. Another way to compute the value: 1
   2 is digit: 50. Another way to compute the value: 2
   3 is digit: 51. Another way to compute the value: 3
   4 is digit: 52. Another way to compute the value: 4
   5 is digit: 53. Another way to compute the value: 5
   6 is digit: 54. Another way to compute the value: 6
   7 is digit: 55. Another way to compute the value: 7
   8 is digit: 56. Another way to compute the value: 8
   9 is digit: 57. Another way to compute the value: 9
   Is 'a' a digit? 0
   Is '0' a digit? 1
   Is '9' a digit? 1
   Is ' ' a digit? 0
   Is '4' a digit? 1

   Now, we can finish the function:
   
   

   const char* get_double_str(const char* line)
   {
       while(!is_digit(*line) && *line != '\0')
       {
           line++;
       }
       return line;
   }
   

   which is motivated by moving the pointer until we find a digit, or until it reaches the null character. We can test this as well in our main function,
   
   

   printf("%s\n", get_double_str("pi = 3.14"));
   printf("%s\n", get_double_str("G = 0.0000000000667"));
   printf("%s\n", get_double_str("e = 2.728"));

which gives us the desired output. At this point, we should also be thinking if we thought of all the test cases. It turns out one thing we didn't think of is dealing with negatives! We can fix this by modifying the is_digit() function to also check if the character is a negative sign, via the following:

int is_digit_or_minus(char c)
{
    return (c >= '0' && c <= '9') || (c == '-');
}

We would also need to test this new code to check if it actually detects the negative sign AND if it still works with the regular digits AND that it is reflected correctly in get_double_str. But since we already have code that tests these functions, we only need to make minor modifications! The full code and test cases will be included at the end of this section.
2. Task 2: Next, we need to be able to convert the string to an actual float. There is a default function for this, atof(), but we will write our own function for practice. The idea behind our function is that it will first get the sign, then get the integer part of the float, then get the decimal portion. To get the integer part, we note that as an example, \[542 = 10 \cdot (10 \cdot 5 + 4) + 2\]
so we can work insides out: we multiply \(5\) by ten, then add \(4\). Then multiply the combined result by \(10\), then add on the next digit. This allows us to work from left to right. We can write a function to do this,



double my_atof(const char *str)
{   
    // First figure out the sign
    int sign = 1;
    if(*str == '-'){
        sign = -1;
        str++;
    }

    // str is now a string that starts with a digit
    double integer_part = 0;
    while(is_digit_or_minus(*str)){
        integer_part = 10*integer_part + (*str - '0');
        str++;
    }

    return sign * integer_part;
}

and of course, test this part out before we move on to the float part. This allows us to very early on identify if there is a problem with the integer part. If we don't test right now, and test later, then we don't know if the problem is with the integer part or the float part.

Always test code you are able to test, before writing more code.

Now how can we deal with the fractional part? We can try breaking down the decimal \(0.123\) in a similar way, writing it as: \[0.123 = 1 \cdot 10^{-1} + 2 \cdot 10^{-2} + 3 \cdot 10^{-3}.\] If we can keep track of the current power of 10 (which decreases by a factor of 10 each time), then we can read from left to right and add on the appropriate terms to the fractional part. This gives us,

double my_atof(const char *str)
{   
    // First figure out the sign
    int sign = 1;
    if(*str == '-'){
        sign = -1;
        str++;
    }

    // str is now a string that starts with a digit
    double integer_part = 0;
    while(is_digit_or_minus(*str)){
        integer_part = 10*integer_part + (*str - '0');
        str++;
    }

    // Now we potentially have a fractional part
    // Assume there is always a decimal point
    str++; // Skip the decimal point

    double fractional_part = 0;
    double cur_pow10 = 0.1;
    while(*str != '\0'){
        fractional_part += (*str - '0') * cur_pow10;
        cur_pow10 *= 0.1;
        str++;
    }

    return sign * (integer_part + fractional_part);
}

which we should also test.

void print_sum_of_constants(const char *filename)
{
    FILE *fp = fopen(filename, "r");
    if(fp == NULL){
        printf("Error opening file %s\n", filename);
        return;
    }

    double sum = 0;
    char line[100]; // Assume no line is longer than 100 characters
    while(fgets(line, 100, fp) != NULL){
        const char *double_str = get_double_str(line);
        sum += my_atof(double_str);
    }
    
    printf("Sum of constants in %s is %f\n", filename, sum);
}

while(*str != '\0' && *str != '\n'){
  fractional_part += (*str - '0') * cur_pow10;
  cur_pow10 *= 0.1;
  str++;
}

L17: Memory Model Review for Structs

#include <stdio.h>
#include <string.h>

typedef struct student1{
    char name[3];
    int age;
} student1;

void change_name_wrong(student1 s)
{
    s.name[0] = 'a';
}

void change_name_right_a(student1 *p_s)
{
    p_s->name[0] = 'b';
}

void change_name_right_b(student1 *p_s)
{
    strcpy(p_s->name, "c");
}

int main(){
    student1 s = {"x", 20};
    printf("%s %d\n", s.name, s.age);

    change_name_wrong(s);
    printf("%s %d\n", s.name, s.age);

    change_name_right_a(&s);
    printf("%s %d\n", s.name, s.age);

    change_name_right_b(&s);
    printf("%s %d", s.name, s.age);
}

C equivalent of Python Code

def change_name(s):
  s[0] = "b"

if __name__ == '__name__':
  s = ["x", 20]
  change_name(s)

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

typedef struct student2{
    char *name;
    int *p_age;
} student2;

void change_name(student2 *p_s)
{
    p_s->name = "b";
}
int main(){
    student2 *p_s = (student2*)malloc(sizeof(student2));

    // Create a temporary student2
    int *p_age = (int*)malloc(sizeof(int));
    *p_age = 20;
    student2 temp = {"x", p_age};

    // Copy the temporary student2 into p_s
    memcpy(p_s, &temp, sizeof(student2));

    printf("%s %d\n", p_s->name, *(p_s->age));

    change_name(p_s);
    printf("%s %d\n", p_s->name, *(p_s->age));

}

L18: Consts and Linked Lists

The const keyword

• const indicates that a value is not to be changing. Changing a const value could result in a compilation warning or warning. The intended purpose is to help catch errors in the code earlier. Consider:

  const char c = 42;
  c = 43; // compilation error
  
  const char *p_c = (char*)malloc(sizeof(char));
  *p_c = 0; // compilation error
  p_c = "hello"; // fine
  

• In the second part of the above example, we demonstrate that we are not allowed to modify the contents of the memory at the address p_c. However, we can assign the pointer p_c to point to a string literal "hello". This is allowed because the pointer itself is not modified, only the memory location it points to.
• String literals like "hello" are of type const char*
• Sometimes, we wish to not be able to change the address, but be able to go to the address and change the contents. We can achieve that via the following:

  int * const p_n = (int*)malloc(sizeof(int))
  p_n = 0; // error
  *p_n = 1; // fine
  

• Similarly, we can disallow changing both the address and the contents (but this is usually not done)

  const int * const p_n = (int*)malloc(sizeof(int))
  p_n = 0; // error
  *p_n = 1; // error
  

typedef struct student2{
    const char *name;
    const int *p_age;
} student2;

void change_name_wrong(student2 *p_s)
{
    p_s->name[0] = 'b';
}

void change_name_right(student2 *p_s)
{
    p_s->name = "b";
}

Linked Lists

• A linked list consists of a data structure called a node, which consists of the following information:
• data: the actual data you need to store
• next: the address of the next node
• We can then make an array by creating a chain of these nodes, where we can find the next node by following the next pointer. While this uses up more space than a regular array, it has the benefit of preventing re-allocating everything. For example, if we want to add an element to the end of the list, we can simply create a new node and set the next pointer of the last node to point to the new node (+ a minor detail we'll touch on in a bit).
• See the lecture slides for a visual of linked lists and their operations.

Linked List Operations

• Inserting: Suppose we already have a pointer to a node, and we wish to insert a node after that. What we can do is create this new node, and set its next pointer to point to the node that the original node pointed to. Then, we can set the original node's next pointer to point to the new node we just created.
• Analogy: A popular children's activity is to form a human train, where each person puts their hand on the shoulder of the person in front of them, forming a chain (linked list). If a new participant Bob (the new node) wants to join the train in front of Alice (who is holding Carol's shoulder), Bob can do so by holding onto Carol's shoulder, and then Alice can hold onto Bob's shoulder.
• Removing: Suppose we already have a pointer to a node, and we wish to delete that node. We can do so by setting the next pointer of the node before the node we want to delete to point to the node after the node we want to delete. Finally, we free up the memory.
• Analogy: If Bob wants to leave the train, he can simply let go of Carol's shoulder, and Alice can hold onto Carol's shoulder.
• Getting: Suppose we wish to find a node (i.e. its pointer) at a certain index (i.e. the ith node) In the previous 2 operations, we assumed we already had this pointer. We can do so by iterating through the linked list by following the next pointer until we find the node we want.
• Analogy: If a teacher wants to find the 7th student, they can start from the very beginning of the train and follow it to the end until the 7th student is found.

Linked List Implementation

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

typedef struct node{
    int data;
    struct node *next;
} node;

typedef struct LL{
    node *head;
    int size;
} LL;

void create_node(node **p_n, int data)
{
    *p_n = (node*)malloc(sizeof(node));
    (*p_n)->data = data;
    (*p_n)->next = NULL;
}


void create_LL_from_data(LL **p_LL, int *data_arr, int size)
{
    (*p_LL) = (LL*)malloc(sizeof(LL));
    (*p_LL)->size = 0; // initialize size to 0
    
    // keep track of the last node of the linked list
    node *tail = 0;

    for(int i = 0; i < size; i++){

        // n is a pointer to a node with data = data[i], next = NULL
        node *n;
        create_node(&n, data_arr[i]);

        // If the last node is the 1st node
        if(tail == 0){
            (*p_LL)->head = n;
        }

        // If the last node is not the 1st node
        else{
            // append the new node to the end of the linked list
            tail->next = n;
        }

        // update the tail
        tail = n;

        // update the size
        (*p_LL)->size++;
    }
}

int main(){
    int data_arr[] = {1, 2, 3, 4, 5};
    LL *p_LL;
    create_LL_from_data(&p_LL, data_arr, 5);
}

• The idea behind the create_LL_from_data function is to keep track of the last node of the linked list (known as the tail) and constantly update it such that every time we create a new node, the tail's next pointer points to the new node.
• Initializing a new node like node *n will cause the next pointer to be 0 i.e. NULL. This is how we can tell we reached the end of a linked list.
• we need to use pointers to pointers because we want to be able to modify the value of the LL pointer (i.e. the memory address it points to), rather than just the value of the data it points to.

L19: Abstract Data Type

• ints with operations +,-*,/,%
• lists with operations insert, remove, get

• Insert(list, i, x): add item x at index i of list. The item previously at index i, and all following items, are shifted up by one index to make room for x.
• Remove(list, i): remove item at index i of list. The item previously at index i+1, and all following items, are shifted down by one index to fill the gap.
• Get(list, i): return the item at index i of list.

Insert for Linked List

typedef struct node{
  int data;
  struct node *next;
} node;

typedef struct LL{
  node *head;
  int size;
} LL;

void LL_insert(LL *my_list, int new_elem, int index)
{
  // Create the new node 
  node *n;
  create_node(&n, new_elem);

  // If the list is empty
  if(my_list->head == NULL){
    my_list->head = n;
    my_list->size++;
    return;
  }

  // To insert at the very beginning
  if(index == 0){
    n->next = my_list->head;
    my_list->head = n;
    my_list->size++;
    return;
  }

  // Errors
  if (index < 0 || index > my_list->size-1){
    fprintf(stderr, "Invalid index %d", index);
    exit(1); // exits the program, returns 1 to the OS
  }

  // Traverse to the desired index
  node *cur = my_list->head;
  for(int i = 0; i < index; i++){
    cur = cur->next;
  }

  n->next = cur->next;
  cur->next = n;
  my_list->size++;
}

• If the list is empty, which we can check if the head is NULL, then we proceed to make the new node the first (and only) element of the linked list.
• We want to implement it such that inserting it at index 0 corresponds to inserting it at the very beginning. To do this, not only do we need to update the next pointer of the new node, but the head pointer of our linked list. The order here is important. If we instead ran my_list->head = n; first, we lose information on where the original head is located.
• If the index is invalid, there are a few possibilities of what we can do.
  1. Just Crash: Sometimes this is a good idea, if we are trying to optimize the code. It's on the user to give valid parameters.
  2. Don't crash and don't insert. Instead, set a global variable to indicate an error. The reason we need a global variable here is that there's no other thing we can return that will indicate this. For example, if we are trying to return the element at an invalid index, a naive idea would be to return something like -1 or "Error", but how do we know that this is actually an error and their list doesn't actually include this!
  3. Print an error message. In particular the best way to print an error is using fprintf(stderr, "message") because it prints to the standard error stream, which is different from the standard output stream. Unlike printf (which sometimes doesn't show in terminal), this will always show, and allows regular print statements and error messages to be separated.

Remove and Get for Linked List

Good Coding Practices

#if !defined(LIST_H)
#define LIST_H
void create_list_from_data(void **p_list, int *data_arr, int size);
void list_append(void *list, int new_elem);
void list_insert(void *list, int new_elem, int index);
void list_delete(void *list, int index);
void list_free_all(void *list);
int list_get(void *list, int index);
#endif

void list_insert(void *list, int new_elem, int index)
{
    LL_insert((LL*)list, new_elem, index);
}

int list_get(void *list, int index)
{
    return LL_get(list, index);
}

gcc linkedlist.c -c -o linkedlist.o

gcc main.c linkedlist.o -o main

gcc main.c arraylist.o -o main

• Modularity and Reusability: When writing our main code, we don't have to worry about how certain functions are implemented. Also, if we already have code that can implement abstract data structures, we can just re-use them for future projects without changing too much!
• Faster compilation: Using a precompiled object like linkedlist.o can save compilation time. Although this is not a big problem now, compilation time can be an issue for larger and more complex projects.

Python Classes

class Student:
  def __init__(self, name, gpa):
      self.name = name
      self.gpa = gpa
  
  def __str__(self):
      return self.name + ": " + str(self.gpa)
if __name__ == "__main__":
  s = Student('Fred', 3.7)
  print(s.name, s.gpa)

s.__str__()
Student.__str__(s)

class Student:
  def __init__(self, name, gpa):
      self.name = name
      self.gpa = gpa
  
  def __str__(self):
      return self.name + ": " + str(self.gpa)
  
  def __lt__(self, other):
      # Return True if self has lower gpa than other
      # If GPAs are tied, compare names

      if self.gpa < other.gpa:
        return True
      elif self.gpa == other.gpa:
        return self.name < other.name
      else:
        return False
if __name__ == "__main__":
  fred = Student('Fred', 3.7)
  bob = Student('Bob', 2.0)
  print(Student.__lt__(fred, bob))
  print(fred < bob)

L = [Student("Fred", 3.7"), Student("Bob", 3.7), Student("Alice", 3.9)]
L.sort()
print(L) # [Bob: 3.7, Fred: 3.7, Alice: 3.9]

def get_name(s):
  return s.name
L.sort(key=get_name)

L.sort(key=lambda s: s.name)

L20: Precedence

++ Operator

int a = 6;
int b = 7 + a++; // make b = 7+a, and then increment a by 1

int a = 6;
int b = 7 + (a++); // make b = 7+a, and then increment a by 1

char *s = "hello";
printf("%c", *(s++)); // incrementing the address 
                      // what happens with just *s++
printf("%c", (*s)++); // incrementing the value at address s
                      // 'h' becomes 'i'

char *s = "hello";
char dest[10];
char *dest_write = dest;
// want to copy string s into dest
while(*dest_write++ = *s++);

• The value of an "assignment relation" is equal to the value assigned. Therefore, the while loop will continue to run as long as *s is not NULL. In general, any non-zero value is true and any zero value (including NULL) is false.
• The notation *dest_write++ = *s++ tells us to assign the value of *s to *dest_write, then the ++ operator tells us to increment both pointers AFTER the assignment happens.

L21: Linked Lists II

class Node:
  def __init__(self, value):
      self.value = value
      self.next = None
  
  def __str__(self):
      return f"{self.value}"

if __name__ == '__main__':
  n1 = Node(12)
  n2 = Node(15)
  n3 = Node(500)

  n1.next = n2
  n2.next = n3

node *n1 = create_node(12)
node *n2 = create_node(15)
n1->next = n2;

class LinkedList:
  def __init__(self):
      self.head = None
  
  def get_i(self, i):
      # return the value at index i
      cur = self.head
      for j in range(i):
          cur = cur.next
      return cur.value

  def append(self, value):
      '''Add a new node with the value value to the end of the list'''
      # Create a new node
      new_node = Node(value)
      print(new_node)

      if self.head == None:
          self.head = new_node
      else:
          # Find the last node
          cur = self.head
          while cur.next != None:
              cur = cur.next
          cur.next = new_node
  
  def insert(self, value, i):
      '''Insert a node with the value value at index i'''
      new_node = Node(value)

      if i == 0:
          new_node.next = self.head
          self.head = new_node
      else:
          cur = self.head
          for j in range(i-1):
              cur = cur.next
          new_node.next = cur.next
          cur.next = new_node

  def __str__(self):
      cur = self.head
      s = ""
      if(cur == None):
          return "Empty list :("
      
      while cur != None:
          s += str(cur) + " -> "
          cur = cur.next
      return s[:-4] # remove last arrow

if __name__ == '__main__':
  LL = LinkedList()
  LL.append(3)
  LL.append(50)
  LL.append(100)

  print(LL)

L22+ Onwards