Linked_Structure.ppt
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (867.55 KB, 35 trang )
Chapter 4
Linked Structures
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-2
Chapter Objectives
•
Describe the use of references to create
linked structures
•
Compare linked structures to array-based
structures
•
Explore the techniques for managing a
linked list
•
Discuss the need for a separate node to
form linked structures
•
Implement a set collection using a linked list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-3
References as Links
•
There are many ways to implement a collection
•
In chapter 3 we explored an array-based
implementation of a set collection
•
A linked structure uses object reference
variables to link one object to another
•
Recall that an object reference variable stores
the address of an object
•
In that sense, an object reference is a pointer
to an object
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-4
FIGURE 4.1 An object reference
variable pointing to an object
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-5
Self-Referential Objects
•
A Person object, for instance, could contain
a reference variable to another Person
object:
public class Person
{
private String name;
private String address;
private Person next; // a link to another Person object
// whatever else
}
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-6
Linked Lists
•
This type of reference can be used to form a
linked list, in which one object refers to the next,
which refers to the next, etc.
•
Each object in a list is often generically called a
node
•
A linked list is a dynamic data structure in that
its size grows and shrinks as needed, unlike an
array, whose size is fixed
•
Java objects are created dynamically when they
are instantiated
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-7
FIGURE 4.2 A linked list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-8
Non-linear Structures
•
A linked list, as the name implies, is a
linear structure
•
Object references also allow us to
create non-linear structures such as
hierarchies and graphs
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-9
FIGURE 4.3
A complex linked structure
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-10
Managing Linked Lists
•
The references in a linked list must be
carefully managed to maintain the integrity of
the structure
•
Special care must be taken to ensure that the
entry point into the list is maintained properly
•
The order in which certain steps are taken is
important
•
Consider inserting and deleting nodes in
various positions within the list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-11
FIGURE 4.4 Inserting a node at the
front of a linked list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-12
FIGURE 4.5 Inserting a node in the
middle of a linked list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-13
FIGURE 4.6
Deleting the first node in a linked list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-14
FIGURE 4.7 Deleting an interior
node from a linked list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-15
Elements without Links
•
The problem with self-referential objects is that
they "know" they are part of a list
•
A better approach is to manage a separate list of
nodes that also reference the objects stored in the
list
•
The list is still managed using the same techniques
•
The objects stored in the list need no special
implementation to be part of the list
•
A generic list collection can be used to store any
kind of object
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-16
FIGURE 4.8 Using separate node
objects to store and link elements
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-17
Doubly Linked Lists
•
There are variations on the
implementation of linked lists that may
be useful in particular situations
•
For example, in a doubly linked list
each node has a reference to both the
next and previous nodes in the list
•
This makes traversing the list easier
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-18
FIGURE 4.9 A doubly linked list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-19
Listing 4.1
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-20
Listing 4.1 (cont.)
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-21
Listing 4.1 (cont.)
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-22
FIGURE 4.10 A linked
implementation of a set collection
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-23
LinkedSet - Constructor
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-24
LinkedSet - the add Operation
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved.
4-25
LinkedSet - the removeRandom
Operation
![Moi gioi BAT DONG SAN 01[1].ppt](https://media.store123doc.com/images/document/12/gu/pr/medium_VqscYiF6ld.jpg)
