Chapter 9.2 Linked Data Structures | Introduction to Programming Using Java

Chapter 9.2 Linked Data Structures | Introduction to Programming Using Java

 

9.2 Linked Data Structures

 

Every useful object contains instance variables. When the type of an instance variable is given by a class or interface name, the variable can hold a reference to another object. Such a reference is also called a pointer, and we say that the variable points to the object.

(Of course, any variable that can contain a reference to an object can also contain the special value null, which points to nowhere.) When one object contains an instance variable that points to another object, we think of the objects as being “linked” by the pointer. Data structures of great complexity can be constructed by linking objects together.

 

Chapter 9.2 Linked Data Structures | Introduction to Programming Using Java

 

9.2.1     Recursive Linking

Something interesting happens when an object contains an instance variable that can refer to another object of the same type. In that case, the definition of the object’s class is recursive. Such recursion arises naturally in many cases.

For example, consider a class designed to represent employees at a company. Suppose that every employee except the boss has a supervisor, who is another employee of the company. Then the Employee class would naturally contain an instance variable of type Employee that points to the employee’s supervisor:

34 3 Chapter 9.2 Linked Data Structures | Introduction to Programming Using Java

If emp is a variable of type Employee, then emp.supervisor is another variable of type Employee. If emp refers to the boss, then the value of emp.supervisor should be null to indicate the fact that the boss has no supervisor. If we wanted to print out the name of the employee’s supervisor, for example, we could use the following Java statement:

Chapter 9.2 Linked Data Structures | Introduction to Programming Using Java

Now, suppose that we want to know how many levels of supervisors there are between a given employee and the boss. We just have to follow the chain of command through a series of supervisor links, and count how many steps it takes to get to the boss:

Chapter 9.2 Linked Data Structures | Introduction to Programming Using Java

As the while loop is executed, runner points in turn to the original employee, emp, then to emp’s supervisor, then to the supervisor of emp’s supervisor, and so on. The count variable is incremented each time runner “visits” a new employee. The loop ends when runner.supervisor is null, which indicates that runner has reached the boss. At that point, count has counted the number of steps between emp and the boss.

In this example, the supervisor variable is quite natural and useful. In fact, data structures that are built by linking objects together are so useful that they are a major topic of study in computer science. We’ll be looking at a few typical examples.

In this section and the next, we’ll be looking at linked lists. A linked list consists of a chain of objects of the same type, linked together by pointers from one object to the next. This is much like the chain of supervisors between emp and the boss in the above example. It’s also possible to have more complex situations, in which one object can contain links to several other objects. We’ll look at an example of this in Section 9.4.

Chapter 9.2 Linked Data Structures | Introduction to Programming Using Java

 

SEE MORE:

 

Leave a Comment