Write a C language linked list in an object-oriented style (with code comparison between Python and Java)

Introduction

Recently, I saw two posts saying "I wrote a linked list in C language". All of them were written in C language, so I commented on the object-oriented writing style.

• Linked List Practice Part 1-Qiita
• C language list of numbers using recursive processing and linked list structure --Qiita

I decided to write this article, hoping that writing in an object-oriented style would help my understanding of object-oriented programming. Without the difficult object-oriented concept, we use classes as an extended version of the structure = user-defined type.

Link list

See other articles and sites for linked lists. Reference: https://ja.wikipedia.org/wiki/ Linked list

First, prepare two types of structures to be used for the linked list.

• struct node: List elements
• struct list: Link list management of node

Use the following rules to write in an object-oriented style.

• ** Pointer to struct ** as ** class name ** typedef
• ** Class name ** is ** capitalized ** to specify that it is ** pointer type ** = ** reference type **
• ** Class function names ** start with ** class name and underscore ** to avoid ** name collisions **
• Make the memory acquisition function name ** new **
• The acquired ** individual memory areas ** are called "** instances **".
• Set the ** memory acquisition & initialization function ** of each class to new, this function is called" ** constructor ** "
• ** Constructor ** returns ** instance **
• Functions of ** classes other than constructors ** are called "** methods **"
• Set ** first argument ** of each ** method ** to ** instance **

Function implementation example in C language

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

typedef const char *String;

void *new(size_t size)
{
    void *memory = malloc(size);
    if (memory == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(8);
    }
    return memory;
}

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

Node Node_new(int data)
{
    Node node = new(sizeof(*node));
    node->data = data;
    node->next = NULL;
    return node;
}

void Node_output(Node node, String separator) {
    printf("%d%s", node->data, separator);
}

void Node_free(Node node)
{
    node->next = NULL;
    free(node);
}

/* } */

/*
 * class List {
 */
typedef struct list {
    Node head;
    Node tail;
} *List;

List List_new()
{
    List list = new(sizeof(*list));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

void List_add(List list, int data)
{
    Node node = Node_new(data);
    if (list->head == NULL) {
        list->head = node;
        list->tail = node;
    } else {
        list->tail->next = node;
        list->tail = node;
    }
}

void List_input(List list)
{
    int size;
    if (scanf("%d", &size) != 1) {
        fprintf(stderr, "Invalid size\n");
        exit(1);
    }
    for (int i = 0; i < size; i++) {
        int data;
        if (scanf("%d", &data) != 1) {
            fprintf(stderr, "Invalid data\n");
            exit(2);
        }
        List_add(list, data);
    }
}

void List_output(List list)
{
    for (Node node = list->head; node != NULL; node = node->next) {
        Node_output(node, " ");
    }
    printf("\n");
}

void List_free(List list)
{
    Node node = list->head;
    while (node != NULL) {
        Node next = node->next;
        Node_free(node);  // cannot access node members after here
        node = next;
    }
    list->head = NULL;
    list->tail = NULL;
    free(list);
}

/* } */

int main(void)
{
    List list = List_new();
    List_input(list);
    List_output(list);
    List_free(list);
}

Function implementation example in Python

The differences between C and Python are shown in the table below.

For comparison, we have defined a new class that reserves an empty memory area (instance).

class new:
    pass

#
# class Node {
#/
def Node_new(data):
    node = new()
    node.data = data
    node.next = None
    return node

def Node_output(node, separator):
    print(node.data, end=separator)

# }

#
# class List {
#/
def List_new():
    list = new()
    list.head = None
    list.tail = None
    return list

def List_add(list, data):
    node = Node_new(data)
    if list.head is None:
        list.head = node
        list.tail = node
    else:
        list.tail.next = node
        list.tail = node

def List_input(list):
    size = int(input())  #Not used in Python
    for data in input().split():
        List_add(list, int(data))

def List_output(list):
    node = list.head
    while node is not None:
        Node_output(node, " ")
        node = node.next
    print()

# }

def main():
    list = List_new()
    List_input(list)
    List_output(list)
    del list

if __name__ == '__main__':
    main()

Class implementation example in Python

By defining Node and List as classes, memory is allocated for each class, eliminating the need for the new class. The initialization process is written in the __init __ method. After the constructor allocates memory, it will be called automatically.

A namespace is created by defining a class, and even if the name conflicts with a function of another class, each function defined in the class can be used as a different function, so "** class name and underscore **" Remove.

I wrote class name_method name (instance, other arguments) If you write instance.method (other argument), It calls class name.method name (instance, other arguments).

It is customary to name the instance variable as the first argument of the method to self.

class Node:

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

    def output(self, separator):
        print(self.data, end=separator)


class List:

    def __init__(self):
        self.head = None
        self.tail = None

    def add(self, data):
        node = Node(data)
        if self.head is None:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def input(self):
        size = int(input())  #Not used in Python
        for data in input().split():
            self.add(int(data))

    def output(self):
        node = self.head
        while node is not None:
            node.output(" ")
            node = node.next
        print()


def main():
    list = List()
    list.input()
    list.output()
    del list

if __name__ == '__main__':
    main()

Class implementation example in Java

The basic grammar is the same as C language. Think of a class as an extended version of a struct. You can write function definitions in the structure and freely define members and methods without worrying about name conflicts with other classes. The instance argument of the first argument of the method does not need to be described, and the implicit first argument this is automatically defined and the instance is assigned. The same method as the class name will be the constructor. Since the instance this is implicitly defined, there is no need to describe the return value type or return. scanf is replaced by the Scanner class.

LinkedList.java

import java.util.Scanner;

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }

    void output(String separator) {
        System.out.print(this.data + separator);
    }
}

class List {
    Node head;
    Node tail;

    List() {
        this.head = null;
        this.tail = null;
    }

    void add(int data) {
        Node node = new Node(data);
        if (this.head == null) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
    }

    void input() {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        for (int i = 0; i < size; i++) {
            int data = scanner.nextInt();
            add(data);
        }
    }

    void output() {
        for (Node node = this.head; node != null; node = node.next) {
            node.output(" ");
        }
        System.out.print("\n");
    }
}

public class LinkedList {
    public static void main(String[] args) {
        List list = new List();
        list.input();
        list.output();
    }
}