Data Structures with Java
data structures with java book, data structures and algorithms in java, data structures in java – pdf, data structures in python, data structures interview questions, data structures tutorial, data structures types, data structures in java examples
Short Summary of the Book:
SOFTWARE DESIGN AND DEVELOPMENT
Successful computer software is produced in a sequence of
stages that are typically managed by separate teams of developers.
These stages are illustrated in Figure 1.1.
The first stage is a recognition of the problem to be solved. In
a corporate setting, this determination could come from market
The second stage, which might be omitted as a formal
process, is a study of whether the project is feasible. For
example, do the development tools exist to produce the
In the third stage, a document is typically produced that
specifies precisely what the software should do. This requirements
document should have enough detail to be used as a
standard when the completed software is tested.
In the fourth stage, a thorough analysis is done before any
effort or resources are spent designing and implementing the
project. This could include a survey of comparable software
already available and a cost-benefit analysis of the value of
spending the anticipated resources.
Once a decision has been made to proceed, the software
design team works from the requirements document to design
the software. This includes the specification of all the software
components and their interrelationships. It may also require the
specification of specialized algorithms that would be implemented
in the software.
The implementation consists of programmers coding the
design to produce the software.
The testing team attempts to ensure that the resulting
software satisfies the requirements document. Failure at this point may require a redesign or even
some fine-tuning of the requirements. Those eventualities are represented by the two feedback
loops shown in Figure 1.1.
Testing occurs at several levels. Individual classes and methods have to be tested separately, and then their success at working together must be verified. Finally, the product as a whole is tested against the requirements document.
One final aspect of software development that is not shown in the figure is the maintenance process. After the software has been delivered, its developers remain obliged to maintain it with corrected versions, service packages, and even major revisions. Any major revision itself would follow the same life cycle steps.
One common approach to software design is a top-down design strategy that gradually breaks the problem down into smaller parts. This is also called step-wise refinement. It focuses on the functional aspects of the problem and the implementation of algorithms. This procedure-oriented design is common in scientific programming.
In contrast, the object-oriented design focuses on the data components of the software, organizing the design around their representatives. For example, an air traffic control system might be designed in terms of airplanes, airports, pilots, controllers, and other “objects.”
The Java programming language is particularly well-suited for implementing object-oriented designs. All executable code in Java is organized into classes that represent objects. For this reason, Java is regarded as an object-oriented programming language.
An object is a software unit that is produced according to a unique class specification. It is
called an instance of its class, and the process of creating it is called instantiating the class. For example, this code instantiates java.util.Date class:
java.util.Date today = new java.util.Date();
The variable today is a reference to the object, as shown in Figure 1.2. Ignoring the distinction between a reference and the object to which it refers, we would also say today is the name of the java.util.Date object. A Java class consists of three kinds of members: fields, methods, and constructors. The fields hold the data for class objects, the methods hold the statements that are executed by the objects, and the constructors hold the code that initializes the objects’ fields. An object-oriented design specifies the classes that will be instantiated in the software. That design can be facilitated and illustrated by the Unified Modeling Language (UML). In UML, each class is represented by a rectangle with separate
parts for listing the class’s name, its fields, and its methods and
Figure 1.3 shows a UML diagram for a Person class with four fields (name, id, sex, and dob), a constructor, and three methods (isAnAdult(), setDob(), and toString()). Each of the eight class members is prefaced with a visibility symbol:
+ means public
# for protected
– for private
(Package visibility has no UML symbol.)
UML diagrams are independent of any implementing programming language. They are used in object-oriented design to specify objects. They should be easy to implement in Java, C++, or any other object-oriented programming language. They provide a kind of pseudo-code for classes. They specify the state (i.e., fields) and the behavior (i.e., methods) of an object without specifying how that behavior is accomplished. UML diagrams include no executable code. Specifying what an object can do without specifying how it does it is an abstraction. It allows the design stage to be separated from the implementation stage of the software development. It
also facilitates modification of the software by allowing an implementation to be changed
without affecting dependent modules. As long as a method’s behavior is unchanged, any invoking modules will be unaffected by a change in that method’s implementation.
For example, suppose that an airline reservation system uses the Person class specified by the UML diagram in Figure 1.3. Presumably, that software will invoke that class’s isAnAdult() method in various modules of the system. The “contract” specified by the software design only requires that the method return the right answer: x.isAnAdult() should be true if and only if x is an adult. How it computes that result is irrelevant. The implementation probably computes the chronological difference between the value of the private field x.dob and the value of the current date. But there is nothing in the contract that specifies that. Moreover, if the implementation
is changed, none of the other code in the reservation system would be affected by that
change. Such a change might be warranted by the preference of a different algorithm for computing chronological differences, or possibly by a redefinition of the meaning of “adult.” Concealing the implementation of a method from the clients who use the method is called information hiding. It is the software designer’s version of the spy’s principle that says, “If you don’t need to know it, then you’re are not allowed to know it.” It makes software easier to design, implement, and modify.
ABSTRACT DATA TYPES
Abstractions are used to help understand complex systems. Even though they are different, rocks and tennis balls fall at the same rate. The physicist uses the abstraction of imagining a single imaginary point mass to understand the physics of falling bodies. By ignoring the irrelevancies (diameter, weight), the abstraction allows the analyst to focus on the relevancies (height). Abstractions are widely used in software development. UML diagrams provide abstractions by focusing on the fields (the state) and methods (the behavior) of a class. But at some levels, even the fields of a class may be irrelevant.
An abstract data type (ADT) is a specification of only the behavior of instances of that type. Such a specification may be all that is needed to design a module that uses the type. Primitive types are like ADTs. We know what the int type can do (add, subtract, multiply, etc.). But we need not know how it does these operations. And we need not even know how an int is actually stored. As clients, we can use the int operations without having to know how they are implemented. In fact, if we had to think about how they are implemented, it would probably be a distraction from designing the software that will use them. Likewise, if you had to think about how your car manages to turn its front wheels when you turn the steering wheel, it would probably be more difficult to drive!