Understanding Linked Lists in Computer Science

Slide Note

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.

leven Follow

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

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