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 is very clean and understandable. Thank you for posting it!

This is a clean code. Thanks for sharing.

Nicely written!

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.

only signed up to say this: God bless you

kudos to the "King of the Coding!"

what a great help! God Bless you

i want deleting operation at front, at last, at a position
insertion at a position

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?

Excellent :)

Hi
I seem to have a problem, whenever i try to use:

cellule `*create_NODE(int` x)
{
    cellule *P=(cellule*)malloc(sizeof(cellule));
    if(P==NULL)
    {
        exit(EXIT_FAILURE);
    }
    P->val=x;
    P->nxt=NULL;
    P->prec=NULL;
    return P;
}
cellule `*ADDTOP(cellule*` llist, int x)
{
    cellule `*NW=create_NODE(x);`
    if(llist==NULL)
    {
        llist=NW;
    }
    llist->prec=NW;
    NW->nxt=llist;
    llist=NW;
    return llist;
}

---

but when i used this it works just fine

---

cellule* ADDTOP(cellule *llist, int x)
{
    cellule *NW=(cellule*)malloc(sizeof(cellule));
    if(NW==NULL)
    {
        printf("Error!!");exit(EXIT_FAILURE);
    }
    NW->val=x;
    NW->nxt=llist;
    NW->prec=NULL;
    if(llist)
    {
        llist->prec=NW;
    }
    llist=NW;

    return llist;

}

Thanks in advance;

Thank you very much, this helped me a lot with one of my assignments1

Thank for such a nice code. It is good to understand doubly link list with this code.

Thank you for this awesome piece of code! Makes understanding very easy.

Neat and clean code. Excellent !!!

please write some code about circular doubly linked list..

please write some code about circular doubly linked list..

Thank you

The head pointer change by ref or by value in the InsertAtHead ?

nice

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