Chapter 15Introduction to Linked Data StructuresJava Linked ListsNodes and Links in a Linked ListA Simple Linked List ClassA Node Class (Part 1 of 3)A Node Class (Part 2 of 3)A Node Class (Part 3 of 3)Slide 9Slide 10An Empty List Is Indicated by nullA Linked List Class (Part 1 of 6)A Linked List Class (Part 2 of 6)A Linked List Class (Part 3 of 6)A Linked List Class (Part 4 of 6)A Linked List Class (Part 5 of 6)A Linked List Class (Part 6 of 6)Indicating the End of a Linked ListTraversing a Linked ListSlide 20Adding a Node to a Linked ListAdding a Node at the StartDeleting the Head Node from a Linked ListA Linked List Demonstration (Part 1 of 3)A Linked List Demonstration (Part 2 of 3)A Linked List Demonstration (Part 3 of 3)Node Inner ClassesPitfall: Privacy LeaksA Linked List Class with a Node Inner Class (Part 1 of 6)A Linked List Class with a Node Inner Class (Part 2 of 6)A Linked List Class with a Node Inner Class (Part 3 of 6)A Linked List Class with a Node Inner Class (Part 4 of 6)A Linked List Class with a Node Inner Class (Part 5 of 6)A Linked List Class with a Node Inner Class (Part 6 of 6)Linked listVariations on a theme (different types of lists)Slide 37A Generic Linked ListA Generic Linked List Class (Part 1 of 9)A Generic Linked List Class (Part 2 of 9)A Generic Linked List Class (Part 3 of 9)A Generic Linked List Class (Part 4 of 9)A Generic Linked List Class (Part 5 of 9)A Generic Linked List Class (Part 6 of 9)A Generic Linked List Class (Part 7 of 9)A Generic Linked List Class (Part 8 of 9)A Generic Linked List Class (Part 9 of 9)A Sample Class for the Data in a Generic Linked List (Part 1 of 2)A Sample Class for the Data in a Generic Linked List (Part 2 of 2)A Generic Linked List Demonstration (Part 1 of 2)A Generic Linked List Demonstration (Part 2 of 2)Slide 52Slide 53Slide 54Slide 55Pitfall: Using Node instead of Node<T>A Generic Linked List: the equals MethodAn equals Method for the Linked List in Display 15.7 (Part 1 of 2)An equals Method for the Linked List in Display 15.7 (Part 2 of 2)StackSlide 61QueueSlide 63SetsSet operationsAdditional set operationsChapter 15Linked Data StructuresCopyright © 2008 Pearson Addison-Wesley. All rights reservedIntroduction to Linked Data Structures•A linked data structure consists of capsules of data known as nodes that are connected via links–Links can be viewed as arrows and thought of as one way passages from one node to another•In Java, nodes are realized as objects of a node class•The data in a node is stored via instance variables•The links are realized as references–A reference is a memory address, and is stored in a variable of a class type–Therefore, a link is an instance variable of the node class type itself15-2Copyright © 2008 Pearson Addison-Wesley. All rights reservedJava Linked Lists•The simplest kind of linked data structure is a linked list•A linked list consists of a single chain of nodes, each connected to the next by a link–The first node is called the head node–The last node serves as a kind of end marker15-3Copyright © 2008 Pearson Addison-Wesley. All rights reservedNodes and Links in a Linked List15-4Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Simple Linked List Class•In a linked list, each node is an object of a node class–Note that each node is typically illustrated as a box containing one or more pieces of data•Each node contains data and a link to another node–A piece of data is stored as an instance variable of the node–Data is represented as information contained within the node "box"–Links are implemented as references to a node stored in an instance variable of the node type–Links are typically illustrated as arrows that point to the node to which they "link"15-5Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Node Class (Part 1 of 3)15-6Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Node Class (Part 2 of 3)15-7Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Node Class (Part 3 of 3)15-8Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Simple Linked List Class•The first node, or start node in a linked list is called the head node–The entire linked list can be traversed by starting at the head node and visiting each node exactly once•There is typically a variable of the node type (e.g., head) that contains a reference to the first node in the linked list–However, it is not the head node, nor is it even a node–It simply contains a reference to the head node15-9Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Simple Linked List Class•A linked list object contains the variable head as an instance variable of the class•A linked list object does not contain all the nodes in the linked list directly–Rather, it uses the instance variable head to locate the head node of the list–The head node and every node of the list contain a link instance variable that provides a reference to the next node in the list–Therefore, once the head node can be reached, then every other node in the list can be reached 15-10Copyright © 2008 Pearson Addison-Wesley. All rights reservedAn Empty List Is Indicated by null•The head instance variable contains a reference to the first node in the linked list–If the list is empty, this instance variable is set to null–Note: This is tested using ==, not the equals method•The linked list constructor sets the head instance variable to null–This indicates that the newly created linked list is empty15-11Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Linked List Class (Part 1 of 6)15-12Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Linked List Class (Part 2 of 6)15-13Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Linked List Class (Part 3 of 6)15-14Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Linked List Class (Part 4 of 6)15-15Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Linked List Class (Part 5 of 6)15-16Copyright © 2008 Pearson Addison-Wesley. All rights reservedA Linked List Class (Part 6 of 6)15-17Copyright © 2008 Pearson Addison-Wesley. All rights reservedIndicating the End of a Linked List•The last node in a linked list should have its link instance variable set to null–That way the code can test whether or not a node is the last node–Note: This is tested using ==, not the equals method15-18Copyright © 2008 Pearson