// Battle Royale Linked List Demo

// Part 1: Creating a linked list using a function
// that creates a single node.
// Looping through the list and printing out the names

// Part 2: Inserting into the linked list.
// Also finding specific insertion points and
// inserting into an ordered list

// Part 3: Removing from the linked list.
// Specifically removing by finding a player
// by their name
// Freeing a memory allocated linked list

// Marc Chee (cs1511@cse.unsw.edu.au) November 2020

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

#define MAX_NAME_LENGTH 100

struct player {
    struct player *next;
    char name[MAX_NAME_LENGTH];

struct player *createPlayer(char *newName, struct player *newNext);
int printPlayers(struct player *playerList);
struct player *insertAfter(struct player *insertPos, char *newName);
struct player *insertAlpha(struct player *list, char *newName);
struct player *removePlayer(struct player *list, char *remName);
void freePlayerList(struct player *head);

int main(void) {
    struct player *head = NULL;        
    head = insertAlpha(head, "Marc");
    head = insertAlpha(head, "Chicken");
    head = insertAlpha(head, "Aang");
    head = insertAlpha(head, "Zuko");    
    head = insertAlpha(head, "Katara");    
    // Game loop. Keep looping until there's only one player left
    while (printPlayers(head) > 1) {
        printf("Please type in the name of a player to knock out: ");
        char input[MAX_NAME_LENGTH];
        fgets(input, MAX_NAME_LENGTH, stdin);
        if (input[strlen(input) - 1] == '\n') {
            input[strlen(input) - 1] = '\0';
        head = removePlayer(head, input);
    // there's one (or less) player remaining
    printf("Winner winner Chicken's Dinner. %s has won.\n", head->name);
    return 0;

// create player allocates memory for a new player and
// populates it with newName and newNext.
// returns a pointer the the newly created player
struct player *createPlayer(char *newName, struct player *newNext) {
    struct player *newPlayer = malloc(sizeof (struct player));
    strcpy(newPlayer->name, newName);
    newPlayer->next = newNext;
    return newPlayer;

// takes the pointer to the head of a list of players
// prints their names, one per line
// returns the number of players that were printed out
int printPlayers(struct player *playerList) {
    int numPlayers = 0;
    printf("The players remaining in the game are:\n");    
    struct player *curr = playerList;
    while (curr != NULL) {
        //fputs(curr->name, stdout);
        printf("%s\n", curr->name);
        curr = curr->next;
    return numPlayers;

// Insert a newly created player after insertPos in a list
// If the list was empty, return a pointer to the new list
// Otherwise, return insertPos
struct player *insertAfter(struct player *insertPos, char *newName) {
    // create a new player
    struct player *newPlayer = createPlayer(newName, NULL);
    if (insertPos == NULL) {
        // inserting into an empty list
        insertPos = newPlayer;
    } else {
        // inserting into a list that exists
        // set the new player's next to be insertPos' next
        newPlayer->next = insertPos->next;
        // set insertPos' next to aim at the new player
        insertPos->next = newPlayer;
    return insertPos;

// Insert an element into an already alphabetically ordered list
// Will insert into the correct position, then return the head
// of the list, even if it has changed
struct player *insertAlpha(struct player *list, char *newName) {
    // loop through looking for the insertion point
    struct player *curr = list;
    struct player *prev = NULL;
    // stop when we see something that's after us in the alphabet
    while (curr != NULL && strcmp(newName, curr->name) > 0) {        
        prev = curr;
        curr = curr->next;
    // prev now aims at where the insertion should happen
    // Use insertAfter
    struct player *newHead = insertAfter(prev, newName);
    if (prev == NULL) {
        // the new player is the head of the list
        newHead->next = list;        
    } else {
        // the new player is inserted somewhere other than the head
        newHead = list;
    return newHead;

struct player *removePlayer(struct player *list, char *remName) {
    // find the player to remove
    struct player *prev = NULL;
    struct player *curr = list;
    // loop through the list, maintaining a prev pointer
    // stop when you find a name match
    while (curr != NULL && strcmp(remName, curr->name) != 0) {        
        prev = curr;
        curr = curr->next;
    // curr will now point at the node that matched or NULL
    if (curr != NULL) {
        // we found a match, so we'll remove it        
        if (prev == NULL) {
            // the node we're removing is the head of the list
            list = list->next;
        } else {
            // we're removing another element of the list
            prev->next = curr->next;
    return list;

// Loop through the list, freeing all the player nodes
void freePlayerList(struct player *head) {
    while (head != NULL) {
        struct player *remNode = head;
        head = head->next;

Resource created Friday 06 November 2020, 01:20:03 PM.

file: battleRoyale.c

Back to top

COMP1511 20T3 (Programming Fundamentals) is powered by WebCMS3
CRICOS Provider No. 00098G