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();
	
}

nice

gd work

thank you good work !

best doubly linked list program

where is deletion function?

Thank you!

Good work, easy to understand basic concept

I faced a lot of problems in implementation of linked list in c ... whatever resource I explore , everywhere the implementation is different and complex at the same time ... but this is quite unambiguous ... thanks a lot ...

Easily understandable.Thank You!

Thank you

Thanks a ton man !
@mycodeschool

excellent!!

I just happened upon you're code after googling "doubly linked list". I'm implementing my own doubly linked list for an open source project and I'm too lazy to pull out a piece of paper to draw a picture, thus seeing someone else's implementation is quite helpful.

I hope you don't mind me pointing out a small (could be huge) problem, that most casual programmers can usually ignore.

Your code causes a memory leak. This is due to using malloc in the function GetNewNode, but the allocated memory isn't freed in the end. At program termination, the memory is freed automatically...so it really doesn't matter with the small example you've given. On the other hand, if I edited the main function to insert an integer in a for loop with lots of iterations, this could starve the computer of memory resources until the program terminates.

This is evident by the output of program, valgrind, below:

$ valgrind --leak-check=full --show-leak-kinds=all ./list
==10234== Memcheck, a memory error detector
==10234== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==10234== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==10234== Command: ./list
==10234==
Forward: 2
Reverse: 2
Forward: 2 4
Reverse: 4 2
Forward: 6 2 4
Reverse: 4 2 6
Forward: 6 2 4 8
Reverse: 8 4 2 6
==10234==
==10234== HEAP SUMMARY:
==10234== in use at exit: 96 bytes in 4 blocks
==10234== total heap usage: 4 allocs, 0 frees, 96 bytes allocated
==10234==
==10234== 24 bytes in 1 blocks are still reachable in loss record 1 of 4
==10234== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10234== by 0x4005E1: GetNewNode (in /home/user/list/list)
==10234== by 0x400689: InsertAtTail (in /home/user/list/list)
==10234== by 0x4007CC: main (in /home/user/list/list)
==10234==
==10234== 24 bytes in 1 blocks are still reachable in loss record 2 of 4
==10234== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10234== by 0x4005E1: GetNewNode (in /home/user/list/list)
==10234== by 0x400689: InsertAtTail (in /home/user/list/list)
==10234== by 0x4007EA: main (in /home/user/list/list)
==10234==
==10234== 24 bytes in 1 blocks are still reachable in loss record 3 of 4
==10234== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10234== by 0x4005E1: GetNewNode (in /home/user/list/list)
==10234== by 0x400621: InsertAtHead (in /home/user/list/list)
==10234== by 0x400808: main (in /home/user/list/list)
==10234==
==10234== 24 bytes in 1 blocks are still reachable in loss record 4 of 4
==10234== at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==10234== by 0x4005E1: GetNewNode (in /home/user/list/list)
==10234== by 0x400689: InsertAtTail (in /home/user/list/list)
==10234== by 0x400826: main (in /home/user/list/list)
==10234==
==10234== LEAK SUMMARY:
==10234== definitely lost: 0 bytes in 0 blocks
==10234== indirectly lost: 0 bytes in 0 blocks
==10234== possibly lost: 0 bytes in 0 blocks
==10234== still reachable: 96 bytes in 4 blocks
==10234== suppressed: 0 bytes in 0 blocks
==10234==
==10234== For counts of detected and suppressed errors, rerun with: -v
==10234== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

To fix this, a minor edit to the ReversePrint function to free each node can fix this.

Again, hope you don't mind me pointing this out. I only wrote this for some poor undergrad or amateur programmer who happened upon this source code.

I agree. Well observed !!

best code 👍

What is the license for this code? Public domain?

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 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!!