-
-
Save mycodeschool/7429492 to your computer and use it in GitHub Desktop.
/* 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 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 Nodetraverses 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 Nodetraverses 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
What is the license for this code? Public domain?