Linked Lists Implementation Method 2 (1).ppt

Data Structures & Algorithms Linked List Implementation

Data Structures & Algorithms Linked Lists • Node data – Data for each node – Link to next node • Start pointer • How to implement a Linked List structure using a class? Suggestions??

Data Structures & Algorithms Linked List Class • Depends upon requirement – Do we need to create only one list or more lists? – If only one list is desired then simply make • start pointer as static (only one start pointer required) • data members and link to next node (next pointer) as non static – If number of lists desired are more than one then start pointer required for each list • Creating struct for each node • And making a list class – We will see implementation of linked list by both methods

Data Structures & Algorithms First Method: Declaring start pointer as static 1. class IntList 2. { 3. static IntList *ListHeadPtr; 4. int data; 5. IntList *next; 6. public: 7. static void AddNodeAtHead(int val); 8. static void AddNodeAtTail(int val); 9. static void DisplayList(void); 10. static void DeleteNode(int key); 11. static void DisplaySpecificNode(int key); 12.}; 13.//defining and initializing static member of class 14.IntList* IntList::ListHeadPtr=NULL;

Data Structures & Algorithms 1. void IntList::AddNodeAtHead(int val) 2. { 3. IntList *ptrNew = new IntList; 4. ptrNew->data = val; 5. ptrNew -> next = ListHeadPtr; 6. ListHeadPtr = ptrNew; 7. } 8. void IntList::AddNodeAtTail(int val) 9. { 10. IntList *ptrNew = new IntList, *ptrTemp=ListHeadPtr; 11. ptrNew->data = val; 12. ptrNew -> next = NULL; 13. if (ListHeadPtr == NULL) 14. { 15. ListHeadPtr = ptrNew; 16. return; 17. } 18. while (ptrTemp->next!=NULL) 19. ptrTemp=ptrTemp->next; 20. ptrTemp->next= ptrNew; 21.}

Data Structures & Algorithms 1. void IntList::DisplayList(void) 2. { 3. IntList *ptrTemp=ListHeadPtr; 4. cout<<endl; 5. while (ptrTemp!=NULL) 6. { 7. cout<<ptrTemp->data<<","; 8. ptrTemp=ptrTemp->next; 9. } 10.} 11.void IntList::DisplaySpecificNode(int key) 12.{ 13. IntList *ptrCurrent=ListHeadPtr; 14. while (ptrCurrent!=NULL && ptrCurrent->data!=key) 15. ptrCurrent = ptrCurrent->next; 16. if (ptrCurrent == NULL) 17. cout<<"nElement not found in the list"; 18. else 19. cout<<"nData for node is :"<<ptrCurrent->data; 20.}

Data Structures & Algorithms 1. void IntList::DeleteNode(int key) 2. { 3. IntList *ptrCurrent=ListHeadPtr,*ptrPrevious; 4. while (ptrCurrent!=NULL && ptrCurrent->data!=key) 5. { 6. ptrPrevious = ptrCurrent; 7. ptrCurrent = ptrCurrent->next; 8. } 9. if (ptrCurrent == NULL) 10. { 11. cout<<"nElement to delete not found in the list"; 12. return; 13. } 14. if (ptrCurrent == ListHeadPtr) //node to delete is first node 15. ListHeadPtr = ListHeadPtr->next; 16. else //node to delete is in middle or at end of list 17. ptrPrevious->next = ptrCurrent->next; 18. delete ptrCurrent; 19.}

Data Structures & Algorithms 1. void main(void) 2. { 3. IntList::AddNodeAtTail(20); 4. IntList::AddNodeAtHead(10); 5. IntList::AddNodeAtHead(34); 6. IntList::AddNodeAtTail(12); 7. IntList::DisplayList(); 8. IntList::DeleteNode(30); 9. IntList::DisplayList(); 10.}

Data Structures & Algorithms Destructor of list • Do we need to write a destructor which should delete all nodes of linked list? • Obviously No!!!!!! • For destroying whole list we should define another static member function, DeleteAll

Data Structures & Algorithms Second Method: Using struct for node data 1. class IntList 2. { 3. struct Node 4. { 5. int data; 6. Node *next; 7. }; 8. Node *ListHeadPtr; 9. public: 10. IntList() { ListHeadPtr = NULL; } 11. void AddNodeAtHead(int val); 12. void AddNodeAtTail(int val); 13. void DisplayList(void); 14. void DeleteNode(int key); 15. void DisplaySpecificNode(int key); 16. ~IntList(); 17.};

Data Structures & Algorithms 1. void IntList::AddNodeAtHead(int val) 2. { 3. Node *ptrNew = new Node; 4. ptrNew->data = val; 5. ptrNew -> next = ListHeadPtr; 6. ListHeadPtr = ptrNew; 7. } 8. void IntList::AddNodeAtTail(int val) 9. { 10. Node *ptrNew = new Node, *ptrTemp=ListHeadPtr; 11. ptrNew->data = val; 12. ptrNew -> next = NULL; 13. if (ListHeadPtr == NULL) 14. { 15. ListHeadPtr = ptrNew; 16. return; 17. } 18. while (ptrTemp->next!=NULL) 19. ptrTemp=ptrTemp->next; 20. ptrTemp->next= ptrNew; 21.}

Data Structures & Algorithms 1. void IntList::DisplayList(void) 2. { 3. Node *ptrTemp=ListHeadPtr; 4. cout<<endl; 5. while (ptrTemp!=NULL) 6. { 7. cout<<ptrTemp->data<<","; 8. ptrTemp=ptrTemp->next; 9. } 10.} 11.void IntList::DisplaySpecificNode(int key) 12.{ 13. Node *ptrCurrent=ListHeadPtr; 14. while (ptrCurrent!=NULL && ptrCurrent->data! =key) 15. ptrCurrent = ptrCurrent->next; 16. if (ptrCurrent == NULL) 17. cout<<"nElement not found in the list"; 18. else 19. cout<<"nData for node is :"<<ptrCurrent->data; 20.}

Data Structures & Algorithms 1. void IntList::DeleteNode(int key) 2. { 3. Node *ptrCurrent=ListHeadPtr,*ptrPrevious; 4. while (ptrCurrent!=NULL && ptrCurrent->data!=key) 5. { 6. ptrPrevious = ptrCurrent; 7. ptrCurrent = ptrCurrent->next; 8. } 9. if (ptrCurrent == NULL) 10. { 11. cout<<"nElement to delete not found in the list"; 12. return; 13. } 14. if (ptrCurrent == ListHeadPtr) //node to delete is first node 15. ListHeadPtr = ListHeadPtr->next; 16. else //node to delete is in middle or at end of list 17. ptrPrevious->next = ptrCurrent->next; 18. delete ptrCurrent; 19.}

Data Structures & Algorithms 1. IntList::~IntList() 2. { 3. Node *ptrPrevious; 4. while (ListHeadPtr!=NULL) 5. { 6. ptrPrevious = ListHeadPtr; 7. ListHeadPtr= ListHeadPtr->next; 8. delete ptrPrevious; 9. } 10.}

Data Structures & Algorithms 1. /*Driver program. Number of calls to functions of class to test working, you should call more functions, and look results thoroughly*/ 2. void main(int key) 3. { 4. IntList list1,list2; 5. list1.AddNodeAtTail(20); 6. list1.AddNodeAtHead(10); 7. list1.AddNodeAtHead(34); 8. list1.AddNodeAtTail(12); 9. list1.DeleteNode(10); 10. cout<<"nList1 after perorming few operations:"; 11. list1.DisplayList(); 12. 13. list2.AddNodeAtTail(23); 14. list2.AddNodeAtHead(45); 15. list2.AddNodeAtHead(75); 16. list2.AddNodeAtTail(29); 17. list2.DeleteNode(45); 18. cout<<"nlist2 after perorming few operations:"; 19. list2.DisplayList(); 20.}

Data Structures & Algorithms What about • 2-Way linked list (or doubly linked list) • 1-Way circular linked list • 2-Way circular linked list

Linked Lists Implementation Method 2 (1).ppt

More Related Content

Similar to Linked Lists Implementation Method 2 (1).ppt

More from Zuŋɘʀa Aɓɗuɭɭʌh

Recently uploaded

Linked Lists Implementation Method 2 (1).ppt