Linked List Implementation In C++

Im going to show you the implementation of Linked List In C++ to continue our Data Structure course in C++ language

You will find the code splitted to three parts at the first part List.h we are going to define function's header and at the second part List.cpp we are going to implement this function and in the last part main.cpp we are going call this function

List.h

  1 typedef int INFO;
  2  
  3 typedef struct node
  4 { 
  5     INFO data; 
  6     struct node *next; 
  7 }Node; 
  8  
  9 typedef struct ListNode
 10 { 
 11     Node *head; 
 12     int size; 
 13 }listnode; 
 14  
 15 void CreateList(listnode *); 
 16 int ListEmpty(listnode *); 
 17 int ListFull(listnode *); 
 18 void InsertNode(listnode *,INFO *,INFO); 
 19 void DeleteNode(listnode *,INFO *,INFO); 
 20 int SizeNode(listnode *); 
 21 void RetriveElement(listnode *,INFO *,INFO);
 22 void TraverseList(listnode *,void (*pvisit) (INFO)); 
 23 void JoinList(listnode *,listnode *);

List.Cpp

  1 #include "List.h" 
  2 #include <stdio.h> 
  3 #include <stddef.h> 
  4 #include <stdlib.h> 
  5  
  6 void CreateList(listnode *pl) 
  7 { 
  8     pl->head=NULL; 
  9     pl->size=0; 
 10 } 
 11  
 12 int ListEmpty(listnode *pl) 
 13 { 
 14     return(pl->head==NULL); 
 15 } 
 16  
 17 int ListFull(listnode *pl) 
 18 { 
 19     return 0;
 20 } 
 21  
 22 void InsertNode(listnode *pl,INFO *item,INFO pos)
 23 { 
 24     Node *ptr=(Node *)malloc(sizeof(Node)); 
 25     ptr->data=*item; 
 26     ptr->next=NULL; 
 27     if(pos==0) 
 28     { 
 29         ptr->next=pl->head; 
 30         pl->head=ptr; 
 31     } 
 32      
 33     else 
 34     { 
 35         Node *q; 
 36         int i; 
 37         for(q=pl->head,i=0;i<pos-1;i++) 
 38         { 
 39             q=q->next; 
 40         } 
 41         ptr->next=q->next; 
 42         q->next=ptr; 
 43  
 44     } 
 45      
 46     pl->size++; 
 47 } 
 48  
 49 void DeleteNode(listnode *pl,INFO *item,INFO pos)
 50 { 
 51     Node *q,*temp; 
 52     if(pos==0) 
 53     { 
 54         *item=pl->head->data; 
 55         temp=pl->head; 
 56         pl->head=pl->head->next; 
 57         free(temp); 
 58     } 
 59     else 
 60     { 
 61         int i; 
 62         for(q=pl->head,i=0;i<pos-1;i++) 
 63         { 
 64             q=q->next; 
 65         } 
 66         *item=q->next->data; 
 67         temp=q->next; 
 68         q->next=q->next->next; 
 69         free(temp); 
 70     } 
 71  
 72     pl->size--; 
 73 } 
 74  
 75 int SizeNode(listnode *pl) 
 76 { 
 77     return pl->size; 
 78 } 
 79  
 80 void RetriveElement(listnode *pl,INFO *item,INFO pos)
 81 { 
 82     Node *q; 
 83     int i; 
 84     for(q=pl->head,i=0;i<pos;i++) 
 85     { 
 86         q=q->next; 
 87     } 
 88     *item=q->data; 
 89  
 90 } 
 91  
 92 void TraverseList(listnode *pl,void (*pvisit) (INFO)) 
 93 { 
 94     Node *q; 
 95     q=pl->head; 
 96     while(q) 
 97     { 
 98         (*pvisit)(q->data); 
 99         q=q->next; 
100     } 
101 } 
102  
103 void JoinList(listnode *pl1,listnode *pl2)
104 { 
105     Node *q1=pl1->head; 
106     Node *q2=pl2->head; 
107     while(q2) 
108     { 
109         q2=q2->next; 
110     } 
111     while(q1) 
112     { 
113     Node *ptr=(Node *)malloc(sizeof(Node)); 
114     ptr->data=q1->data; 
115     ptr->next=q2->next; 
116     q2->next=ptr; 
117     q1=q1->next; 
118     } 
119 }

Main.Cpp

  1 #include "List.h" 
  2 #include <stddef.h> 
  3 #include <stdio.h> 
  4 #include <stdlib.h> 
  5  
  6 void Display(INFO e) 
  7 { 
  8     printf("%d\n",e); 
  9 } 
 10  
 11 int main() 
 12 { 
 13     int ch; 
 14     listnode l1,l2; 
 15     INFO e,pos; 
 16     CreateList(&l1); 
 17     CreateList(&l2); 
 18     printf("Press 1 To Insert Into List\nPress 2 To Delete From List\nPress 3 To Get Size Of List\nPress 4 To Get A Specific Element\nPress 5 To Traverse List\nPress 6 To Join Two Lists\nPress 7 To Exit\n"); 
 19     scanf("%d",&ch); 
 20     while(ch!=7) 
 21     { 
 22         if(ch==1) 
 23         { 
 24             printf("\nEnter Data To Insert It Into List\n"); 
 25             scanf("%d",&e); 
 26             printf("\nEnter Position\n"); 
 27             scanf("%d",&pos); 
 28             if(!ListFull(&l1)) 
 29             { 
 30                 InsertNode(&l1,&e,pos); 
 31                 InsertNode(&l2,&e,pos); 
 32             } 
 33             else 
 34                 printf("\nList Full\n");
 35         } 
 36  
 37         if(ch==2) 
 38         { 
 39             printf("\nEnter Position\n"); 
 40             scanf("%d",&pos); 
 41             if(!ListEmpty(&l1)) 
 42             { 
 43                 DeleteNode(&l1,&e,pos); 
 44                 printf("Item Which Has Been Extracted is : %d\n",e); 
 45             } 
 46             else 
 47                 printf("\nList Empty\n"); 
 48         } 
 49          
 50         if(ch==3) 
 51         { 
 52             printf("Size Of List Is : %d\n",SizeNode(&l1)); 
 53         } 
 54         if(ch==4) 
 55         { 
 56             printf("\nEnter The Position Of The Element To Get It\n"); 
 57             scanf("%d",&pos); 
 58             RetriveElement(&l1,&e,pos); 
 59             printf("\n The Values IS : %d\n",e); 
 60         } 
 61         if(ch==5) 
 62         { 
 63             printf("You Are Going To Traverse List\n"); 
 64             TraverseList(&l1,&Display); 
 65             printf("\nTraversed Successfully\n"); 
 66         } 
 67  
 68         else if(ch==6) 
 69         { 
 70             JoinList(&l1,&l2); 
 71             printf("\nJoined Successfully\n"); 
 72         } 
 73     printf("Press 1 To Insert Into List\nPress 2 To Delete From List\nPress 3 To Get Size Of List\nPress 4 To Get A Specific Element\nPress 5 To Traverse List\nPress 6 To Join Two Lists\nPress 7 To Exit\n"); 
 74     scanf("%d",&ch); 
 75     } 
 76  
 77 return 0;
 78 }