Convert a linked list to a string

Related Kata

Although this Kata is not part of an official Series, you may also want to try out Parse a linked list from a string if you enjoyed this Kata.

Preloaded

Preloaded for you is a class, struct or derived data type Node ( depending on the language ) used to construct linked lists in this Kata:

typedef struct node {
  int data;
  struct node *next;
} Node;

      * Defined in the linkage section
       01  node.
           05 val     pic 9(4).
           05 nxt     usage pointer.

class Node {
  public $data, $next;
  public function __construct($data, $next = NULL) {
    $this->data = $data;
    $this->next = $next;
  }
}

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

public class Node {
  public int Data { get; private set; }
  public Node Next { get; private set; }

  public Node(int data, Node next = null) {
    Data = data;
    Next = next;
  }
}

class Node():
    def __init__(self, data, next = None):
        self.data = data
        self.next = next

class Node {
    private int data;
    private Node next;
    
    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }

    public int getData() {
        return data;
    }

    public Node getNext() {
        return next;
    }
}

class Node
  attr_reader :data, :next_node
  
  def initialize(data, next_node=nil)
    @data = data
    @next_node = next_node
  end
end

class Node
{
  public:
    int data;
    Node* next;
  
  Node(int data, Node* next = nullptr)
  {
    this->data = data;
    this->next = next;
  }
};

-- use regular lists, which are already singly-linked
data [a] = [] | a : [a]

typedef struct node {
  int data;
  struct node *next;
} Node;

type Node
  integer :: data
  type(Node), pointer :: next
end type Node

SYMBOL: +nil+
TUPLE: node data next ;
C: <node> node

Prerequisites

This Kata assumes that you are already familiar with the idea of a linked list. If you do not know what that is, you may want to read this article on Wikipedia. Specifically, the linked lists this Kata is referring to are singly linked lists, where the value of a specific node is stored in its data / $data / Data property, the reference to the next node is stored in its next / $next / Next / next_node property and the terminator for a list is null / NULL / None / nil / nullptr / null().

Task

Create a function stringify which accepts an argument list / $list and returns a string representation of the list. The string representation of the list starts with the value of the current Node, specified by its data / $data / Data property, followed by a whitespace character, an arrow and another whitespace character (" -> "), followed by the rest of the list. The end of the string representation of a list must always end with null / NULL / None / nil / nullptr / null() ( all caps or all lowercase depending on the language you are undertaking this Kata in ). For example, given the following list:

&((Node){
  .data = 1,
  .next = &((Node){
    .data = 2,
    .next = &((Node){
      .data = 3,
      .next = NULL
    })
  })
})

new Node(1, new Node(2, new Node(3)))

new Node(1, new Node(2, new Node(3)))

new Node(1, new Node(2, new Node(3)))

Node(1, Node(2, Node(3)))

new Node(1, new Node(2, new Node(3)))

Node.new(1, Node.new(2, Node.new(3)))

new Node(1, new Node(2, new Node(3)))

[1,2,3]

&((Node){
  .data = 1,
  .next = &((Node){
    .data = 2,
    .next = &((Node){
      .data = 3,
      .next = NULL
    })
  })
})

type(Node), pointer :: oneTwoThree
! Where:
! oneTwoThree%data == 1
! oneTwoThree%next%data == 2
! oneTwoThree%next%next%data == 3
! oneTwoThree%next%next%next => null()

1 2 3 +nil+ <node> <node> <node>

       01 node1.
         05 val pic 9(4) value 1.
         05 nxt usage pointer.
       01 node2.
         05 val pic 9(4) value 2.
         05 nxt usage pointer.
       01 node3.
         05 val pic 9(4) value 3.
         05 nxt usage pointer value null.
       ...
       set nxt of node1 to address of node2
       set nxt of node2 to address of node3

... its string representation would be:

"1 -> 2 -> 3 -> null"

"1 -> 2 -> 3 -> NULL"

"1 -> 2 -> 3 -> NULL"

"1 -> 2 -> 3 -> None"

"1 -> 2 -> 3 -> nil"

"1 -> 2 -> 3 -> nullptr"

@"1 -> 2 -> 3 -> NULL"

"1 -> 2 -> 3 -> null()"

"1 -> 2 -> 3 -> +nil+"

       "1 -> 2 -> 3 -> NULL"

And given the following linked list:

new Node(0, new Node(1, new Node(4, new Node(9, new Node(16)))))

Node(0, Node(1, Node(4, Node(9, Node(16)))))

Node.new(0, Node.new(1, Node.new(4, Node.new(9, Node.new(16)))))

[ 0, 1, 4, 9, 16 ]

&((Node){
  .data = 0,
  .next = &((Node){
    .data = 1,
    .next = &((Node){
      .data = 4,
      .next = &((Node){
        .data = 9,
        .next = &((Node){
          .data = 16,
          .next = NULL
        })
      })
    })
  })
})

&((Node){
  .data = 0,
  .next = &((Node){
    .data = 1,
    .next = &((Node){
      .data = 4,
      .next = &((Node){
        .data = 9,
        .next = &((Node){
          .data = 16,
          .next = NULL
        })
      })
    })
  })
})

type(Node), pointer :: list
! Where:
! list%data == 0
! list%next%data == 1
! list%next%next%data == 4
! list%next%next%next%data == 9
! list%next%next%next%next%data == 16
! list%next%next%next%next%next => null()

0 1 4 9 16 +nil+ <node> <node> <node> <node> <node>

       01 node1.
         05 val pic 9(4) value 0.
         05 nxt usage pointer.
       01 node2.
         05 val pic 9(4) value 1.
         05 nxt usage pointer.
       01 node3.
         05 val pic 9(4) value 4.
         05 nxt usage pointer.
       01 node4.
         05 val pic 9(4) value 9.
         05 nxt usage pointer.
       01 node5.
         05 val pic 9(4) value 16.
         05 nxt usage pointer value null.
       ...
       set nxt of node1 to address of node2
       set nxt of node2 to address of node3
       set nxt of node3 to address of node4
       set nxt of node4 to address of node5

... its string representation would be:

"0 -> 1 -> 4 -> 9 -> 16 -> null"

"0 -> 1 -> 4 -> 9 -> 16 -> NULL"

"0 -> 1 -> 4 -> 9 -> 16 -> NULL"

"0 -> 1 -> 4 -> 9 -> 16 -> None"

"0 -> 1 -> 4 -> 9 -> 16 -> nil"

"0 -> 1 -> 4 -> 9 -> 16 -> nullptr"

@"0 -> 1 -> 4 -> 9 -> 16 -> NULL"

"0 -> 1 -> 4 -> 9 -> 16 -> null()"

"0 -> 1 -> 4 -> 9 -> 16 -> +nil+"

       "0 -> 1 -> 4 -> 9 -> 16 -> NULL"

Note that null / NULL / None / nil / nullptr / null() itself is also considered a valid linked list. In that case, its string representation would simply be "null" / "NULL" / "None" / "nil" / "nullptr" / @"NULL" / "null()" ( again, depending on the language ).

For the simplicity of this Kata, you may assume that any Node in this Kata may only contain non-negative integer values. For example, you will not encounter a Node whose data / $data / Data property is "Hello World".

Enjoy, and don't forget to check out my other Kata Series :D