// A demo of reversing a linked list

// This demo will show a possible procedural implementation
// of printing out the data from a linked list in reverse

// It will also show a recursive implementation

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

#include <stdio.h>
#include <stdlib.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);
void reversePrint(struct player *playerList);
struct player *printBefore(struct player *playerList, struct player *after);
void revPrintRec(struct player *playerList);

int main(void) {
    // create a list of players
    // In a game, we'd expect this list to be created during the game based
    // on who was knocked out
    struct player *list = NULL;
    list = createPlayer("Marc", list);
    list = createPlayer("Zuko", list);
    list = createPlayer("Katara", list);
    list = createPlayer("Chicken", list);
    list = createPlayer("Aang", list);
    struct player *prev = NULL;
    if (prev != NULL && prev->next == NULL) {

// 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;

// Go through a list in reverse order and print it out
void reversePrint(struct player *playerList) {
    struct player *end = NULL;
    // Call printBefore repeatedly until end
    // returns to the start of the list
    while (end != playerList) {
        end = printBefore(playerList, end);

// print out the node in a list that's just before "after"
// return a pointer to the node that we just printed
struct player *printBefore(struct player *playerList, struct player *after) {
    // loop until after, keeping prev as the node before
    struct player *curr = playerList;
    struct player *prev = NULL;
    while (curr != after) {
        prev = curr;
        curr = curr->next;
    // prev is now pointed at the element just before after
    if (prev != NULL) {
        // print out the name in prev
        fputs(prev->name, stdout);
    return prev;

// print a linked list in reverse
// This is the recursive version
void revPrintRec(struct player *playerList) {    
    if (playerList == NULL) {
        // stopping case: if the list is empty
    } else {
        // going case: head prints last, 
        // the rest of the list prints out before that
        //fputs(playerList->name, stdout);
        printf("%s\n", playerList->name);

Resource created Friday 13 November 2020, 01:54:17 PM.

file: reverseList.c

Back to top

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