Understanding Linked Lists in Computer Science
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.
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
CMSC202 Computer Science II for Majors Lecture 12 Linked Lists Dr. Katherine Gibson www.umbc.edu
Last Class We Covered Inheritance Object relationships is-a (Inheritance) has-a (Composition and Aggregation) 2 www.umbc.edu
Any Questions from Last Time? www.umbc.edu
Todays Objectives To cover linked lists in detail Traversal Creation Insertion Deletion 4 www.umbc.edu
Linked Lists vs Vectors www.umbc.edu
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
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
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
Representation in Memory Each cell is a block of memory Vector location in memory First node of Linked List NULL 9 www.umbc.edu
(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
Nodes www.umbc.edu
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
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
Linked List Overview www.umbc.edu
15 www.umbc.edu
Example Linked List link m_head name name DUMMY name testGrade testGrade DUMMY testGrade link link link link NULL 16 www.umbc.edu
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
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
Linked List Functions What functions does a Linked List class implementation require? Linked_List constructor insert() remove() printList() isEmpty() 19 www.umbc.edu
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
Creating a Linked List 21 www.umbc.edu
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
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
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
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
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
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
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
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
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
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
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
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
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
Insertion and Deletion 35 www.umbc.edu
Announcements Project 3 is out get started now! It is due Thursday, March 31st 36 www.umbc.edu