Linked Lists The University of Texas at El Paso（链表的德克萨斯大学埃尔帕索分校）.pdfVIP

Linked Lists Chris Kiekintveld CS 2401 (Fall 2010) Elementary Data Structures and Algorithms Motivation   Suppose I have an array: 1,4,10,19,6   I want to insert a 7 between the 4 and the 10   What do I need to do? Java Programming: Program Design Including Data Structures 2 Linked Lists aka “Reference-Based Lists”   Linked list   List of items, called nodes   The order of the nodes is determined by the address, called the link, stored in each node   Every node (except the last node) contains the address of the next node   Components of a node   Data: stores the relevant information   Link: stores the address of the next node Java Programming: Program Design Including Data Structures 3 Linked Lists (continued) Figure 16-1 Structure of a node Figure 16-2 Linked list   Head or first   Holds the address of the first node in the list   The info part of the node can be either a value of a primitive type or a reference to an object Java Programming: Program Design Including Data Structures 4 Linked Lists (continued)   Class Node   Represents nodes on a list   It has two instance variables   info (of type int, but it can be any other type)   link (of type Node) public class Node { public int info; public Node link; } Java Programming: Program Design Including Data Structures 5 Linked List: Some Properties Figure 16-4 Linked list with four nodes Java Programming: Program Design Including Data Structures 6 Linked List: Some Properties   Now consider the statement current = he