[Header File] Doubly Linked LIst Implementation

dll.h

#ifndef DLL_H
#define DLL_H

#include<stdlib.h>

typedef ... data_t;

/* Node of a DLL */
typedef struct DLLNode
{
	data_t data;
	struct DLLNode *next;
	struct DLLNode *prev;
} DLLNode;

/* Initialize DLL */
// make global const head node
DLLNode *head = NULL;

/* Insert a new node on the front of DLL */
void prepend(data_t newData)
{
	/* 1. Allocate Node */
	DLLNode *newNode = (DLLNode*) malloc(sizeof(DLLNode));

	/* 2. Put in the data */
	newNode->data = newData;

	/* 3. Make next of new node as head and prev is NULL */
	newNode->next = head;
	newNode->prev = NULL;

	/* 4. Change prev head of head node to new node */
	if (head != NULL)
	{
		head->prev = newNode;
	}

	/* 5. Make the head again */
	head = newNode;
}

/* Append a new node at the end */
void append(data_t newData)
{
	/* 1. Allocate mode */
	DLLNode *newNode = (DLLNode*) malloc(sizeof(DLLNode));
	
	/* 2. Put in the data */
	newNode->data = newData;

	/* 3. This node is gonna be last node, so make it next NULL */
	newNode->next = NULL;

	/* 4. If DLL is empty, then make new node as head */
	if (head == NULL)
	{
		newNode->prev = NULL;
		head = newNode;

		return; // use in void means: function stop here
		// it will NOT go to step 5
	}

	/* 5. Else traverse till the last node */
	DLLNode *tail = head;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}

	/* Change the next of last node */
	tail->next = newNode;

	/* Make last node as prev of newNode */
	newNode->prev = tail;

	return;
}

/* Insert new node after a given node (prevNode) */
void insertAfter(DLLNode *prevNode, data_t newData)
{
	/* 1. check if the given prev is NULL */
	if (prevNode == NULL)
	{
		printf("The given previous node cannot be NULL.\n");
		return;
	}

	/* 2. Allocate new node */
	DLLNode *newNode = (DLLNode*) malloc(sizeof(DLLNode));

	/* 3. Put in the data */
	newNode->data = newData;

	/* 4. Make next of new node as next of prevNode */
	newNode->next = prevNode->next;

	/* 5. Make next of prevNode as newNode */
	prevNode->next = newNode;

	/* 6. Make prevNode as previous of newNode */
	newNode->prev = prevNode;

	/* 7. Change previous of newNode's next mode */
	if (newNode->next != NULL)
	{
		newNode->next->prev = newNode;
	}
}

/* Insert new node befor a given node (nextNode) */
void insertBefore(DLLNode *nextNode, data_t newData)
{
	/* 1. check if the given next is NULL */
	if (nextNode == NULL)
	{
		printf("The given next node cannot be NULL.\n");
		return;
	}

	/* 2. Allocate new node */
	DLLNode *newNode = (DLLNode*) malloc(sizeof(DLLNode));

	/* 3. Put in the data */
	newNode->data = newData;

	/* 4. Make prev of new node as prev of nextNode */
	newNode->prev = nextNode->prev;

	/* 5. Make prev of nextNode as newNode */
	nextNode->prev = newNode;

	/* 6. Make nextNode as next of newNode */
	newNode->next = nextNode;

	/* 7. Change next of newNode's prev mode */
	if (newNode->prev != NULL)
	{
		newNode->prev->next = newNode;
	}
}

/* Delete a nod form DLL */
// *del: pointer to node to be deleted
void delete(DLLNode *del)
{
	// base case
	if (head == NULL || del == NULL)
		return;

	/* If node to be deleted is head node */
	if (head == del)
	{
		head = del->next;
	}

	/* Change next only if node to be deleted is NOT the tail node */
	if (del->next != NULL)
	{
		del->next->prev = del->prev;
	}

	/* Change prev only if node to be deleted is NOT the head node */
	if(del->prev != NULL)
	{
		del->prev->next = del->next;
	}

	/* Finally, free the memory occupied by del */
	free(del);
	return;
}

///// Utility to print DLL
void display()
{
	DLLNode *cur = head;

	// foward direction
	while (cur != NULL)
	{
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

#endif