Linked List

Linked List Advantages 

• Linked List is Dynamic data Structure .
• Linked List can grow and shrink during run time.
• Insertion and Deletion Operations are Easier.
• Efficient Memory Utilization ,i.e no need to pre-allocate memory.
• Faster Access time,can be expanded in constant time without memory overhead.

Disadvantages of Linked List

1. They use more memory than arrays because of the storage used by their pointers.
2. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer.
3. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
4. Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list, especially with a CPU cache.

<code>
#include <iostream>
using namespace std;
struct node
{
int value;
node *next;
}*first,*last;
class LinkedList
{
public:
LinkedList();
void addNodeatTheEnd(int val);
void addNodeatTheFirt(int val);
void Insert(int val, int atPosition);
void DeleteNode(int pos);
void Display();
};
LinkedList::LinkedList()
{
first = NULL;
last = NULL;
}
void LinkedList::addNodeatTheEnd(int val)
{
node *temp;
temp = new node;
temp->value = val;
temp->next =NULL;
if(first == NULL)
{
first=temp;
last=temp;
}
else
{
last->next = temp;
last = temp;
}

}
void LinkedList::addNodeatTheFirt(int val)
{
node *temp;
temp = new node;
temp->value = val;
temp->next =NULL;
if(first == NULL)
{
first=temp;
last=temp;
}
else
{
temp->next = first;
first = temp;
}

}
void LinkedList::DeleteNode(int position)
{
node* itr,*q,*temp;
node* tmp = new node;
itr =first;

for(int pos =0;pos < position;pos++)
{
itr = itr->next;
}
q = itr->next->next;
temp = itr->next;
itr->next = q;
delete temp;

}
void LinkedList::Insert(int val, int position)
{
node* itr,*q;
node* tmp = new node;
itr =first;

for(int pos =0;pos < position;pos++)
{
itr = itr->next;
}
q = itr->next;

tmp->next = q;
tmp->value = val;
itr->next = tmp;
       
}
void LinkedList::Display()
{
node *disp;
for(disp=first;disp!= NULL;disp = disp->next)
{
cout<<disp->value <<" "<<"\n";
}

}
int main()
{
LinkedList l;
l.addNodeatTheEnd(10);
l.addNodeatTheEnd(20);
l.addNodeatTheEnd(30);
l.addNodeatTheFirt(40);
l.Insert(100, 2);
l.Display();
return 0;
}
</code>
quiz on linked list
http://www.bogotobogo.com/cplusplus/quiz_linkedlist.php#sortedlist
http://www.bogotobogo.com/cplusplus/quiz_linkedlist.php#duplicatesnode
http://www.bogotobogo.com/cplusplus/linkedlist.php#linkedlistexample10