Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Created November 12, 2013 11:38
Star You must be signed in to star a gist
Save mycodeschool/7429492 to your computer and use it in GitHub Desktop.
Doubly Linked List implementation in 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();
}
@deep5050
Copy link

please write some code about circular doubly linked list..

@madogan
Copy link

madogan commented May 11, 2017

Thank you

@LefterisIkaria
Copy link

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

@IT-17005
Copy link

nice

@krizedward
Copy link

nice

@AnjanaSamindraPerera
Copy link

gd work

@Djihanegh
Copy link

thank you good work !

@SanjayBoricha
Copy link

best doubly linked list program

@oguzsk
Copy link

oguzsk commented Nov 27, 2018

where is deletion function?

@ermatesg
Copy link

ermatesg commented Jan 5, 2019

Thank you!

@bashish2711
Copy link

Good work, easy to understand basic concept

Copy link

ghost commented Oct 6, 2019

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

@Aiman-Jannat
Copy link

Easily understandable.Thank You!

@TakbeerAli
Copy link

Thank you

@tridibsamanta
Copy link

tridibsamanta commented Feb 18, 2020

Thanks a ton man !
@mycodeschool

@pratyakshamaheshwari
Copy link

excellent!!

@srivastava006amit
Copy link

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

@IAMNITESHPANDIT
Copy link

best code 👍

@pitargue
Copy link

What is the license for this code? Public domain?

@airglow923
Copy link

airglow923 commented Mar 28, 2021

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).

@amannan-123
Copy link

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.

@airglow923
Copy link

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.

@soda-available
Copy link

thank you very much! understand easily!

@dazzling-prog
Copy link

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

@Manishkip
Copy link

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

@Appamada
Copy link

thanks with all my heart

@tarunmahi
Copy link

tarunmahi commented Jul 1, 2022

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

@functionguyy
Copy link

Thank you so much for this implementation.

@harmsong
Copy link

You are my hero in this field.

@masheitang
Copy link

thanks a lot

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment