Urpagin · October 9, 2025 02:11 · Urpagin · Oct 9, 2025
diff --git a/dll.c b/dll.c
 #if 0
    TMP=$(mktemp -d)
    clang -Wall -Wextra -pedantic -o ${TMP}/a.out ${0} && ${TMP}/a.out ${@:1} ; RV=$?
    rm -rf ${TMP}
    exit ${RV}
 #endif

 /// Metadata
 /// Author: Urpagin
 /// Date: 2025-10-09 @ 02:54AM
 /// Description: An attempt at creating a doubly-linked list from memory in pure C.
 ///
 /// Words I use frequently: 'DLL': Doubly-Linked List
 /// and 'Super': the struct that holds some metadata over the nodes, see it as the 
 /// list itself, the wrapper.
 ///
 ///
 /// Program execution: have clang, have the execution perm on the source file and just `./dll.c`.
 /// Thanks to the pretty shebang on lines 0..=6.


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

 // TODO: Implement pop() function.
 // TODO: Implement get() function.
 // TODO: Implement set() function.
 // TODO: Play with it and also implement other primitives I'm sure I forgot.


 /// One node of our DLL that holds the value and the next and previous node.
 /// prev and next can be NULL in case there is no next or previous node (e.g., tail and head nodes).
 struct DllNode {
    void *val;
    struct DllNode *next;
    struct DllNode *prev;
 };

 /// The "superstruct" that will hold a bit of metadata of our Doubly-Linked List.
 /// - the head node (beginning)
 /// - the tail node (end)
 /// - (optional) the lenghth of our list
 struct Dll {
    struct DllNode* head;
    struct DllNode* tail;
    size_t len;
 };

 /// Returns an empty doubly-linked list.
 struct Dll *dll_make_empty(void) {
    struct Dll *dll_ptr = (struct Dll *)malloc(sizeof(struct Dll));
    struct DllNode *node_ptr = (struct DllNode *)malloc(sizeof(struct DllNode));
    node_ptr->prev = NULL;
    node_ptr->next = NULL;

    // link the initial node with the superstruct.
    dll_ptr->head = node_ptr;
    dll_ptr->tail = node_ptr;
    dll_ptr->len = 0;

    return dll_ptr;
 }


 /// Creates a DLL node initialised with a value and allocated memory.
 /// This node is not linked (I would like call it an orphan?).
 struct DllNode* dll_make_orphan(void* item) {
    struct DllNode* node = (struct DllNode*)malloc(sizeof(struct DllNode));
    node->val = item;
    node->prev = NULL;
    node->next = NULL;
    return node;
 }


 /// Appends a new item at the very end of the doubly-linked list.
 /// dll should be the first node.
 /// item should be the item to append to the DLL.
 void dll_append(struct Dll* super, void* item) {
    struct DllNode* dll = super->head;

    // Super hasn't yet been initialized
    // In other words: this is appending an item in an EMPTY list.
    if (!super->len) {
        dll->val = item;
        super->len++;
        return;
    }

    // Go to the final node
    while (dll->next != NULL)
        dll = dll->next;

    // Link our new node
    struct DllNode* new_node = dll_make_orphan(item);

    dll->next = new_node;
    new_node->prev = dll;

    // update super
    super->tail = new_node;
    super->len++;
 }


 /// Displays each element of the DLL.
 /// The DLL must contain ints, else it won't work.
 void dll_display_int(struct Dll* dll) {

    if (!dll->len) {
        printf("DLL is uninitialized\n");
        return;
    }


    struct DllNode* node = dll->head;
    printf("[");

    for (;;) {
        printf("%d", *(int*)node->val);
        if (node->next != NULL)
            printf(", ");
        if (node == dll->tail) {
            break;
        }
        node = node->next;
    }

    printf("]\n");
 }


 /// Frees each node and super.
 void dll_free(struct Dll* dll) {
    struct DllNode* node = dll->head;
    while (node->next != NULL) {
        node = node->next;
        free(node->prev);
    }
    // Free the last one with next == NULL.
    free(node);
    // Finally, free the super wrapper.
    free(dll);
 }

 int main(void) {
    printf("[Start Of Program]\n");

    // Initialize some dummy values on the stack
    // to then populate our list.
    int item = 10;
    int a, b, c = 69;
    int olaaa = 1337;

    // Create an empty Doubly-Linked List
    struct Dll* dll = dll_make_empty();

    // Populate the DLL with the dummy values.
    dll_append(dll, &item);
    dll_append(dll, &a);
    dll_append(dll, &b);
    dll_append(dll, &c);
    dll_append(dll, &olaaa);

    // print the list
    dll_display_int(dll);


    // Good practice to free (even if it's the end of the program)
    dll_free(dll);

    return 0;
 }
	#if 0
	TMP=$(mktemp -d)
	clang -Wall -Wextra -pedantic -o ${TMP}/a.out ${0} && ${TMP}/a.out ${@:1} ; RV=$?
	rm -rf ${TMP}
	exit ${RV}
	#endif

	/// Metadata
	/// Author: Urpagin
	/// Date: 2025-10-09 @ 02:54AM
	/// Description: An attempt at creating a doubly-linked list from memory in pure C.
	///
	/// Words I use frequently: 'DLL': Doubly-Linked List
	/// and 'Super': the struct that holds some metadata over the nodes, see it as the
	/// list itself, the wrapper.
	///
	///
	/// Program execution: have clang, have the execution perm on the source file and just `./dll.c`.
	/// Thanks to the pretty shebang on lines 0..=6.


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

	// TODO: Implement pop() function.
	// TODO: Implement get() function.
	// TODO: Implement set() function.
	// TODO: Play with it and also implement other primitives I'm sure I forgot.


	/// One node of our DLL that holds the value and the next and previous node.
	/// prev and next can be NULL in case there is no next or previous node (e.g., tail and head nodes).
	struct DllNode {
	void *val;
	struct DllNode *next;
	struct DllNode *prev;
	};

	/// The "superstruct" that will hold a bit of metadata of our Doubly-Linked List.
	/// - the head node (beginning)
	/// - the tail node (end)
	/// - (optional) the lenghth of our list
	struct Dll {
	struct DllNode* head;
	struct DllNode* tail;
	size_t len;
	};

	/// Returns an empty doubly-linked list.
	struct Dll *dll_make_empty(void) {
	struct Dll dll_ptr = (struct Dll )malloc(sizeof(struct Dll));
	struct DllNode node_ptr = (struct DllNode )malloc(sizeof(struct DllNode));
	node_ptr->prev = NULL;
	node_ptr->next = NULL;

	// link the initial node with the superstruct.
	dll_ptr->head = node_ptr;
	dll_ptr->tail = node_ptr;
	dll_ptr->len = 0;

	return dll_ptr;
	}


	/// Creates a DLL node initialised with a value and allocated memory.
	/// This node is not linked (I would like call it an orphan?).
	struct DllNode* dll_make_orphan(void* item) {
	struct DllNode* node = (struct DllNode*)malloc(sizeof(struct DllNode));
	node->val = item;
	node->prev = NULL;
	node->next = NULL;
	return node;
	}


	/// Appends a new item at the very end of the doubly-linked list.
	/// dll should be the first node.
	/// item should be the item to append to the DLL.
	void dll_append(struct Dll* super, void* item) {
	struct DllNode* dll = super->head;

	// Super hasn't yet been initialized
	// In other words: this is appending an item in an EMPTY list.
	if (!super->len) {
	dll->val = item;
	super->len++;
	return;
	}

	// Go to the final node
	while (dll->next != NULL)
	dll = dll->next;

	// Link our new node
	struct DllNode* new_node = dll_make_orphan(item);

	dll->next = new_node;
	new_node->prev = dll;

	// update super
	super->tail = new_node;
	super->len++;
	}


	/// Displays each element of the DLL.
	/// The DLL must contain ints, else it won't work.
	void dll_display_int(struct Dll* dll) {

	if (!dll->len) {
	printf("DLL is uninitialized\n");
	return;
	}


	struct DllNode* node = dll->head;
	printf("[");

	for (;;) {
	printf("%d", (int)node->val);
	if (node->next != NULL)
	printf(", ");
	if (node == dll->tail) {
	break;
	}
	node = node->next;
	}

	printf("]\n");
	}


	/// Frees each node and super.
	void dll_free(struct Dll* dll) {
	struct DllNode* node = dll->head;
	while (node->next != NULL) {
	node = node->next;
	free(node->prev);
	}
	// Free the last one with next == NULL.
	free(node);
	// Finally, free the super wrapper.
	free(dll);
	}

	int main(void) {
	printf("[Start Of Program]\n");

	// Initialize some dummy values on the stack
	// to then populate our list.
	int item = 10;
	int a, b, c = 69;
	int olaaa = 1337;

	// Create an empty Doubly-Linked List
	struct Dll* dll = dll_make_empty();

	// Populate the DLL with the dummy values.
	dll_append(dll, &item);
	dll_append(dll, &a);
	dll_append(dll, &b);
	dll_append(dll, &c);
	dll_append(dll, &olaaa);

	// print the list
	dll_display_int(dll);


	// Good practice to free (even if it's the end of the program)
	dll_free(dll);

	return 0;
	}
No results found