Please enable JavaScript.
Coggle requires JavaScript to display documents.
Abstract Data Types and Data Structures - Coggle Diagram
Abstract Data Types and Data Structures
Definitions
Type is a colection of values
Boolean type consists of the values True and False
The interger is a simple type because its values contain no subparts
An aggregate type is a structure, union, or array type.
Data type
It is a type together with a collection of operations to manipulate
the type.
Data types have both a logical and a physical form
Abstract data type (ADT)
It is the realization of a data type as a software
component.
An ADT does not specify how the data type is implemented.
Data structure
It is the implementation for an ADT.
It is one istance of a important principle that must be understood by any sucessful computer scientist.
Fundamental Data Structures
Lists
The most important concept related to lists is that of position
We define a list to be a finite, ordered sequence of data items known as elements.
We said that a list is empty when it contains no elements, the number of elements is called lenght
Sorted lists have their elements positioned in ascending order of value
A list should be able to grow and shrink in size as we insert
and remove elements.
Unsorted lists have no particular relationship between element values and
positions.
Array-Based List Implementation
See algorithm on page 100
Class AList’s private portion contains the data members for the array-based
list.
listArray must be allocated at some fixed size, the size of the array must be
known when the list object is created.
Maxsize is maximum permitted size.
Because listArray, maxSize, listSize, and curr are all declared to be private, they may only be accessed by methods of Class AList
Most of the other member functions for Class AList simply access the current
list element or move the current position.
Linked List
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers
singly linked list
s a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail). Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list.
See algorithm on page109
Comparation of list implementation
Array-based
Array-based lists have the disadvantage that their size must be predetermined
before the array can be allocated.
Array-based lists have the advantage that there is no wasted space for an individual element
A simple formula can be used to determine whether the array-based list or
linked list implementation will be more space efficient in a particular situation.
Linked list
Linked lists have the
advantage that they only need space for the objects actually on the list
Doubly Linked Lists
Doubly linked list is a type of data structure that is made up of nodes that are created using self referential structures. Each of these nodes contain three parts, namely the data and the reference to the next list node and the reference to the previous list node.
