Data_Structures_in_Java 7,

Posted on | Edited on

7 List and Iterator ADTs

7.1 The List ADT

1
2
3
4
5
6
size();
isEmpty();
get(i);
set(i, e);
add(i, e);
remove(i);

7.2 Array Lists

dynamic array based on List.

7.2.1 Dynamic Arrays

7.2.2 Implementing a Dynamic Array

7.2.3 Amortized Analysis of Dynamic Arrays

7.2.4 Java’s StringBuilder class

7.4 Iterators

1
2
3
4
5
import java.util.Iterator;

hasNext();
next();
remove();

7.5 The Java Collections Framework

Imgur

7.5.1 List Iterators in Java

1
2
3
4
5
6
7
8
9
add(e);
hasNext();
hasPrevious();
previous();
next();
nextIndex();
previousIndex();
remove();
set(e);

7.5.2 Comparison to Our Positional List ADT

Imgur

7.5.3 List-Based Algorithms in the Java Collections Framework

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import java.util.Collections

copy(L_dest, L_src);
disjoint(C, D);
fill(L, e);
frequency(C, e);
max(C);
min(C);
replaceAll(L, e, f);
reverse(L);
rotate(L, d);
shuffle(L);
sort(L);
swap(L, i, j);

Converting Lists into Arrays:

1
2
toArray();
toArray(A);

Converting Arrays into List:

1
asList(A);

7.6 Sorting a Positional List

8 Trees

Imgur

Imgur

9 Priority Queues

1
2
3
4
5
insert(k, v);
min();
removeMin();
size();
isEmpty();

java.util.Priority

10 Maps, Hash Tables, and Skip Lists

10.1 Maps

java.util.Map;
Count word frequency

10.2 Hash Tables

Sorted Maps

Applications:
Flight Databases
Maxima Sets;

10.4 Skip Lists

11 Search Trees

12 Sorting and Selection

13 Text Processing

13.2 Pattern-Matching Algorithms

13.2.1 Brute Force

13.2.2 The Boyer-Moore Algorithm

13.2.3 The KMP Algorithm

13.3 Tries

13.3.3 Suffix Tries

13.3.4 Search Engine Indexing

13.4 Text Compression and the Greedy Method

13.4.1 The Huffman Coding Algorithm

13.4.2 The Greedy Method

13.5 Dynamic Programming

Matrix Chain-Product

DNA and Text Sequence Alignment