serverbrazerzkidai.blogg.se - Basic data types and operations

Describe the characteristics and applications of a collection.

Sketch linked lists (single, double and circular).

Describe how linked lists operate logically.

Describe the features and characteristics of a dynamic data structure.

Explain the use of arrays as static stacks and queues.

Construct algorithms using the access methods of a queue.

Describe the characteristics and applications of a queue.

Construct algorithms using the access methods of a stack.Describe the characteristics and applications of a stack.Construct algorithms using two- dimensional arrays.Describe the characteristics of a two- dimensional array.Trace a recursive algorithm to express a solution to a problem.Identify recursive thinking in a specified problem solution.Identify a situation that requires the use of recursive thinking.This graphic is used with tremendous gratitude from Dartford Grammar School Computer Science Department. The relationship between different elements of data will change as the program is run.Ĭhoosing which data structure to use The relationship between different elements of data does not change. Structures vary in size so there needs to be a mechanism for knowing the size of the current structure. Structures are a fixed size, making them more predictable to work with. Memory addresses allocated may be fragmented so slower to access. Memory addresses allocated will be contiguous so quicker to access. Slower access to each element as the memory location is allocated at run-time. Inefficient as memory is allocated that may not be needed.Įfficient as the amount of memory varies as needed.įast access to each element of data as the memory location is fixed when the program is written. This comparison is used from our computer science textbook. 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?Ĭomparison of static vs dynamic data structures.Speed of insertion and deletion, speed of access, maintaining sorted order 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 elements, iterating through the collection I found this excellent slide from Simon Allardice.Ĭomparison of different data structures Data Structure

NOT Assessed by the IB, but you should know them īasic operations of data structures Some types of abstract data structures Assessed by the IB

5 Comparison of static vs dynamic data structures.

4 Comparison of different data structures.

2.2 NOT Assessed by the IB, but you should know them.

2 Some types of abstract data structures.

In more common language, an abstract data structure is just some arrangement of data that we've built into an orderly arrangement. 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.

The reason we use abstract structures is because they efficiently use memory based on the design of the data stored in them. Some authors also include the computational complexity ("cost"), both in terms of time (for computing operations) and space (for representing values). 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. This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.įormally, 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. 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.