Friends!
We all know how to deal with Singly and Doubly linked list.
Now here I tried to put some differences which will help you to take decisions on the choice of using linked list type in your implementation.
Your inputs are welcome to make this increase the number of differences.
| S.No. | Singly Linked List | Doubly Linked List |
| 1 | Singly linked list allows you to go one way direction | Doubly linked list has two way directions next and previous |
| 2 | Singly linked list uses less memory per node (one pointer) | Doubly linked list uses More memory per node than Singly Linked list (two pointers) |
| 3 | There is a little-known trick that lets you delete from a singly-linked list in O(1), but the list must be circular for it to work (move the content of next into the current, and delete next). | Doubly-linked lists can be used in places where singly-linked lists would not work (a doubly-ended queue), but they require slightly more "housekeeping", and are slightly less efficient on insertions as the result |
| 4 | Complexity of Insertion and Deletion at known position is O (n). | Complexity of Insertion and Deletion at known position is O (1). |
| 5 | If we need to save memory in need to update node values frequently and searching is not required, we can use Singly Linked list. | If we need faster performance in searching and memory is not a limitation we use Doubly Linked List |
| 6 | For B-Tree, Heap we need doubly linked list. .Net Framework only provides the LinkedList<T> class which is double-linked. | |
| 7 | If we know in advance that element to be searched is found near the end of the list(for example name 'Yogesh' in a telephone directory), even then singly linked list is traversed sequentially from beginning. | In doubly linked list If we know in advance that element to be searched is found near the end of the list(for example name 'Yogesh' in a telephone directory), then the list can traversed from the end thereby saving time |
| 8 | In single list Each node
contains at least two parts: a) info b) link |
In doubly linked list Each
node contains at least three parts: a) info b) link to next node c) link to previous node |
Cheers!
If we know in advance that element to be searched is found near the end of the list(for example name 'Yogesh' in a telephone directory), even then singly linked list is traversed sequentially from beginning. but in doubly linked list If we know in advance that element to be searched is found near the end of the list(for example name 'Yogesh' in a telephone directory), then the list can traversed from the end thereby saving time.
ReplyDeleteDifference Between Singly Linked List And Doubly Linked List >>>>> Download Now
Delete>>>>> Download Full
Difference Between Singly Linked List And Doubly Linked List >>>>> Download LINK
>>>>> Download Now
Difference Between Singly Linked List And Doubly Linked List >>>>> Download Full
>>>>> Download LINK rx
in single list Each node contains at least two parts:
ReplyDeletea) info
b) link
in doubly linked list Each node contains at least three parts:
a) info
b) link to next node
c) link to previous node
Thanks for your inputs. I have incorporated your suggestions.
ReplyDeletethnx....
ReplyDeleteThanks
ReplyDeletecan we delete a last node from a singly linklist
ReplyDeleteyes we can
Deleteyes we can
DeleteThis comment has been removed by the author.
ReplyDeleteNode current = this.head;
ReplyDeletefor (int i = 0; i < this.count-1; i++)
current = current.Next;
var result = current.Data;
current.Data = null;
count--;
return result;
Thanks for helping.
ReplyDeleteWhat does O(n) mean in the above difference 3 of lists??
ReplyDeletegood information for beginner like me
ReplyDeleteWrong information.
ReplyDeleteAccording to your chart,
Singly Linked List
Complexity of Insertion and Deletion at known position is O (n).
Doubly Linked List
Complexity of Insertion and Deletion at known position is O (1).
It should O(n) even it is Doubly Linked List or Singly Linked List
SINGLE LINK LIST PROGRAM->
ReplyDelete#include
using namespace std;
class data
{
int roll;
char name[20];
int age;
public:
data *n;
int rroll()
{
return roll;
}
void accept()
{
cout<<"Enter Roll Number: ";
cin>>roll;
cout<<"Enter Name : ";
cin>>name;
cout<<"Enter Age : ";
cin>>age;
}
void disp()
{
cout<<"Roll Number is: "<accept();
ne->n=NULL;
if(s==NULL)
{
s=ne;
}
else
{
for(ptr=s;ptr!=NULL && ne->rroll() > ptr->rroll();prev=ptr,ptr=ptr->n);
if(ptr!=s)
{
prev->n=ne;
ne->n=ptr;
}
else
{
ne->n=ptr;
s=ne;
}
}
}
void del()
{
int troll;
data *ptr,*prev;
cout<<"Enter Roll No. to be Deleted: ";
cin>>troll;
for(ptr=s;ptr!=NULL && troll != ptr->rroll();prev=ptr,ptr=ptr->n);
if(ptr==s)
{
s=s->n;
delete ptr;
}
else
{
prev->n=ptr->n;
delete ptr;
}
}
void disp()
{
int droll;
int choice;
data *ptr,*prev;
cout<<"Press-\n1. To Display Full List:\n2. To Display According to Choice:"<>choice;
switch(choice)
{
case 1:
for(ptr=s;ptr!=NULL;ptr=ptr->n)
{
ptr->disp();
}
break;
case 2:
cout<<"Enter Roll No. to be Displayed: ";
cin>>droll;
for(ptr=s;ptr!=NULL && droll != ptr->rroll();prev=ptr,ptr=ptr->n);
ptr->disp();
break;
}
}
};
int main()
{
stru ob;
char ch;
do
{
cout<>ch;
cout<<endl;
switch(ch)
{
case '1':
ob.add();
break;
case '2':
ob.disp();
break;
case '3':
ob.del();
break;
}
}
while(ch!='4');
return 0;
}
thanks
ReplyDeleteThanks For Sharing
ReplyDeleteDifference Between Singly Linked List And Doubly Linked List >>>>> Download Now
ReplyDelete>>>>> Download Full
Difference Between Singly Linked List And Doubly Linked List >>>>> Download LINK
>>>>> Download Now
Difference Between Singly Linked List And Doubly Linked List >>>>> Download Full
>>>>> Download LINK dB