Fundamental Data Structures

Fundamental Data Structures

1. Data Types

   • Type is a collection of values, such as booleans and integers.
     • A record (like a bank account) is an example of an composite type.
     • A Data Item is a member (or a part) of a type
   • A data type is a type together with a collection of operations to manipulate the type.
     • An abstract data type (ADT) is the realization of a data type as a software component
       • A given ADT might be supported by more than one implementation
     • Data types have both a logical and a physical form, and the definition of the data type in terms of an ADT is its logical form.

2. Data Structures

   • A data structure is the implementation for an ADT.
     • In a object-oriented language as C++, and ADT and its implementation (data structure) together make up a class.
   • The term "data structure"often refers to data stored in a computer's main memory

3. Lists

   • We define a list to be a finite, ordered sequence of data items known as elements
     • Every element has a position in the list and a data type
     • sorted lists have their elements positioned in ascending order of value, while unsorted lists have no particular relationship between element values and positions
     • Given that we wish to support the concept of a sequence, with access to any position in the list, we need many of the member functions such as insert and moveToPos.
       • It is also important to support the concept of a current position, for example with the method moveToStart
         • The current position is where any action such as insertion or deletion will take place.
   • We increase the flexibility of the list ADT by writing it as a C++ template.
   • The declaration for abstract class List also makes private the class copy constructor and an overloading for the assignment operator. This protects the class from accidentally being copied

4. Array-Based List Implementation

   • Advantages and disadvantages
     • Array-based lists have the advantage that there is no wasted space for an in- dividual element
     • Array-based lists have the disadvantage that their size must be predetermined before the array can be allocated.
   • Because listArray must be allocated at some fixed size, the size of the array must be known when the list object is created
     • Because each list can have a differently sized array, each list must remember its maximum permitted size. Data member maxSize serves this purpose.
       • The array-based list implementation is defined to store list elements in contiguous cells of the array, so the insert, append, and remove methods must maintain this property

5. Linked Lists

   • The linked list uses dynamic memory allocation, that is, it allocates memory for new list elements as needed.
     • A linked list is made up of a series of objects, called the nodes of the list and it is a good practice to make a separate list node class
       • The list built from such nodes is called a singly linked list, or a one-way list, because each list node has a single pointer to the next node on the list.
       • Objects in the Link class contain an element field to store the element value, and a next field to store a pointer to the next node on the list
   • Advantages and disadvantages
     • Linked lists require that an extra pointer be added to every list node. If the element size is small, then the overhead for links can be a significant fraction of the total storage.
     • Linked lists have the advantage that they only need space for the objects actually on the list.

6. Freelists

   • Instead of making repeated calls to new and delete, the Link class can handle its own freelist
     • A freelist holds those list nodes that are not currently being used.
       • When a node is deleted from a linked list, it is placed at the head of the freelist. When a new element is to be added to a linked list, the freelist is checked to see if a list node is available. If so, the node is taken from the freelist. If the freelist is empty, the standard new operator must then be called.
   • The C++ free-store management operators new and delete are expensive to use, so Freelists are particularly useful for linked lists that periodically grow and then shrink.
   • The freelist variable declaration uses the keyword static. This creates a single variable shared among all instances of the Link nodes

7. Doubly Linked Lists

   • Allows convenient access from a list node to the next node and also to the preceding node on the list
     • It works by storing two pointers: one to the node following it (as in the singly linked list), and a second pointer to the node preceding it
   • It is easier to implement than a singly linked list
     • While the code for the doubly linked implementation is a little longer than for the singly linked version, it tends to be a bit more “obvious” in its intention, and so easier to implement and debug

Bilder und Dateien der Mindmap