Please enable JavaScript.
Coggle requires JavaScript to display documents.
M5 - Algorithms and Data Structures, typedef struct list { - Coggle Diagram
M5 - Algorithms and Data Structures
1 Data Structures and Algorithms
1.2 Abstract Data Types (ADT) and Data Structures
A
type
is a collection of values. Like int, boolean, char...
A
data item
is a piece of information or a record whose value is drawn from a type. A data item is said to be a member of a type.
A
data type
is a type together with a collection of operations to manipulate the type.
Data types have both a logical and a physical form
The definition of the data type in terms of an ADT is its logical form.
The implementation of the data type as
a data structure is its physical form.
An
abstract data type (ADT)
is the realization of a data type as a software
component.
managing complexity through abstraction.
A
data structure
is the implementation for an ADT
an ADT and its implementation together make up a
class
An
object
is an instance of a class, that is, something that is created and takes up storage during the execution of a computer program.
Each operation associated with the ADT is implemented by a
member function or method
The variables that define the space required by a data item are referred to as
data members
The related term
file structure
often refers to the organization of data on peripheral storage, such as a disk drive or CD.
The ADT is implemented in one part of the program by a particular data structure.
There are often many approaches to solving a problem. How do we choose between them? At the heart of computer program design are two (sometimes conflicting) goals:
To design an algorithm that is easy to understand, code, and debug.
To design an algorithm that makes efficient use of the computer’s resources
4 Lists, Stacks, and Queues
4.1 Lists
4.1.1 Array-Based List Implementation
Composite type:
1 int maxSize; // capacity
2 int listSize; // number of elements
3 int curr; // position of the cursor
4 E[] listArray; // array with values
Algorithms:
List create list(int size);
void insert(List l, E it);
void moveToStart(List l);
void moveToEnd(List l);
void prev(List l);
void next(List l).
E remove(List l)
4.1.2 Linked Lists
uses dynamic memory allocation, that is, it allocates memory for new list elements as needed.
This data structure is known as a
dynamic array
The disadvantage of this approach is that it takes time to deal with space adjustments on the array
To analyze the overall cost of dynamic array
operations over time, we need to use a technique known as amortized analysis,
Composite type(Link):
1 E element; // value stored in this link/node
2 Link next; // reference to the next link/node
Composite type (List):
1 Link head;
2 Link tail;
3 Link curr;
4 int cnt; // list size
Algorithms (Link):
Link create link(E it, Link nextval);
Algorithms (List):
List create list();
void insert(List l, E it);
void moveToStart(List l);
void prev(List l);
void next(List l);
E remove(List l)
4.1.3 Comparison of List Implementations (Array-based x Linked)
Array-based lists
have the disadvantage that their size must be predetermined
before the array can be allocated.
Array-based lists cannot grow beyond their predetermined size
The amount of space required by a
linked list is Θ(n)
, while the space required by the
array-based list implementation is Ω(n)
,
Array-based lists have the advantage that there is no wasted space for an individual element
The array-based list will then be more space
efficient,
by a constant factor
, than the linked implementation.
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
The amount of space required for the
array-based list is = DE
; D = the maximum number of list elements that
can be stored in the array; E = the size of a data element in storage units.
The smaller of these expressions for a given value n determines the more space-efficient implementation for n elements
2 more items...
The amount of space required for the
linked list is n(P + E).
; n = the number of elements currently in the list; P = the size of a pointer in storage units.
Linked lists require that an extra pointer be added to every list node
Linked lists
have the advantage that they only need space for the objects actually on the list
4.1.4 Element Implementations
For
small elements
such as an integer, this makes sense.
If the elements are payroll records, it might be desirable for the list node to store a pointer
to the record rather than store a copy of the record itself
The disadvantage of storing a pointer to
each element is that the pointer requires space of its own
The third issue that users of the list implementations must face is primarily of concern when programming in languages that do not support automatic
garbage collection
how to deal with the memory of the objects stored on the list
when the list is deleted or the clear method is called.
the user of the list must be responsible for deleting these objects when that is appropriate
Two implementations for the list ADT:
the array-based list and the linked list
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
.
“ordered” in this context to mean that the list elements are sorted by value.
In the simple list implementations discussed in this chapter, all elements of the list have the same data type.
list ADT can be used for lists of integers, lists of characters, lists of payroll records,
even lists of lists.
A list is said to be
empty
when it contains no elements. The number of elements currently stored is called the
length
of the list. The beginning of the list is called the
head
, the end of the list is called the
tail
.
OPERATIONS (let E be an arbitrary data type):
void clear(List l);
void insert(List l, E item);
void append(List l, E item);
E remove(List l);
void moveToStart(List l);
void moveToEnd(List l);
1 more item...
Along with presenting these fundamental data structures, the other goals of the chapter are to:
(1) Give examples of separating a logical representation in the form of an ADT from a physical implementation for a data structure.
(2) Illustrate the use of asymptotic analysis in the context of some simple operations that you might already be familiar with.
(3) Introduce the concept and use of dictionaries
typedef struct list {
int maxSize; int listSize; int curr; E* listArray;
} List;