Data Structures 03 - Doubly Linked List

#include <stdio.h>
#include <malloc.h>

// Define the node structure for a doubly linked list
typedef struct DoubleLinkedNode {
	char data; // Data stored in the node
	struct DoubleLinkedNode *previous; // Pointer to the previous node
	struct DoubleLinkedNode *next; // Pointer to the next node
} DLNode, *DLNodePtr;

// Initialize the doubly linked list and create a head node
DLNodePtr initLinkList() {
	DLNodePtr tempHeader = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode));
	tempHeader->data = '\0'; // Head node data is null
	tempHeader->next = NULL; // Head node's next pointer is null
	tempHeader->previous = NULL; // Head node's previous pointer is null
	return tempHeader; // Return head node
}

// Print the contents of the doubly linked list
void printList(DLNodePtr paraHeader) {
	DLNodePtr p = paraHeader->next; // Start from the node after the head node
	while (p != NULL) {
		printf("%c", p->data); // Print current node's data
		p = p->next; // Move to the next node
	}
	printf("\r\n"); // Print newline
}

// Insert an element at the specified position in the doubly linked list
void insertElement(DLNodePtr paraHeader, char paraChar, int paraPosition) {
	DLNodePtr p, q, r;
	p = paraHeader;
	for (int i = 0; i < paraPosition; i++) {
		p = p->next;
		if (p == NULL) {
			printf("The position %d is beyond the scope of the list.", paraPosition);
			return;
		}
	}
	q = (DLNodePtr)malloc(sizeof(struct DoubleLinkedNode)); // Create new node
	q->data = paraChar; // Set new node's data
	r = p->next; // r points to the node after p's current next
	q->next = p->next; // New node's next points to p's next node
	q->previous = p; // New node's previous points to p
	p->next = q; // p's next points to the new node
	if (r != NULL) {
		r->previous = q; // If r is not null, set r's previous to point to the new node
	}
}

// Delete a specified element from the doubly linked list
void deleteElement(DLNodePtr paraHeader, char paraChar) {
	DLNodePtr p, q, r;
	p = paraHeader;
	while ((p->next != NULL) && (p->next->data != paraChar)) {
		p = p->next;
	}
	if (p->next == NULL) {
		printf("The char '%c' does not exist.\r\n", paraChar);
		return;
	}
	q = p->next; // q points to the node to be deleted
	r = q->next; // r points to the node after q
	p->next = r; // p's next points to r
	if (r != NULL) {
		r->previous = p; // If r is not null, set r's previous to point to p
	}
	free(q); // Free memory occupied by node q
}

// Test insertion and deletion functions
void insertDeleteTest() {
	DLNodePtr tempList = initLinkList(); // Initialize linked list
	printList(tempList); // Print linked list
	// Insert elements
	insertElement(tempList, 'H', 0);
	insertElement(tempList, 'e', 1);
	insertElement(tempList, 'l', 2);
	insertElement(tempList, 'l', 3);
	insertElement(tempList, 'o', 4);
	insertElement(tempList, '!', 5);
	printList(tempList); // Print linked list
	// Delete elements
	deleteElement(tempList, 'e');
	deleteElement(tempList, 'a'); // This element does not exist
	deleteElement(tempList, 'o');
	printList(tempList); // Print linked list
	insertElement(tempList, 'o', 1); // Insert element again
	printList(tempList); // Print linked list
}

// Test node addresses
void basicAddressTest() {
	DLNode tempNode1, tempNode2;

	tempNode1.data = 4; // Set node 1's data
	tempNode1.next = NULL; // Node 1's next pointer is null

	tempNode2.data = 6; // Set node 2's data
	tempNode2.next = NULL; // Node 2's next pointer is null

	// Print node address information
	printf("The first node: %p, %p, %p\r\n",
		&tempNode1, &tempNode1.data, &tempNode1.next);
	printf("The second node: %p, %p, %p\r\n",
		&tempNode2, &tempNode2.data, &tempNode2.next);

	tempNode1.next = &tempNode2; // Set node 1's next to point to node 2
}

int main() {
	insertDeleteTest(); // Run insertion and deletion tests
	basicAddressTest(); // Run address test
	return 0;
}

Running Result