In C, we have to implement the Abstract Data Types (ADTs) ourselves. Implementations of these ADTs would be very limited if we had to base the underlying memory off of arrays in C. This is because C arrays, as we know, are fixed length.
The solution to this issue is to use dynamic memory allocation in order to request chunks of memory during runtime as needed. We ask the computer for these chunks (called nodes) and connect/link them using pointers. This is the idea of a linked list.
Modelling a bank line using a linked list
Here is how we can use a linked list to model a queue in a bank line where:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Person person_t;
typedef struct BankLine bank_line_t;
struct Person {
char name[100];
int age;
person_t *next;
};
struct BankLine {
char name[50];
person_t *head;
person_t *tail;
};
bank_line_t create_bank_line(char *name) {
bank_line_t new_line;
strcpy(new_line.name, name);
new_line.head = NULL;
new_line.tail = NULL;
return new_line;
}
person_t *create_person(char *name, int age) {
person_t *new_person = malloc(sizeof(person_t));
strcpy(new_person->name, name);
new_person->age = age;
new_person->next = NULL;
printf("😁 Someone appeared: %s (%d years old)\n", new_person->name,
new_person->age);
return new_person;
}
void add_person_to_line(char *name, int age, bank_line_t *bank_line) {
person_t *new_person = create_person(name, age);
if (bank_line->head == NULL) {
bank_line->head = new_person;
printf(" 👆 %s is the first person in the line\n", new_person->name);
}
if (bank_line->tail == NULL) {
bank_line->tail = new_person;
printf(" 👇 %s is the last person in the line\n", new_person->name);
} else {
bank_line->tail->next = new_person;
bank_line->tail = new_person;
printf(" 👇 %s went to the back of the line\n", new_person->name);
}
}
void info(person_t *person) {
printf(" 😃 \"My name is %s. I am %d years old. ", person->name,
person->age);
if (person->next != NULL) {
printf("The person after me is %s\"\n", person->next->name);
} else {
printf("No one comes after me in the line\"\n");
}
}
void bank_line_info(bank_line_t *bank_line) {
printf("👀 This bank line is %s\n", bank_line->name);
printf("👀 The person at the head of the line is %s (age %d years)\n",
bank_line->head->name, bank_line->head->age);
person_t *current_person = bank_line->head;
while (current_person != NULL) {
info(current_person);
current_person = current_person->next;
}
}
void free_bank_line(bank_line_t *bank_line) {
printf("👀 Freeing the line \"%s\"\n", bank_line->name);
person_t *current_person = bank_line->head;
while (current_person != NULL) {
person_t *next = current_person->next;
free(current_person);
current_person = next;
}
}
int main() {
bank_line_t rb_line = create_bank_line("Reepooblic Bank Line");
add_person_to_line("David", 17, &rb_line);
add_person_to_line("Joash", 26, &rb_line);
add_person_to_line("Athaliah", 18, &rb_line);
add_person_to_line("Anita", 36, &rb_line);
bank_line_info(&rb_line);
free_bank_line(&rb_line);
return 0;
}
bank-line.c Copy
Assignment
Create a modified version of the code above with the following variations:
- Use Node instead of Person
- Use linked list instead of bank line
- Each node should store an integer called value instead of the member variables name and age
- Add a function that can swap two nodes in the linked list by changing their next member variables