Linked Lists in Computer Science

CMSC202
 Computer Science II for Majors
Lecture 12 –
Linked Lists
Dr. Katherine Gibson
Last Class We Covered
•
Inheritance
•
Object relationships
–
is-a (Inheritance)
–
has-a (Composition and Aggregation)
2
Any Questions from Last Time?
 
Today’s Objectives
•
To cover linked lists in detail
–
Traversal
–
Creation
–
Insertion
–
Deletion
4
Linked Lists vs Vectors
 
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
Example Linked List
7
head
NULL
In these diagrams, a doubly-
outlined box indicates a pointer.
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
Representation in Memory
9
Vector location
in memory
 
NULL
First node of
Linked List
Each cell is a
block of memory
(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
Nodes
 
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
 
•
Often represented as classes
 
12
Code for Node Class
class 
Node
{
    
String 
name
;
    
int
    
testGrade
;
    
Node
  *
link
;
    
// constructor
    // accessors
    // mutators
};
13
link can point to other nodes
two options:
1.
another Node
2.
NULL
 
NULL
Linked List Overview
 
15
Example Linked List
16
 
NULL
link
m_head
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
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
Linked List Functions
 
•
What functions does a Linked List
class implementation require?
 
•
Linked_List constructor
•
insert()
•
remove()
•
printList()
•
isEmpty()
 
 
19
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
Creating a Linked List
21
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
)
Demonstration of Traversal
FRONT
CURR
NULL
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
    // ignore, dummy node
 
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
    // print information (Bob)
 
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
    // print information (Eve)
 
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
NULL
Demonstration of Traversal
FRONT
CURR
for (CURR = FRONT; CURR != NULL; CURR = CURR->link) {
NULL
 
}  // exit the loop
Insertion and Deletion
35
Announcements
•
Project 3 is out – get started now!
–
It is due Thursday, March 31st
36

								

								
								

										

												
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.


								
    
																		
  •   Linked lists
    • 
																	
  •    Data structure
    • 
																	
  •    Computer science
    • 
																	
  •    Memory representation
    • 
																	
  •    Node structure
    • 
																

								

								

									

										leven
										

											 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

								

								
  1. CMSC202 Computer Science II for Majors Lecture 12     Linked Lists Dr. Katherine Gibson www.umbc.edu
    2. 
            
            
            
  2. Last Class We Covered     Inheritance     Object relationships     is-a (Inheritance)     has-a (Composition and Aggregation) 2 www.umbc.edu
    3. 
            
            
            
  3. Any Questions from Last Time? www.umbc.edu
    4. 
            
            
            
  4. Todays Objectives     To cover linked lists in detail     Traversal     Creation     Insertion     Deletion 4 www.umbc.edu
    5. 
            
            
            
  5. Linked Lists vs Vectors www.umbc.edu
    6. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  11. Nodes www.umbc.edu
    12. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  14. Linked List Overview www.umbc.edu
    15. 
            
            
            
  15. 15 www.umbc.edu
    16. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  21. Creating a Linked List 21 www.umbc.edu
    22. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  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. 
            
            
            
  35. Insertion and Deletion 35 www.umbc.edu
    36. 
            
            
            
  36. Announcements     Project 3 is out     get started now!    It is due Thursday, March 31st 36 www.umbc.edu
    37. 
            
            
            
							

							

					

					
					
					

						
Related

						

						


							
							
							
							

						

							

									

      

        
          

            

              LINKED LIST.MODULE 3
            

            

              
LINKED LIST.MODULE 3

              
mori

            

          

        
      


     

      

        
          

            

              Threads, Linked Lists, and Programming Models in Concurrent Programs
            

            

              
Threads, Linked Lists, and Programming Models in Concurrent Programs

              
marmaduke

            

          

        
      


     

      

        
          

            

              Sex-Linked Inheritance: Key Concepts and Examples
            

            

              
Sex-Linked Inheritance: Key Concepts and Examples

              
wade

            

          

        
      


     

      

        
          

            

              Computer Science Department Information and Courses Offered
            

            

              
Computer Science Department Information and Courses Offered

              
suki

            

          

        
      


     

      

        
          

            

              Introduction to Creating Lists in Python
            

            

              
Introduction to Creating Lists in Python

              
meera

            

          

        
      


     

      

        
          

            

              Sex-Linked Inheritance in Genetics
            

            

              
Sex-Linked Inheritance in Genetics

              
sailor

            

          

        
      


     

      

        
          

            

              Evolution of Algorithms and Computer Science Through History
            

            

              
Evolution of Algorithms and Computer Science Through History

              
irvin

            

          

        
      


     

      

        
          

            

              Data Structures in Computer Science
            

            

              
Data Structures in Computer Science

              
dax

            

          

        
      


     

      

        
          

            

              Doubly Linked Lists in C Programming
            

            

              
Doubly Linked Lists in C Programming

              
remo

            

          

        
      


     

      

        
          

            

              List ADT and Linked Lists
            

            

              
List ADT and Linked Lists

              
rosc_617

            

          

        
      


     

      

        
          

            

              Linked Data: Building a Semantic Web Ecosystem
            

            

              
Linked Data: Building a Semantic Web Ecosystem

              
ella779

            

          

        
      


     

      

        
          

            

              X-Linked Inheritance and Diseases
            

            

              
X-Linked Inheritance and Diseases

              
hardnett_a

            

          

        
      


     

      

        
          

            

              Introduction to Linked Lists: An Overview of LinkedIntList
            

            

              
Introduction to Linked Lists: An Overview of LinkedIntList

              
atro956

            

          

        
      


     

      

        
          

            

              Mix and Match Data Structures for Efficient Algorithms
            

            

              
Mix and Match Data Structures for Efficient Algorithms

              
demariyav

            

          

        
      


     

      

        
          

            

              Lists and Strings in Computer Science I
            

            

              
Lists and Strings in Computer Science I

              
omer_831

            

          

        
      


     

      

        
          

            

              Comparison between Array and Linked List Data Structures
            

            

              
Comparison between Array and Linked List Data Structures

              
kmarn

            

          

        
      


     

      

        
          

            

              Linked Lists in Data Structures and Algorithms
            

            

              
Linked Lists in Data Structures and Algorithms

              
ais_m

            

          

        
      


     

      

        
          

            

              Basic Data Structures and Recursion in Programming
            

            

              
Basic Data Structures and Recursion in Programming

              
forseth_m

            

          

        
      


     

      

        
          

            

              Inserting a Number into a Sorted List Using Linked Lists
            

            

              
Inserting a Number into a Sorted List Using Linked Lists

              
icke_v

            

          

        
      


     

      

        
          

            

              Arrays and Linked Lists in Computer Science
            

            

              
Arrays and Linked Lists in Computer Science

              
vira_69

            

          

        
      


     

      

        
          

            

              Doubly Linked Lists in Data Structures
            

            

              
Doubly Linked Lists in Data Structures

              
sukhma

            

          

        
      


     

      

        
          

            

              Streamlining EMS Documentation: Defined Lists for Efficient Patient Care
            

            

              
Streamlining EMS Documentation: Defined Lists for Efficient Patient Care

              
zwiebel_z

            

          

        
      


     							

						

					

					

				


				

			

		
		

			

				
				

					
More Related Content

					

						

														

					

				

				
			

		












 





  
  
  



giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#