Abstract data structures
In computer science, an abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.
Formally, an ADT may be defined as a "class of objects whose logical behavior is defined by a set of values and a set of operations"; this is analogous to an algebraic structure in mathematics. What is meant by "behavior" varies by author, with the two main types of formal specifications for behavior being axiomatic (algebraic) specification and an abstract model; these correspond to axiomatic semantics and operational semantics of an abstract machine, respectively. Some authors also include the computational complexity ("cost"), both in terms of time (for computing operations) and space (for representing values).[2]
In more common language, a data structure is just some arrangement of data that we've built into an orderly arrangement.
Some types of abstract data structures[edit]
Basic operations of data structures[edit]
I found this excellent slide from Simon Allardice.
Types of abstract data structures[edit]
Thinking recursively[edit]
Abstract data structures[edit]
Linked lists[edit]
Trees[edit]
Comparison of different data structures[edit]
I'm still working on this. :-)
| Data Structure | Strengths | Weaknesses | ||||
| arrays | ** direct indexing ** Easy to create and use | ** Sorting and searching
|
Interviews | An interview is a conversation where questions are asked and answers are given. In common parlance, the word "interview" refers to a one-on-one conversation with one person acting in the role of the interviewer and the other in the role of the interviewee. The interviewer asks questions, the interviewee responds, with participants taking turns talking. Interviews usually involve a transfer of information from interviewee to interviewer, which is usually the primary purpose of the interview, although information transfers can happen in both directions simultaneously.[3] | You can gather in-depth information and explore topics which are tangentially related to the system. There is flexibility in information | You are usually limited to few people, not many people. If an interview isn't structured, you may get fragmented information. It can be harder to quantify requirements from an interview. |
| Direct observations | Direct observation is a social research technique that involves the direct observation of phenomena in their natural setting. | observational research tends to be less reliable but often more valid. The main advantage of observational research is flexibility. The researchers can change their approach as needed. Also it measures behavior directly, not reports of behavior or intentions. | The problem with this approach is subjects may modify their behaviour when they know they are being watched. They portray their “ideal self” rather than their true self in what is called the Hawthorne Effect.[4] |
- Strengths
- inserting and deleting elements
- iterating through the collection
- Weaknesses
- direct access
- searching and sorting
- Strengths
- designed for LIFO / FIFO
- Weaknesses
- direct access
- searching and sorting
- Strengths
- speed of insertion and deletion
- speed of access
- Weaknesses
- some overhead
- retrieving in a sorted order
- searching for a specific value
- Strengths
- checking for membership (is an object in a collection)
- avoiding duplicates
- Weaknesses
- direct access
- almost everything else
- Strengths
- speed of insertion and deletion
- speed of access
- maintaining sorted order
- Weaknesses
- some overhead
- Fixed structures are faster / smaller
- Ask yourself: what holds the most data and what holds the most frequently changed data
Standards[edit]
- Identify a situation that requires the use of recursive thinking.
- Identify recursive thinking in a specified problem solution.
- Trace a recursive algorithm to express a solution to a problem.
- Describe the characteristics of a two- dimensional array.
- Construct algorithms using two- dimensional arrays.
- Describe the characteristics and applications of a stack.
- Construct algorithms using the access methods of a stack.
- Describe the characteristics and applications of a queue.
- Construct algorithms using the access methods of a queue.
- Explain the use of arrays as static stacks and queues.
- Describe the features and characteristics of a dynamic data structure.
- Describe how linked lists operate logically.
- Sketch linked lists (single, double and circular).
- Describe how trees operate logically (both binary and non-binary).
- Define the terms: parent, left-child, right-child, subtree, root and leaf.
- State the result of inorder, postorder and preorder tree traversal.
- Sketch binary trees.
- Define the term dynamic data structure.
- Compare the use of static and dynamic data structures.
- Suggest a suitable structure for a given situation.