Understanding Linked Lists in Computer Science

Slide Note
Embed
Share

Explore the concept of linked lists in computer science, detailing their structure, advantages, and disadvantages compared to vectors. Learn about the representation in memory, node structure, and reasons for using linked lists over other data structures.


Uploaded on Sep 24, 2024 | 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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. CMSC202 Computer Science II for Majors Lecture 12 Linked Lists Dr. Katherine Gibson www.umbc.edu

  2. Last Class We Covered Inheritance Object relationships is-a (Inheritance) has-a (Composition and Aggregation) 2 www.umbc.edu

  3. Any Questions from Last Time? www.umbc.edu

  4. Todays Objectives To cover linked lists in detail Traversal Creation Insertion Deletion 4 www.umbc.edu

  5. Linked Lists vs Vectors www.umbc.edu

  6. What is a Linked List? Data structure Dynamic Allow easy insertion and deletion Uses nodes that contain Data Pointer to next node in the list 6 www.umbc.edu

  7. Example Linked List In these diagrams, a doubly- outlined box indicates a pointer. tail head data data data data link link link link NULL 7 www.umbc.edu

  8. Why Use Linked Lists? We already have vectors! What are some disadvantages of a vectors? Inserting in the middle of a vector takes time Deletion as well Sorting Requires a contiguous block of memory 8 www.umbc.edu

  9. Representation in Memory Each cell is a block of memory Vector location in memory First node of Linked List NULL 9 www.umbc.edu

  10. (Dis)Advantages of Linked Lists Advantages: Change size easily and constantly Insertion and deletion can easily happen anywhere in the Linked List Only one node needs to be contiguously stored Disadvantages: Can t access by index value Requires management of memory Pointer to next node takes up more memory 10 www.umbc.edu

  11. Nodes www.umbc.edu

  12. Nodes A node is one element of a Linked List Nodes consist of two main parts: Data stored in the node Pointer to next node in list data link Often represented as classes 12 www.umbc.edu

  13. Code for Node Class class Node { String name; int testGrade; Node *link; name testGrade link NULL // constructor // accessors // mutators }; link can point to other nodes two options: 1. another Node 2. NULL 13 www.umbc.edu

  14. Linked List Overview www.umbc.edu

  15. 15 www.umbc.edu

  16. Example Linked List link m_head name name DUMMY name testGrade testGrade DUMMY testGrade link link link link NULL 16 www.umbc.edu

  17. Important Points to Remember Last node in the Linked List points to NULL Each node points to either another node in the Linked List, or to NULL Only one link per node 17 www.umbc.edu

  18. Managing Memory with LLs Hard part of using Linked Lists is ensuring that none of the nodes go missing Think of Linked List as a train (Or as a conga line of Kindergarteners) Must keep track of where links point to If you re not careful, nodes can get lost in memory (and you have no way to find them) 18 www.umbc.edu

  19. Linked List Functions What functions does a Linked List class implementation require? Linked_List constructor insert() remove() printList() isEmpty() 19 www.umbc.edu

  20. Linked Lists Special Cases Linked Lists often need to be handled differently under specific circumstances Linked List is empty Linked List has only one element Linked List has multiple elements Changing something with the first or last node Keep this in mind when you are coding Dummy nodes alleviate some of these concerns 20 www.umbc.edu

  21. Creating a Linked List 21 www.umbc.edu

  22. Traversing the List To control our traversal, we ll use a loop Initialization, Termination Condition, Modification 1. Set CURR to the first node in the list 2. Continue until we hit the end of the list (NULL) 3. Move from one node to another (using m_next) www.umbc.edu

  23. Demonstration of Traversal NULL FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { www.umbc.edu

  24. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { www.umbc.edu

  25. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { // ignore, dummy node www.umbc.edu

  26. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { www.umbc.edu

  27. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { www.umbc.edu

  28. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { // print information (Bob) www.umbc.edu

  29. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { www.umbc.edu

  30. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { www.umbc.edu

  31. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { // print information (Eve) www.umbc.edu

  32. Demonstration of Traversal FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { www.umbc.edu

  33. Demonstration of Traversal NULL FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { www.umbc.edu

  34. Demonstration of Traversal NULL FRONT CURR DUMMY Bob Eve DUMMY 91 94 link link link NULL for (CURR = FRONT; CURR != NULL; CURR = CURR->link) { } // exit the loop www.umbc.edu

  35. Insertion and Deletion 35 www.umbc.edu

  36. Announcements Project 3 is out get started now! It is due Thursday, March 31st 36 www.umbc.edu

Related


More Related Content