Created
November 12, 2013 11:38
-
-
Save mycodeschool/7429492 to your computer and use it in GitHub Desktop.
Doubly Linked List implementation in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* 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(); | |
} |
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Yes, you are right. I thought constant time complexity is part of requirements for a doubly linked list. Sorry for the confusion.