Java, Java, Java: Object-Oriented Problem Solving, 2022E

Subsection 16.10.1 Technical Terms

Subsection 16.10.2 Important Points

• A data structure is used to organize data and make them more efficient to process. An array is an example of a static structure, since its size does not change during a program’s execution. An ArrayList is an example of a dynamic structure, one whose size can grow and shrink during a program’s execution.
• A linked list is a linear structure in which the individual nodes of the list are joined together by references. A reference is a variable that refers to an object. Each node in the list has a link variable that refers to another node. An object that can refer to the same kind of object is said to be self-referential.
• The Node class is an example of a self-referential class. It contains a link variable that refers to a Node. By assigning references to the link variable, Node s can be chained together into a linked list. In addition to their link variables, Node s contain data variables, which should be accessible through public methods.
• Depending on the use of a linked list, nodes can be inserted at various locations in the list: at the head, the end, or in the middle of the list.
• Traversal algorithms must be used to access the elements of a singly linked list. To traverse a list you start at the first node and follow the links of the chain until you reach the desired node.
• Depending on the application, nodes can be removed from the front, rear, or middle of a linked list. Except for the front node, traversal algorithms are used to locate the desired node.
• In developing list algorithms, it is important to test them thoroughly. Ideally, you should test every possible combination of insertions and removals that the list can support. Practically, you should test every independent case of insertions and removals that the list supports.
• An Abstract Data Type (ADT) is a concept that combines two elements: A collection of data, and the operations that can be performed on the data. For the list ADT, the data are the values (Object s or int s) contained in the nodes that make up the list, and the operations are insertion, removal, and tests of whether the list is empty.
• In designing an ADT, it’s important to provide a public interface that can be used to access the ADT’s data. The ADT’s implementation details should not matter to the user and should, therefore, be hidden. A Java class definition, with its public and private aspects, is perfectly suited to implement an ADT.
• A stack is a list that allows insertions and removals only at the front of the list. A stack insertion is called a push and a removal is called a pop. The first element in a stack is usually called the top of the stack. The StackADT can easily be defined as a subclass of List. Stacks are used for managing the method call and return in most programming languages.
• A queue is a list that only allows insertions at the rear and removals from the front of a list. A queue insertion is called enqueue, and a removal is called dequeue. The QueueADT can easily be defined as a subclass of List. Queues are used for managing the various lists used by the CPU scheduler—such as the ready, waiting, and blocked queues.
• A binary search tree is a binary tree in which the ordered data stored at any node is greater than all data stored in the left subtree and is less than all data stored in the right subtree.