COMP SCI 354 LECTURE 008

Linked Lists

Struct Review

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

struct address {
    char street[100];
    char state[3];
    int zip;
}

struct person {
    char name[100];
    int id;
    struct address addr;
};

int main() {
    struct person p;
    p.id = 12345;
    p.addr.zip = 54321;

    strncpy(p.name, "Mike", 100);

    struct person *pp = &p;
    pp -> id = 45678;
}

Linked List

#include <stdio.h>

struct node {
    int data;
    struct node *next; // Must have a pointer here
};

• head

int main() {
    struct node *head = NULL;
    struct node *first = malloc(sizeof(struct node));
    first -> data = 10;
    first -> next = NULL;

    head = first; // a pointer equals to a pointer
}

• Append function

struct node* Append(struct node * head, int data) { // append a node in the linked list
    // create the new node
    struct node *new_node = malloc(sizeof(struct node));
    new_node -> data = data;
    new_node -> next = NULL;

    if (head == NULL) return new_node;
    else {
        struct node *current = head;
        while (current -> next != NULL) {
            current = current -> next;
        }
        current -> next = new_node;
    }
    return head;
}

• Print function

void print_list (struct node *head) { // The head pointer in main will not be modified
    while (head != null) {
        printf("%d ", head -> data);
        head = head -> next;
    }
    printf("\n");
}

• delete first function

// to delete the very first element, we need a pointer as parameter to change the
// one that in main function (the function that calls delete_first function),
// otherwise, the 'head' in the upper level function would not be changed
void delete_first(struct node **phead) {
    *phead = (*phead) -> next; // *phead equals to the content of the head, equals
// to the address of the first element.
}

// whenever calling the method in main function, remember that we need to provide
// a pointer to a pointer, so as head is a pointer to the first element, which is
// struct node *head = NULL;
delete_first(&head);

The deleted element is still in the heap: Memory Leak. We need to free that memory.

void delete_first(struct node **phead) {
    struct node *deleted = *phead; // store the address of the deleted element
    *phead = (*phead) -> next;
    free(deleted);
}

• If the linked list is empty

if (*phead == NULL) return;