Data Structures: Intro Flashcards
What are the two characteristics of a data structure?
- defines a specific domain of values
- defines operations that can be performed on
that domain of values.
What are Abstract data types (ADT’s)?
Abstract Data Type provides abstraction
The term abstract data type, or ADT, defines operations on values, using functions, without any specification of how the values are to be represented or how the operations are to be implemented.
ADT’s are blueprints, that define an interface, but not the implementation. It hides the implementation from the client/user
ADT’s can be implemented in multiple ways e.g. A stack is an ADT that can be implemented using an Array or a Linked List, but regardless of its implementation, the client will always use it in the same way, by calling push, or pop.
Difference between primitive and user-defined data types?
The values and operations of user-defined data types are not specified in the language itself but are specified by the user.
What is the program that uses a data structure called?
Client
What is the program called that implements a data structure?
Implementation
What is a data structure?
An efficient organizaiton of data.
Difference between ADT and data structures?
data structures are implementations of ADT’s.
ADT tells us what is to be done, whereas data structures tell us how to do it.
What are the advantages of data structures?
Efficiency: The proper choice of data structure makes the program efficient in terms of time and space.
Reusability: One implementation can be used by multiple client programs.
Abstraction: Client programs do not have to worry about implementation, the ADT provides an interface for client interaction.
What are the two basic types of Data structures?
linear and non-linear
Linear data structures
A data structure is linear when all the elements are arranged in a linear or sequential order.
Every element has only one predecessor and one successor, with the exception of the first and last element.
E.g. Arrays, linked lists, queues, stacks
Non-Linear data structures
A data structure is Non-Linear when it’s elements are NOT arranged in linear or sequential order. The elements have more than one predecessor or successor
e.g. Trees or Graphs
Static Data Structures
Memory is allocated at compile time, therefore size is fixed.
Advantage: Faster access to elements
Disadvantages: Slower insertion and deletion
e.g. Arrays
Dynamic Data Structures
Memory is allocated at run time, therefore maximum size is flexible.
Advantage: Faster insertion and Deletion
Disadvantage: Slower access to elements.
e.g. Linked lists
What is Data?
quantities, symbols or characters on which operations can be performed by a computer, and which may be transmitted or stored.
