Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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();
}
@cameronellis

This comment has been minimized.

Copy link

cameronellis commented Sep 10, 2015

This is very clean and understandable. Thank you for posting it!

@sayem612

This comment has been minimized.

Copy link

sayem612 commented Oct 11, 2015

This is a clean code. Thanks for sharing.

@JuanbiB

This comment has been minimized.

Copy link

JuanbiB commented Nov 16, 2015

Nicely written!

@rickyefarr

This comment has been minimized.

Copy link

rickyefarr commented Feb 14, 2016

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.

@rev118588

This comment has been minimized.

Copy link

rev118588 commented May 14, 2016

only signed up to say this: God bless you

@learning-dev

This comment has been minimized.

Copy link

learning-dev commented Jul 3, 2016

kudos to the "King of the Coding!"

@chinmayyande

This comment has been minimized.

Copy link

chinmayyande commented Aug 10, 2016

what a great help! God Bless you

@teja1600

This comment has been minimized.

Copy link

teja1600 commented Aug 17, 2016

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

@karbfg10k

This comment has been minimized.

Copy link

karbfg10k commented Aug 24, 2016

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?

@Ganeshbg

This comment has been minimized.

Copy link

Ganeshbg commented Nov 26, 2016

Excellent :)

@SalahHamza

This comment has been minimized.

Copy link

SalahHamza commented Dec 22, 2016

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;

@coredamnwork

This comment has been minimized.

Copy link

coredamnwork commented Feb 26, 2017

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

@bhavikbhansali

This comment has been minimized.

Copy link

bhavikbhansali commented Mar 3, 2017

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

@bitnahian

This comment has been minimized.

Copy link

bitnahian commented Apr 3, 2017

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

@Praveer1981

This comment has been minimized.

Copy link

Praveer1981 commented Apr 25, 2017

Neat and clean code. Excellent !!!

@deep5050

This comment has been minimized.

Copy link

deep5050 commented Apr 26, 2017

please write some code about circular doubly linked list..

@deep5050

This comment has been minimized.

Copy link

deep5050 commented Apr 26, 2017

please write some code about circular doubly linked list..

@madogan

This comment has been minimized.

Copy link

madogan commented May 11, 2017

Thank you

@LefterisIkaria

This comment has been minimized.

Copy link

LefterisIkaria commented Dec 1, 2017

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

@IT-17005

This comment has been minimized.

Copy link

IT-17005 commented Feb 17, 2018

nice

@krizedward

This comment has been minimized.

Copy link

krizedward commented Apr 5, 2018

nice

@AnjanaSamindraPerera

This comment has been minimized.

Copy link

AnjanaSamindraPerera commented May 8, 2018

gd work

@Djihanegh

This comment has been minimized.

Copy link

Djihanegh commented Sep 21, 2018

thank you good work !

@SanjayBoricha

This comment has been minimized.

Copy link

SanjayBoricha commented Nov 26, 2018

best doubly linked list program

@oguzsk

This comment has been minimized.

Copy link

oguzsk commented Nov 27, 2018

where is deletion function?

@ermatesg

This comment has been minimized.

Copy link

ermatesg commented Jan 5, 2019

Thank you!

@bashish2711

This comment has been minimized.

Copy link

bashish2711 commented Jul 29, 2019

Good work, easy to understand basic concept

@devparkk

This comment has been minimized.

Copy link

devparkk 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

This comment has been minimized.

Copy link

Aiman-Jannat commented Oct 30, 2019

Easily understandable.Thank You!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.