20162314 2017-2018-1 《Program Design & Data Structures》Learning Summary Of The Fifth Week
Summary of Key Concepts
A collection is an object that gathers and organizes other objects.
Elements in a collection are typically organized by the order of their addition to the collection or by some inherent relationship among the elements.
A collection is an abstraction where the details of the implementation are hidden.
A data structure is the underlying programming constructs used to implement a collection.
Stack elements are processed in a LIFO manner—the last element in is the first element out.
A programmer should choose the structure that is appropriate for the type of data management needed.
A polymorphic reference uses the type of the object, not the type of the reference, to determine which version of a method to invoke.
A Java interface defines a set of abstract methods and is useful in separating the concept of an abstract data type from its implementation.
By using the interface name as a return type, the interface doesn’t commit the method to the use of any particular class that implements a stack.
A stack is the ideal data structure to use when evaluating a postfix expression.
Errors and exceptions represent unusual or invalid processing.
The implementation of the collection operations should not affect the way users interact with the collection.
How we handle exceptional conditions determines whether the collection or the user of the collection controls the particular behavior.
For efficiency, an array-based stack implementation keeps the bottom of the stack at index 0.
Object reference variables can be used to create linked structures.
A linked list is composed of objects that each point to the next object in the list.
A linked list dynamically grows as needed and essentially has no capacity limitations.
The order in which references are changed is crucial to maintaining a linked list.
Dealing with the first node in a linked list often requires special handling.
Implementing a list with a sentinel node or dummy node as the first node eliminates the special cases dealing with the first node.
Objects that are stored in a collection should not contain any implementation details of the underlying data structure.
Any implementation of a collection can be used to solve a problem as long as it validly implements the appropriate operations.
A linked implementation of a stack adds and removes elements from one end of the linked list.
The java.util.Stack class is derived from Vector, which gives a stack inappropriate operations.
Problem and solution in teaching materials.
Why should a linked list node be separate from the element stored on the list?
It is unreasonable to assume that every object that we may want to put in a collection can be designed to cooperate with the collection implementation.
What do the LinkedStack
and ArrayStack classes have in common? Both the LinkedStack
and ArrayStack classes implement the StackADT interface. This means that they both represent a stack collection, providing the necessary operations needed to use a stack.
What would be the time complexity of the push operation if we chose to push at the end of the list instead of the front?
To push at the end of the list, we would have to traverse the list to reach the last element. This traversal would cause the time complexity to be O(n). An alternative would be to modify the solution to add a rear reference that always pointed to the last
element in the list. This would help the time complexity for add but would have consequences if we try to remove the last element.
What impact would the use of sentinel nodes or dummy nodes have upon a doubly linked list implementation?
It would take two dummy records in a doubly linked list, one at the front and one at the rear, to eliminate the special cases when dealing with the first and last node.
How to expand capacity in arraystack?
The expandCapacity method is implemented to double the size of the array as needed. Of course since an array cannot be resized once it is instantiated, this method simply creates a new larger array, and then copies the contents of the old
array into the new one. It serves as a support method of the class and can therefore be implemented with private visibility.
To start with, change the arraystack into double size as needed.Then, use the for-loop to copy the content of the old array into the new one.
Last, make the new one is stack.
Code hosting
Summary of error for last week.
Linear search is always more effective than binary search.The answer should be false, for the situation of "n = 2".
Evaluate for my partner
- Advantage and problem in the blog：
- Concise and comprehensie
- Uncleary to the content
- Mould is amazing
- Advantage and problem in the code：
- Serious writing.
- Wonderful idea
- Too less
Learning situation of partner
- Learning content of partner：
- Algorithm
- Recursion
- HanoiTowers and maze
Anything else that want to say
- It's not easy to persere on utizing English to write a blog.But I'm getting used to doing this because of the benefit.
Academic progress check
| Code line number（increasing/accumulative） | Blog number（inc/acc） | studying time（inc/acc） | progress | |
|---|---|---|---|---|
| target | 5000lines | 30articles | 400hours | |
| First week | 180/180 | 1/1 | 20/20 | |
| Second week | 1049/1229 | 1/2 | 18/38 | |
| Third week | 1037/2266 | 3/7 | 22/60 | |
| Fourth week | 300/1300 | 2/9 | 30/90 |