3: Basic Data Structures and Abstract Data Types
- Page ID
- 46791
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Upon completion of this unit you should be able to:
- identify data structures used to organize data in a computer
- describe abstract data types used in the organization of data in the computer
- explain the data structures used to organize data for the efficient use of the computer
Unit Introduction
This section introduces the learner to the basic types of data structures that are used in computer systems. Data structures also called data types are the particular ways of organizing data in a computer so that it can be used efficiently. Abstract data types (ADT) are set of values (the carrier set), and operations on these values. Also arrays, lists, linked lists, stacks, queues, hashing and trees are included in this section.
- Data structure: the programmatic way of storing data so that data can be used efficiently
- Abstract data type: the carrier set together with their operations
- Array: a fixed length, ordered collection of values of the same type stored in contiguous memory locations
- Lists: an abstract data type that represents a sequence of values, where the same value may occur more than once
- Linked Lists: a data structure consisting of a group of nodes which together represent a sequence
- Stack: a particular kind of abstract data type or collection in which the principal operations on the collection are the push and pop
- Queues: an abstract data type or collection in which the entities in the collection are kept in order and the only operations on the collection are the addition of entities to the rear terminal position, and removal of entities from the front terminal position
- Hashing: a method for storing and retrieving records from a database
- Trees: a data structure made up of nodes or vertices and edges and is not cyclic
Learning Activities
- 3.1: Activity 1 - Data Structures
- This section introduces the learner to the different data structures that are used to organize data in the computer. Better data organization ensures efficient utilization of the computer. These include arrays, lists, linked lists, stacks, queues, hashing and trees. The different data structures offer advantages to algorithm designers in that they are able to know which one would enable efficient use of the computer.
- 3.2: Activity 2 - Abstract Data Type
- This section introduces the learner to abstract data types (ADT). The ADT section describes the different data types behaviour 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. All in all different data structures have different operations performed on them.
- 3.3: Unit Summary
- This unit covered data structures and abstract data types. In the data structures section, different structures were discussed. These included arrays, links, Linked lists, Stacks, Queues, Hashing and Trees. These structures are used to organize data in the computer to make it work efficiently. In the abstract data types section, the operations performed on the data structures are discussed.