Data Structures and Algorithms

Lecture - 1

 
 
 
CS-406
Data Structures and Algorithms
 Data Structures and Algorithms
2

Outline

This topic will describe:
• The concrete data structures that can be used to store
information
• The basic forms of memory allocation
• Contiguous
• Linked
• Indexed
• The prototypical examples of these:  arrays and linked lists
• Other data structures:
• Trees
• Hybrids
• Higher-dimensional arrays
 
 Data Structures and Algorithms
3

Memory Allocation

Memory allocation can be classified as either
• Contiguous
• Linked
• Indexed
 
Prototypical examples:
• Contiguous allocation: arrays
• Linked allocation: linked lists
 Data Structures and Algorithms
4

Memory Allocation

Contiguous, adj.
Touching or connected throughout in an unbroken sequence.
Meriam Webster
 
Touching, in actual contact, next in space; meeting at a
common boundary, bordering, adjoining.
www.oed.com
 
 Data Structures and Algorithms
5
2.2.1
Contiguous Allocation

An array stores n objects in a single contiguous space
of memory
Unfortunately, if more memory is required, a request
for new memory usually requires copying all information
into the new memory
• In general, you cannot request for the operating
system to allocate to you the next n memory
locations
 Data Structures and Algorithms
6

Linked Allocation

Linked storage such as a linked list associates two
pieces of data with each item being stored:
• The object itself, and
• A reference to the next item
• In C++ that reference is the address of the next node
 Data Structures and Algorithms
7

Linked Allocation

This is a class describing such a node
 
template <typename Type>
class Node {
        private:
        Type element;
        Node *next_node;
    public:
                // ...
};
 Data Structures and Algorithms
8

Linked Allocation
The operations on this node must include:
• Constructing a new node
• Accessing (retrieving) the value
• Accessing the next pointer
 
Node( const Type& = Type(), Node* = nullptr );
Type retrieve() const;
Node *next() const;

Pointing to nothing has been represented as:
   C NULL
   Java/C# null
   C++ (old) 0
   C++ (new) nullptr
   Symbolically Ø
 Data Structures and Algorithms
9

Linked Allocation

For a linked list, however, we also require an object
which links to the first object
 
The actual linked list class must store two pointers
• A head and tail:
Node *head;
Node *tail;
Optionally, we can also keep a count
int count;
The next_node of the last node is assigned nullptr
 
 Data Structures and Algorithms
10

Linked Allocation

The class structure would be:
 
template <typename Type>
class List {
    private:
        Node<Type> *head;
        Node<Type> *tail;
        int count;
    public:
        // constructor(s)...
        // accessor(s)...
        // mutator(s)...
};
 Data Structures and Algorithms
11

Indexed Allocation

With indexed allocation, an array of pointers
(possibly NULL) link to a sequence of allocated
memory locations
 
Used in the C++ standard template library
 
 
 Data Structures and Algorithms
12

Indexed Allocation

Matrices can be implemented using indexed allocation:

1 2 3
4 5 6
 Data Structures and Algorithms
13

Indexed Allocation
Matrices can be implemented using indexed allocation
• Most implementations of matrices (or higher-dimensional arrays) use indices
pointing into a single contiguous block of memory

Row-major order Column-major order

1 2 3
4 5 6

C, Python Matlab, Fortran
 Data Structures and Algorithms
14

Other Allocation Formats

We will look at some variations or hybrids of these
memory allocations including:
• Trees
• Graphs
• Deques (linked arrays)
• inodes
 
 
 
 
 Data Structures and Algorithms
15

Trees

The linked list can be used to store linearly ordered
data
• What if we have multiple next pointers?
 
A rooted tree is similar
to a linked list but with multiple next
pointers
 
 
 
 Data Structures and Algorithms
16

Trees

A tree is a variation on a linked list:
• Each node points to an arbitrary number of subsequent nodes
• Useful for storing hierarchical data
• We will see that it is also useful for storing sorted data
• Usually we will restrict ourselves to trees where each node
points to at most two other nodes
 Data Structures and Algorithms
17

Graphs

Suppose we allow arbitrary relations between any two
objects in a container
• Given n objects, there are n2 – n possible relations
2
• If we allow symmetry, this reduces to n n
  2
• For example, consider the network
 Data Structures and Algorithms
18

Arrays
Suppose we allow arbitrary relations between any two
objects in a container
• We could represent this using a two-dimensional array
• In this case, the matrix is
symmetric   A B C D E F G H I J K L
  A   ×       ×       ×    
B ×   ×     × ×     ×    
C   ×   ×     × ×     × ×
D     ×   ×             ×
E       ×         ×      
F × ×                    
G   × ×         ×        
H     ×       ×   ×      
I         ×     ×        
J × ×                 ×  
K     ×             ×   ×
L     × ×             ×  
 Data Structures and Algorithms
19

Array of Linked Lists
Suppose we allow arbitrary relations between any two objects in
a container
• Alternatively, we could use a hybrid:  an array of linked lists

   
A  
B  
C  
D  
E  
F  
G  
H  
I  
J  
K  
L  
 Data Structures and Algorithms
20

Linked Arrays
Other hybrids are linked lists of arrays
• Something like this is used for the C++ STL deque container
 
For example, the alphabet could be stored either as:
• An array of 26 entries, or
• A linked list of arrays of 8 entries
 Data Structures and Algorithms
21

Hybrid data structures
The Unix inode was used to store information about
large files
• The first twelve entries can reference the first twelve blocks (48 KiB)
 Data Structures and Algorithms
22

Hybrid data structures

The Unix inode was used to store information about large
files
• The next entry is a pointer to an array that stores the next 1024
blocks
 

This stores files up to 4 MiB on a 32-bit computer
 Data Structures and Algorithms
23

Hybrid data structures
The Unix inode was used to store information about
large files
• The next entry has two levels of indirection for files up to 4 GiB
 Data Structures and Algorithms
24

Summary

In this topic, we have introduced the concept of data
structures
• We discussed contiguous, linked, and indexed allocation
• We looked at arrays and linked lists
• We considered
• Trees
• Two-dimensional arrays
• Hybrid data structures
• We considered the run time of the algorithms required to perform
various queries and operations on specific data structures:
• Arrays and linked lists