C++ my notes(3) Linked list(insertion/deletion/doubly linked list)

Linked list:

(https://www.interviewbit.com/tutorial/arrays-vs-linked-lists/#arrays-vs-linked-lists

linked list implementation and insertion nodes at the end)

Linked Lists is a linear data structure.Its a Special kind of array we can say.To implement a linked list we need nodes.

Every node holds a value and a next field to hold the next nodes address.

Linked list Implementation:

#include <iostream> using namespace std;

void print (); struct node { int data; node *next; };

node *head = NULL; int main () { int n, x; cout << "enter the elements number:"; cin >> n; cout << "Enter the numbers:"; cin >> x; node *temp = new node (); temp->data = x; temp->next = NULL; head = temp;

node *temp1 = head;

for (int i = 0; i < n - 1; i++) { node *temp = new node (); cin >> x; temp->data = x; temp->next = NULL;

temp1 = head; while (temp1->next != NULL) { temp1 = temp1->next; } temp1->next = temp; print (); } return 0; }

void print () { node *temp = head; while (temp != NULL) { cout << temp << " " << temp->data << " " << temp->next<<endl; temp = temp->next;

} }

inserting data in the beginning in linked list:

#include <iostream> using namespace std; //inserting a node in the beggining void print (); struct node { int data; node *next; };

node *head = NULL;

int main () { int n,x; cin>>n; node *temp=new node(); cin>>x; temp->data=x; temp->next=NULL; head=temp; for(int i=0;i<n-1;i++) { node *temp=new node(); cin>>x; temp->data=x; temp->next=NULL; temp->next=head; head=temp; print(); } return 0; }

void print() { node *temp=head; while(temp!=NULL) { cout<<temp->data<<" "; temp=temp->next; } }

Deletion of a node:

assuming we have a linked list.And we want to delete the 3rd node.So we take a temporary variable which initially pointed at the head.Then we traverse and change the temp->next unless we go to the given node.The temp->next value of the 3rd node should stored in any variable.Then we again traverse in same procedure but this time up to the 2nd node and change the second nodes next with the stored value previously.

Doubly linked list:

https://www.geeksforgeeks.org/doubly-linked-list/

a node holds the value of its previous node and also the next node.

advantages:

1.We can traverse in both direction

2.Deletion is much easier.(read deletion of the node).When we have both the nodes we don't have to traverse twice to get the previous node again.Fantastic!!