LinkedList Stack Queue

Views:
 
Category: Education
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

WELCOME TO Linked List, Stack & Queue:

WELCOME TO Linked List, Stack & Queue By VIKAS PANDEY BAL MANDIR SR. SEC. SCHOOL

Linked-List:

Linked-List A link-list is a linear collection of data elements, called nodes pointing to the next nodes by means of pointers. A stack is a linear structure implemented in LIFO manner where insertions and deletions are restricted to occur only at one end – stack’s top. The stack is also a dynamic data structure as it can grow or shrink. A Queue is also a linear dynamic structure implemented in FIFO manner where insertions can occur at the “rear” end, and deletions occur only at “front” end.

Important Point about Link list:

Important Point about Link list Linked list overcome the drawbacks of arrays as in linked list number of elements need not be predetermined, more memory can be allocated or released during the processing as and when required. Making insertions and deletions much easier and simpler.

Singly, Doubly and Circular Linked List:

Singly, Doubly and Circular Linked List

Free Store Allocation in c++:

Free Store Allocation in c++ struct Node { char info; Node *next; }; Node *ptr; ptr = new Node; ptr->info; ptr->next; delete ptr;

Insertion:

Insertion Beginning MID END

Insertion in Link List:

Insertion in Link List #include<iostream.h> #include<process.h> struct Node { int info; Node *next; } *start, *newptr, *save, *ptr, *rear; Node * create_new_node(int); void insert_beg(Node *); void insert_end(Node *); void display(Node *); void main( ) {start = NULL; int inf; cout<<“Enter info for new node”; cin>>inf; cout<<“create new node !!”; newptr= create_new_node(inf); if(newptr!=NULL) cout<<“Success”; else { cout<<“Cannot create”; exit(1);} cout<<“insert new node in the beginning of list”; insert_beg(newptr); //Or insert_end(newptr); display(start); }

Insertion in Link List:

Insertion in Link List Node * create_new_node( int n) { ptr = new ptr; ptr->info=n; ptr->next=NULL; return ptr; } void insert_beg(Node *np) { if( start= =NULL) start=np; else { save=start; start=np; np->next=save;} } void display( Node *np) { while(np!=NULL) { cout<<np->info<<“->”; np=np->next; } cout<<“!!!\n”; } void insert_end(Node *np) { if( start= =NULL) start=rear=np; else { rear->next=np; rear=np;} }

Deletion in Link List:

Deletion in Link List #include<iostream.h> #include<process.h> struct Node { int info; Node *next; } *start, *newptr, *save, *ptr, *rear; Node * create_new_node(int); void insert(Node *); void display(Node *); void delnode(Node *); void main( ) {start = rear = NULL; int inf; cout<<“Enter info for new node”; cin>>inf; cout<<“create new node !!”; newptr= create_new_node(inf); if(newptr!=NULL) cout<<“Success”; else { cout<<“Cannot create”; exit(1);} cout<<“insert new node in the beginning of list”; insert(newptr); display(start); delnode( ); }

Deletion in Link List:

Deletion in Link List Node * create_new_node( int n) { ptr = new ptr; ptr->info=n; ptr->next=NULL; return ptr; } void insert(Node *np) { if( start= =NULL) start=rear=np; else { rear->next=np; rear=np;} } void display( Node *np) { while(np!=NULL) { cout<<np->info<<“->”; np=np->next; } cout<<“!!!\n”; } void delnode( ) { if( start= =NULL) cout<<“Underflow”; else { ptr=start; start=start->next; delete ptr;} }

Traversal in Link List:

Traversal in Link List #include<iostream.h> #include<process.h> struct Node { int info; Node *next; } *start, *newptr, *save, *ptr, *rear; Node * create_new_node(int); void insert(Node *); void traverse(Node *); void main( ) {start = rear = NULL; int inf; cout<<“Enter info for new node”; cin>>inf; cout<<“create new node !!”; newptr= create_new_node(inf); if(newptr!=NULL) cout<<“Success”; else { cout<<“Cannot create”; exit(1);} insert(newptr); traverse(start); }

Traversal in Link List:

Traversal in Link List Node * create_new_node( int n) { ptr = new ptr; ptr->info=n; ptr->next=NULL; return ptr; } void insert(Node *np) { if( start= =NULL) start=rear=np; else { rear->next=np; rear=np;} } void display( Node *np) { while(np!=NULL) { cout<<np->info<<“->”; np=np->next; } cout<<“!!!\n”; } void traverse(Node *np) { while(np!= NULL) { cout<<np->info <<“->”; np=np->next; } cout<<“!!!\n”; }

Stack:

Stack Stack refer to the lists stored and accessed in a special way i.e. LIFO technique. In stack, insertion and deletions take place only at one end called the top.

Stack Operation:

Stack Operation

Queues:

Queues Queues are FIFO lists, where insertions take place at the “rear” end of the queue and deletions take place at the “front” end of the queues.

Queues:

Queues

Application of Stack :Polish Strings:

Application of Stack :Polish Strings PUSH A PUSH B ADD   PUSH C PUSH D ADD   MUL   POP X

PowerPoint Presentation:

Thank You !!!

authorStream Live Help