Doubly Linked List implementation in C

DoublyLinkedList.c

/* Doubly Linked List implementation */
#include<stdio.h>
#include<stdlib.h>

struct Node  {
	int data;
	struct Node* next;
	struct Node* prev;
};

struct Node* head; // global variable - pointer to head node.

//Creates a new Node and returns pointer to it. 
struct Node* GetNewNode(int x) {
	struct Node* newNode
		= (struct Node*)malloc(sizeof(struct Node));
	newNode->data = x;
	newNode->prev = NULL;
	newNode->next = NULL;
	return newNode;
}

//Inserts a Node at head of doubly linked list
void InsertAtHead(int x) {
	struct Node* newNode = GetNewNode(x);
	if(head == NULL) {
		head = newNode;
		return;
	}
	head->prev = newNode;
	newNode->next = head; 
	head = newNode;
}

//Inserts a Node at tail of Doubly linked list
void InsertAtTail(int x) {
	struct Node* temp = head;
	struct Node* newNode = GetNewNode(x);
	if(head == NULL) {
		head = newNode;
		return;
	}
	while(temp->next != NULL) temp = temp->next; // Go To last Node
	temp->next = newNode;
	newNode->prev = temp;
}

//Prints all the elements in linked list in forward traversal order
void Print() {
	struct Node* temp = head;
	printf("Forward: ");
	while(temp != NULL) {
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

//Prints all elements in linked list in reverse traversal order. 
void ReversePrint() {
	struct Node* temp = head;
	if(temp == NULL) return; // empty list, exit
	// Going to last Node
	while(temp->next != NULL) {
		temp = temp->next;
	}
	// Traversing backward using prev pointer
	printf("Reverse: ");
	while(temp != NULL) {
		printf("%d ",temp->data);
		temp = temp->prev;
	}
	printf("\n");
}

int main() {

	/*Driver code to test the implementation*/
	head = NULL; // empty list. set head as NULL. 
	
	// Calling an Insert and printing list both in forward as well as reverse direction. 
	InsertAtTail(2); Print(); ReversePrint();
	InsertAtTail(4); Print(); ReversePrint();
	InsertAtHead(6); Print(); ReversePrint();
	InsertAtTail(8); Print(); ReversePrint();
	
}

This data structure is not a doubly linked list since it does not provide O(1) when inserting node at tail.

This line:

	while(temp->next != NULL) temp = temp->next; // Go To last Node

traverses through the entire nodes to reach the tail, which is O(n), not O(1).

This is Doubly Linked List...
To get O(1), you need to create additional pointer named tail.

This data structure is not a doubly linked list since it does not provide O(1) when inserting node at tail.
This line:

	while(temp->next != NULL) temp = temp->next; // Go To last Node

traverses through the entire nodes to reach the tail, which is O(n), not O(1).

This is Doubly Linked List...
To get O(1), you need to create additional pointer named tail.

Yes, you are right. I thought constant time complexity is part of requirements for a doubly linked list. Sorry for the confusion.

thank you very much! understand easily!

Quick question, when inserting at the tail why not use head->prev instead of iteration. Doubly linked makes tail insertion much faster this way right? Or have I made a wrong assumption?

because head->prev will always point to NULL

This code is clear and understandable, thanks for the code. Its helping me to learn more clearly.

thanks with all my heart

i have added delete function too.. if anyone wants it hop onto my repository... I have posted link to the file here double linked list

Thank you so much for this implementation.

You are my hero in this field.

thanks a lot

good luck

thanks,my teacher

Anyone knows about how to reverse the doubly linked list?

My code:
struct List* Reverse_Recursion(List* head)
{
if (head == nullptr || head->next == nullptr)
return head;

List* newHead = Reverse_Recursion(head->next);
head->next->next = head;
head->prev = head->next;
head->next = nullptr;

return newHead;

}

didn't work at all!!