Abstract data structures: Difference between revisions

From Computer Science Wiki
No edit summary
 
(39 intermediate revisions by 2 users not shown)
Line 1: Line 1:
[[File:Square-target-interface-symbol.png|right|frame|Abstract data types<ref>http://www.flaticon.com/</ref>]]
[[File:Square-target-interface-symbol.png|right|frame|Abstract data types<ref>http://www.flaticon.com/</ref>]]


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.
In computer science, an abstract data type (ADT) is a model for data types where a data type is defined by its behavior 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).<ref>https://en.wikipedia.org/wiki/Abstract_data_type</ref>
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).<ref>https://en.wikipedia.org/wiki/Abstract_data_type</ref>


In more common language, a data structure is just some '''arrangement of data that we've built into an orderly arrangement.'''
The reason we use abstract structures is because they efficiently use memory based on the design of the data stored in them. With very large amounts of data or very frequently changing data, the data structure can make a huge difference in the efficiency (run time) of your computer program.
 
In more common language, '''an abstract data structure is a collection of related data items that a stored together in a clear, structured form.
'''
== A perfectly lovely overview ==
 
<html>
<iframe width="560" height="315" src="https://www.youtube.com/embed/DuDz6B4cqVc" frameborder="0" allowfullscreen></iframe>
</html>
 
== Some types of abstract data structures ==
== Some types of abstract data structures ==
=== Assessed by the IB ===
#  [[static and dynamic data structure]]


# [[arrays]]
# [[arrays]]
# [[two-dimensional arrays]]
# [[stack]]
# [[stack]]
# [[queue]]
# [[queue]]
# [[linked list]]
# [[linked list]]
# [[tree]]
# [[binary tree]]
# [[binary tree]]
# [[collections]]
# [[recursion]]
=== NOT Assessed by the IB, but you should know them ===
# [[lists]]
# [[dictionaries]]
# [[sets]]
# [[tuple]]
# [[enum]]
# [[struct]]
# [[char]]
# [[vector]]


== Basic operations of data structures ==
== Basic operations of data structures ==
Line 20: Line 47:
[[File:Basic operations of arrays.png]]
[[File:Basic operations of arrays.png]]


== Types of abstract data structures ==  
== Comparison of different data structures ==  
 
=== Thinking recursively ===
* [[Recursive thinking]]
* [[Recursive algorithms]]
 
=== Abstract data structures ===
 
* [[Two dimensional arrays]]
* [[Stack]]
* [[Queue]]




=== Linked lists ===
* [[Dynamic data structures]]
* [[Linked lists]]
=== Trees ===
* [[Trees]]
== Comparison of different data structures ==
'''I'm still working on this. :-) '''




Line 51: Line 56:
| '''Data Structure''' || '''Strengths''' || '''Weaknesses'''
| '''Data Structure''' || '''Strengths''' || '''Weaknesses'''
|-
|-
| '''[[arrays]]'''  ||  ** direct indexing ** Easy to create and use || ** Sorting and searching
| '''[[arrays]]'''  || Inserting and deleting elements, iterating through the collection || Sorting and searching,  Inserting and deleting - especially if you are inserting and deleting at the beginning or the end of the array
** Inserting and deleting - especially if you are inserting and deleting at the beginning or the end of the array
|-
 
| '''[[linked list]]''' ||  direct indexing, Easy to create and use || direct access, searching and sorting
| '''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.<ref>https://en.wikipedia.org/wiki/Interview</ref>  || 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.
|-
| '''[[stack]] and [[queue]]'''  ||  designed for LIFO / FIFO || direct access, searching and sorting
|-
| '''[[binary tree]]'''  || speed of insertion and deletion, speed of access, maintaining sorted order || some overhead
|-
|-
| '''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.<ref>https://en.wikipedia.org/wiki/Observational_techniques#Three_Approaches</ref>
|}
|}




[[linked list]]
* Fixed structures are faster / smaller
* When you are considering if you should use an abstract data structure, you should ask yourself: '''what holds the most data and what holds the most frequently changed data'''?


* Strengths
== Comparison of static vs dynamic data structures ==
** inserting and deleting elements
This comparison is used from [[IB Computer Science textbook | our computer science textbook]].
** iterating through the collection
{| style="width: 95%;" class="wikitable"
 
|-
* Weaknesses
| '''Static data structure''' || '''Dynamic data structure'''
** direct access
|-
** searching and sorting
| Inefficient as memory is allocated that may not be needed.|| Efficient as the amount of memory varies as needed.
 
|-
[[stacks and queues]]
| Fast access to each element of data as the memory location is fixed when the program is written. || Slower access to each element as the memory location is allocated at run-time.
|-
| Memory addresses allocated will be contiguous so quicker to access. || Memory addresses allocated may be fragmented so slower to access.
|-
|Structures are a fixed size, making them more predictable to work with. For example, they can contain a header. || Structures vary in size so there needs to be a mechanism for knowing the size of the current structure.
|-
| The relationship between different elements of data does not change. || The relationship between different elements of data will change as the program is run.
|-
|}


* Strengths
== Choosing which data structure to use ==
** designed for LIFO / FIFO


* Weaknesses
This graphic is used with tremendous gratitude from Dartford Grammar School Computer Science Department.
** direct access
** searching and sorting


[[hash tables]]
[[File:Choosing a data type flow chart.png]]
 
* Strengths
** speed of insertion and deletion
** speed of access
 
* Weaknesses
** some overhead
** retrieving in a sorted order
** searching for a specific value
 
[[Sets]]
 
* Strengths
** checking for membership (is an object in a collection)
** avoiding duplicates
 
* Weaknesses
** direct access
** almost everything else
 
[[binary search trees]]
 
* 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 ==
== Standards ==
Line 131: Line 110:
* Describe the features and characteristics of a dynamic data structure.
* Describe the features and characteristics of a dynamic data structure.
* Describe how linked lists operate logically.
* Describe how linked lists operate logically.
* Sketch linked lists (single, double and circular).
* Describe the characteristics and applications of a collection.
* Construct algorithms using the access methods of a collection.
* Discuss the need for sub-programmes and collections within programmed solutions.
* Construct algorithms using pre-defined sub-programmes, one-dimensional arrays and/or collections.


* Sketch linked lists (single, double and circular).
* Describe how trees operate logically (both binary and non-binary).
* Describe how trees operate logically (both binary and non-binary).
* Define the terms: parent, left-child, right-child, subtree, root and leaf.
* Define the terms: parent, left-child, right-child, subtree, root and leaf.

Latest revision as of 06:46, 26 April 2023

Abstract data types[1]

In computer science, an abstract data type (ADT) is a model for data types where a data type is defined by its behavior 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]

The reason we use abstract structures is because they efficiently use memory based on the design of the data stored in them. With very large amounts of data or very frequently changing data, the data structure can make a huge difference in the efficiency (run time) of your computer program.

In more common language, an abstract data structure is a collection of related data items that a stored together in a clear, structured form.

A perfectly lovely overview[edit]

Some types of abstract data structures[edit]

Assessed by the IB[edit]

  1. static and dynamic data structure
  1. arrays
  2. two-dimensional arrays
  3. stack
  4. queue
  5. linked list
  6. tree
  7. binary tree
  8. collections
  9. recursion

NOT Assessed by the IB, but you should know them[edit]

  1. lists
  2. dictionaries
  3. sets
  4. tuple
  5. enum
  6. struct
  7. char
  8. vector

Basic operations of data structures[edit]

I found this excellent slide from Simon Allardice.

Basic operations of arrays.png

Comparison of different data structures[edit]

Data Structure Strengths Weaknesses
arrays Inserting and deleting elements, iterating through the collection Sorting and searching, Inserting and deleting - especially if you are inserting and deleting at the beginning or the end of the array
linked list direct indexing, Easy to create and use direct access, searching and sorting
stack and queue designed for LIFO / FIFO direct access, searching and sorting
binary tree speed of insertion and deletion, speed of access, maintaining sorted order some overhead


  • Fixed structures are faster / smaller
  • When you are considering if you should use an abstract data structure, you should ask yourself: what holds the most data and what holds the most frequently changed data?

Comparison of static vs dynamic data structures[edit]

This comparison is used from our computer science textbook.

Static data structure Dynamic data structure
Inefficient as memory is allocated that may not be needed. Efficient as the amount of memory varies as needed.
Fast access to each element of data as the memory location is fixed when the program is written. Slower access to each element as the memory location is allocated at run-time.
Memory addresses allocated will be contiguous so quicker to access. Memory addresses allocated may be fragmented so slower to access.
Structures are a fixed size, making them more predictable to work with. For example, they can contain a header. Structures vary in size so there needs to be a mechanism for knowing the size of the current structure.
The relationship between different elements of data does not change. The relationship between different elements of data will change as the program is run.

Choosing which data structure to use[edit]

This graphic is used with tremendous gratitude from Dartford Grammar School Computer Science Department.

Choosing a data type flow chart.png

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 the characteristics and applications of a collection.
  • Construct algorithms using the access methods of a collection.
  • Discuss the need for sub-programmes and collections within programmed solutions.
  • Construct algorithms using pre-defined sub-programmes, one-dimensional arrays and/or collections.
  • 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.

References[edit]

  1. ↑ http://www.flaticon.com/
  2. ↑ https://en.wikipedia.org/wiki/Abstract_data_type

Produce a plan, simulation or model.

Provide an answer from a number of possibilities. Recognize and state briefly a distinguishing fact or feature.

Follow and record the action of an algorithm.

Give a detailed account or picture of a situation, event, pattern or process.

Develop information in a diagrammatic or logical form.

Give a detailed account including reasons or causes.

Represent by means of a diagram or graph (labelled as appropriate). The sketch should give a general idea of the required shape or relationship, and should include relevant features.

Offer a considered and balanced review that includes a range of arguments, factors or hypotheses. Opinions or conclusions should be presented clearly and supported by appropriate evidence.

Give the precise meaning of a word, phrase, concept or physical quantity.

Give a specific name, value or other brief answer without explanation or calculation.

Give a specific name, value or other brief answer without explanation or calculation.

Propose a solution, hypothesis or other possible answer.

Retrieved from "https://computersciencewiki.org/index.php?title=Abstract_data_structures&oldid=12084"