Building a Linked List and Pointer Manipulation

linked lists n.w
1 / 48
Embed
Share

Learn the fundamentals of building a linked list in C++, including dynamic memory allocation, pointer manipulation, node creation, traversal, and more. Dive into the intricacies of pointer dereferencing and member selection to understand how to work with linked lists effectively.

  • Linked List
  • Pointer Manipulation
  • C++
  • Node Creation
  • Traversal
rayaanacharya
fabia Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Linked Lists Introduction Building a Linked List Traversing a Linked List Deleting a Node Dr. Hyrum D. Carroll (with some material from Dale & Weems s Programming and Problem Solving with C++ slides)

  2. Declarations for a Dynamic Linked List // Type declarations struct NodeType { char info; NodeType* link; }; // Variable DECLARATIONS NodeType* head; NodeType* ptr; A 0x600 . .info . .link

  3. ptr is a pointer to a node ptr A 0x600 . .info . .link ptr

  4. *ptr is the entire node pointed to by ptr ptr A 0x600 . .info . .link *ptr

  5. ptr->info is a node member ptr A 0x600 . .info . . link ptr->info or (*ptr).info // Equivalent

  6. ptr->link is a node member ptr A 0x600 . . info . . link ptr->link or (*ptr).link // Equivalent

  7. Pointer Dereferencing and Member Selection A 0x600 ptr . . info . . link ptr ptr A 0x600 . . info . . link *ptr ptr A 0x600 . . info . . link (*ptr).info or ptr->info

  8. BUILDING A LINKED LIST

  9. Building a Linked List newNodePtr head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  10. Building a Linked List newNodePtr 0x200 head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  11. Building a Linked List newNodePtr 0x200 L head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  12. Building a Linked List newNodePtr 0x200 L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  13. Building a Linked List newNodePtr 0x200 L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  14. Building a Linked List newNodePtr 0x500 0x200 L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  15. Building a Linked List newNodePtr 0x500 0x200 I L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  16. Building a Linked List newNodePtr 0x500 0x200 I 0x200 L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  17. Building a Linked List newNodePtr 0x500 0x200 0x200 L NULL head I newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  18. Building a Linked List newNodePtr 0x300 0x500 0x200 I 0x200 L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  19. Building a Linked List newNodePtr 0x300 0x500 0x200 T I 0x200 L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  20. Building a Linked List newNodePtr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  21. Building a Linked List newNodePtr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head newNodePtr = new NodeType; newNodePtr->info = L ; newNodePtr->link = NULL; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = I ; newNodePtr->link = head; head = newNodePtr; newNodePtr = new NodeType; newNodePtr->info = T ; newNodePtr->link = head; head = newNodePtr;

  22. TRAVERSING A LINKED LIST

  23. Traversing a Linked List ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  24. Traversing a Linked List 0x300 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  25. Traversing a Linked List 0x300 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  26. Traversing a Linked List 0x300 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: T ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  27. Traversing a Linked List 0x500 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  28. Traversing a Linked List 0x500 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  29. Traversing a Linked List 0x500 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: I ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  30. Traversing a Linked List 0x200 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: I ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  31. Traversing a Linked List 0x200 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: I ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  32. Traversing a Linked List 0x200 ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: L ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  33. Traversing a Linked List NULL ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: L ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  34. Traversing a Linked List NULL ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: L ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  35. Traversing a Linked List NULL ptr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 Output: L ptr = head; while (ptr != NULL){ cout << ptr->info; ptr = ptr->link; }

  36. DELETING A NODE

  37. Deleting Node I prev curr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  38. Deleting Node I NULL 0x300 prev curr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  39. Deleting Node I NULL 0x300 prev curr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  40. Deleting Node I 0x300 0x300 prev curr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  41. Deleting Node I 0x300 0x300 prev curr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  42. Deleting Node I 0x300 0x300 prev curr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  43. Deleting Node I 0x300 0x300 prev curr 0x300 0x500 0x200 T 0x500 I 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  44. Deleting Node I 0x300 0x300 prev curr 0x300 0x500 0x200 T 0x200 I 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  45. Deleting Node I 0x300 0x300 prev curr 0x300 0x500 0x200 T 0x200 ? ? L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  46. Deleting Node I 0x300 NULL prev curr 0x300 0x200 T 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  47. Deleting Node I 0x300 NULL prev curr 0x300 0x200 T 0x200 L NULL head 0x300 // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

  48. Deleting Node I 0x300 NULL prev curr 0x300 0x200 T 0x200 0x300 0x200 L NULL L NULL head // find node I NodeType *curr = head, *prev = NULL; while( curr != NULL && curr->info != I ){ prev = curr; curr = curr->link; } if( curr == NULL){/* I not found*/ return; } prev->link = curr->link; // copy pointer to prev s delete curr; // free up memory on the heap curr = NULL; // clean up the pointer

Related


Lists and Collections in Java

Lists and Collections in Java

kingmic

More Related Content