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.
Here is how we can use a linked list to model a queue in a bank line:
#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