Transcript Chapter5. Linear Lists

Ch5. Linear Lists –
Array Representation
© copyright 2006 SNU IDB Lab.
SNU
IDB Lab.
Bird’s-Eye View

Ch.5 ~ Ch.7: Linear List
Ch. 5 – array representation
 Ch. 6 – linked representation
 Ch. 7 – simulated pointer representation
※ In succeeding chapters - matrices, stacks, queues, dictionaries,
priority queues


Java’s linear list classes




java.util.ArrayList
Java.util.Vector
java.util.LinkedList
In an array representation of linear list

Elements are stored in an array
Data Structures
2
SNU
IDB Lab.
Table of Contents






Data Objects and Structures
The Linear List Data Structure
Array Representation
Vector Representation
Multiple Lists in a Single Array
Performance
Data Structures
3
SNU
IDB Lab.
Data Objects

Data Object: A set of instances of values




Boolean
= {false, true}
Integer
= {0, +1, -1, +2, -2, +3, -3, …}
daysOfWeek = {S, M, T, W, Th, F, Sa}
Individual instances of a data object

Primitive (atomic)


3, 5, a, Z,
Composed of instances of another data object


Element: the individual components of an instance of an object
good: an instance of String class
Data Structures

g, o, o, d is four elements of good

each element is an instance of the data object Letter
4
SNU
IDB Lab.
Data Structures

Definition: Data structure



Relationships among instances of integer





369 < 370
280 + 4 = 284
Relationships among elements that comprise an instance 369


Data object +
Relationships that exist among instances and elements
3 is more significant than 6
9 is immediately to the right of 6
The relationships are usually specified by specifying operations on instances

add, subtract, predecessor, multiply
Our primary concern:

the representation of data objects

the implementation of the operations of interest for the data objects
Data Structures
5
SNU
IDB Lab.
Table of Contents






Data Objects and Structures
The Linear List Data Structure
Array Representation
Vector Representation
Multiple Lists in a Single Array
Performance
Data Structures
6
SNU
IDB Lab.
Linear List (Ordered List)


An ordered collection of elements
Instances are of the form




(e0, e1, e2, …, en-1)
Where ei denotes a list element
i : The index of ei
n : The list length or size, n (>= 0) is finite

L = (e0, e1, e2, e3, …, en-1)

Relationships



e0 is the zero’th (or front) element
en-1 is the last element
ei immediately precedes ei+1
Data Structures
7
SNU
IDB Lab.
Linear List Examples
Students in COP3530 = (Jack, Jill, Abe, Henry, Mary, …, Judy)
Exams in COP3530 = (exam1, exam2, exam3)
Grades in COP3530 = (“Jack A+”, “Jill B-”, “Abe D”, … “Judy F”)
Days of Week = (S, M, T, W, Th, F, Sa)
Months = (Jan, Feb, Mar, Apr, …, Nov, Dec)
Data Structures
8
SNU
IDB Lab.
LinearList operations
Suppose L = (a, b, c, d, e, f, g)

size() : Determine list size


get(index) : Get element with given index


get(0) = a
indexOf(d) = 2
get(4) = e
get(-1) = error
get(9) = error
indexOf(a) = 0
indexOf(z) = -1
remove(index) : Remove and return element with given index.



get(2) = c
indexOf(element) : Determine the index of an element


L.size() = 7
remove(2) returns c, L becomes (a,b,d,e,f,g), indices of d,e,f and g are decreased by 1
remove(-1)  error
remove(20)  error
add(index, element) : Add an element so that the new element has a specified index.
add(0,h)  L = (h,a,b,c,d,e,f,g) // indices of a,b,c,d,e,f, and g are increased by 1
add(2,h)  L = (a,b,h,c,d,e,f,g) // indices of c,d,e,f, and g are increased by 1
add(10,h)  error
add(-6,h)  error

Data Structures
9
SNU
IDB Lab.
Data Structure Specification

Abstract Data Type (ADT)

Specification of







The instances
The operations to be performed
Language independent
All representation of the ADT must satisfy the specification
A way to validate the representation
Hiding the details of implementation
Two ways of ADT specification in Java


Interface
Abstract class
Data Structures
10
SNU
IDB Lab.
Abstract Data Type LinearList
AbstractDataType LinearList {
instances
ordered finite collections of zero or more elements
operations
isEmpty(): return true iff the list is empty, false otherwise
size():
return the list size (i.e., number of elements in the list)
get(index): return the indexth element of the list
indexOf(x):return the index of the first occurrence of x in the list,
return -1 if x is not in the list
remove(index): remove and return the indexth element,
elements with higher index have their index reduced by 1
add(theIndex, x): insert x as the indexth element, elements
with theIndex >= index have their index increased by 1
output(): output the list elements from left to right
}
SNU
Data Structures
11
IDB Lab.
Interface in Java

A named collection of method definitions


A class implements an interface


Does not provide any implementation (no nonabstract methods)
A class that implements the interface agrees to implement all of the
methods defined in the interface
Useful for



Capturing similarities between unrelated classes
Declaring methods that one or more classes are expected to implement
Revealing an object's programming interface without revealing its class
Data Structures
12
SNU
IDB Lab.
Abstract class in Java

Two types of classes in java



Abstract and Nonabstract
Default type is Nonabstract
Abstract class

Contains zero or more abstract methods




Abstract method: implementation is not provided
Can also contain nonabstract methods
You cannot create an instance of an abstract class
A class extends an abstract class (as usual classes)
Data Structures
13
SNU
IDB Lab.
Abstract class vs. Interface

Abstract class or interface ?




An abstract class can define nonconstant data members and nonabstract methods
If only constants and abstract methods are needed  interface will do
A class can implement many interfaces but can extend at most one class
 Only single inheritance among classes
 Multiple inheritance is simulated using interfaces
Data Structures in this Text



Use interfaces to specify ADTs throughout this lecture
Exception is Graph in Chapter 17 (The abstract class Graph)
Java specifies all of its data structures as interfaces

Ex) java.util.Map, java.util.Set
Data Structures
14
SNU
IDB Lab.
The Java Interface: LinearList
public interface LinearList
{ public boolean isEmpty();
public int
size();
public Object get(int index);
public int
indexOf(Object elem);
public Object remove(int index);
public void
add(int index, Object obj);
public String toString();
}
public class ArrayLinearList implements LinearList
{
// code for all LinearList methods must be provided here by the user
}
Data Structures
15
SNU
IDB Lab.
The Java Abstract Class:
LinearListAsAbstractClass
public abstract class LinearListAsAbstractClass
{ public abstract boolean isEmpty();
public abstract int size();
public abstract Object get(int index);
public abstract int indexOf(Object theElement);
public abstract Object remove(int index);
public abstract void add(int index, Object theElement);
public abstract String toString();
}
public class ArrayLinearList extends LinearListAsAbstractClass
{
// code for all abstract classes of LinearListAsAbstractClass must come here
}

ArrayLinearList inherits “implemented nonabstract methods”
Data Structures
16
SNU
IDB Lab.
Table of Contents





Data Objects and Structures
The Linear List Data Structure
Array Representation
Vector Representation
Multiple Lists in a Single Array
Data Structures
17
SNU
IDB Lab.
The Array Representation
public class ArrayLinearList implements LinearList {
protected Object[] element; // no array size declaration in Java
protected int size;
// no of elements in array
// …
element = new Object[initialCapacity]; // initialization
}




Use a one-dimensional array element[]
a
b
c
0
1
2
d
e
3 4
5 6
L = (a, b, c, d, e)
Store element i of linear list into element[i]
location(i) = i
Data Structures
18
SNU
IDB Lab.
Various mapping strategies
Right to Left mapping  location (i) = last - i

e
d
c
b
a
Mapping that skips every other position

a
b
c
d
e
Wrap around mapping  location (i) = (7 + i) % 15

d
e
a
b
c
Put element i of list in element[i]

a
b
c
d
e
size = 5

Use a variable size to record current number of elements
Data Structures
19
SNU
IDB Lab.
Add/Remove An Element
size = 5
a b

c
d
e
Add
add(1,g)
a

g
b
size = 6
c
d
e
Remove
remove(3)
a
Data Structures
g
c
size = 5
d
e
20
SNU
IDB Lab.
Declaring Array in Java

Primitive Data Types (declaration and initialization)



int[] anArray;
anArray = new int[10];
int anArray[];
anArray = new int[10];

int[] anArray= new int[10];

int anArray[] = new int[10];
Non-Primitive Data Types (declaration only)


Auto[] KoreanCar;
KoreanCar = new Auto[10];
Auto KoreanCar[];
KoreanCar = new Auto[10];

Auto[] KoreanCar = new Auto[10];

Auto KoreanCar[] = new Auto[10];
** initialization needs a for loop
Data Structures
21
SNU
IDB Lab.
“element” array of type “Object”

Syntax: Object[] element or Object element[]

element[] hold references to elements of any user-defined data type


Cannot put elements of primitive data types (int, float, double, char)


Data type of element is unknown
Instead, Use corresponding Class – Integer, Float, Double, Character, etc.
Array Length



Don’t know how many elements will be in list
Must pick an initial length
Dynamically increase the length as needed by the user
Data Structures
22
SNU
IDB Lab.
Increasing Array Length



Define an array of the new length
Copy the n elements from old array to the new array  θ(n)
Change the references to the new array
// create a new array of proper length and data type
Object[] newArray = new Object[newLength];
// copy all elements from old array “element” into new one “newArray”
System.arrayCopy(element, 0, newArray, 0, element.length);
// change the reference
element = newArray;
Data Structures
23
SNU
IDB Lab.
Space Complexity (1)

Increase the array size 1 by 1

element = new char [6]


b
c
d
e
f
newArray = new char[7];


a
MaxListSize=6
newLength=7
Space needed during array copying

Data Structures
2 * newLength – 1 = 2 * maxListSize + 1
24
SNU
IDB Lab.
Space complexity (2)
The array length is normally doubled wherever the array becomes full.

element maxListSize = 6
a
b
c
d
e
f
newArray = new char[12];
a

b
c
d
e
newLength = 12
f
maxListSize increased by *2  newLength

Space needed = 1.5 * newLength = 3 * maxListSize
Data Structures
25
SNU
IDB Lab.
How Big Should The New Array Be? (1)
By doubling the array, the complexity (num of copy) is θ(n)

T(n) = 1 + 2 + 4 + 8 + … + 2k = θ(2k+1 – 1) = θ(2n – 3) = θ(n)
Process
■ → ■□
■■ → ■■□□
■■■□
■■■■ → ■■■■□□□□
■■■■■□□□
■■■■■■□□
■■■■■■■□
■■■■■■■■ →■■■■■■■■□□□□□□□□
…
2k → 2k+1
Data Structures
26
# of adds
1
2
3
4
5
6
7
8
…
n-1 (= 2k)
n (= 2k+1)
Cost
1
2
0
4
0
0
0
8
…
2k
0
SNU
IDB Lab.
How Big Should The New Array Be? (2)

By increasing the length by 1, the complexity of becoming
an array with size n is θ(n2)
Process
■ → ■□
■■ → ■■□
...
n–1→n
Cost (No of Copy)
1
2
...
n–1

After n-1 adds, the array size is now n

T(n) = 1 + 2 + 3 + … + (n – 1) = θ((n2 – n) / 2) = θ(n2)
Data Structures
27
SNU
IDB Lab.
Insert theElement with array doubling
Public void add(int index, Object theElement) {
if (index < 0 || index > size) //invalid index
throw new IndexOoutOfBoundsException (…);
if (size == element.length) { // no space  double capacity
Object[] newArray = new Object[2*size];
System.arraycopy(element, 0, newArray, 0, size);
element = newArray;
}
for (int i = size-1; i >=index; i--)
element[i+1] = element[i]; // move up the remaining elements
element[index] = theElement;
Size++;
}
Data Structures
28
SNU
IDB Lab.
Java’s Linear List Classes
Vector
java
util

size():int
elementAt(index:int):Object
addElement(o:Object):void
removeElement(o:Object):boolean
ArrayList


연산속도는 ArrayList가
조금 빠름
Vector는 size에 신경쓸
필요가 없음
내부구현:

size():int
get(index:int):Object
add(o:Object):boolean
remove(o:Object):boolean


Vector
 vector
ArrayList  array
LinkedList  reference
LinkedList
size():int
get(index:int):Object
add(o:Object):boolean
remove(o:Object):boolean
Data Structures
29
SNU
IDB Lab.
The Class ArrayLinearList (ALL)
: program 5.4 — 5.8
public class ArrayLinearList implements LinearList{
protected Object[] element;
protected int size;
...
public boolean isEmpty()
{ return (size == 0); }
public int size()
{ return size; }
public Object get(int index)
{ return element[index]; }
public int indexOf(Object theElement) { …..}
public Object remove(int index) {
Object removedElement = element[index];
for (int i = index + 1; i < size; i++) element[i-1] = element[i];
element[--size] = null;
return removedElement; }
public void add(int index, Object theElement) { …….}
}
* FastArrayLinearList (FALL) : System.arraycopy() instead of for loop in
remove() and add()
Data Structures
30
SNU
IDB Lab.
Implementing ArrayLinearList (1)

Constructor



With initial capacity
With default capacity (say, 10 elements)
Removing an Element


Ascertain that the list contains an indexed element (if not, exception)
Shift index+1,…, size-1 elements down (left) one position


Complexity = O(size – index)
Reduce the value of size by 1
Data Structures
31
SNU
IDB Lab.
Implementing ArrayLinearList (2)

Inserting an Element

Move index ~ size-1 elements one position up (right)




Insert the new element in position index
Increment size by 1
Decreasing the Length of element



Complexity = O(size – index + 1)
To enable the linear list to free some of the array space when
the list size becomes small
slight modification of the method remove
Iterator

Navigate elements of linear list
Data Structures
32
SNU
IDB Lab.
Iterator: Basic Concepts


Specifies a unified mechanism to examine the elements in an object
one at a time
Related methods are in the interface java.util.Iterator
※With iterator methods we can easily examine ArrayLinearList’s all
elements

Iterator ix = x.iterator();



Constructs and initializes an iterator to examine the elements of x
constructed iterator is assigned to ix
You must define & implement the method iterator() in the class for x
Data Structures
33
SNU
IDB Lab.
Iterator: Methods

2 Main Methods

ix.hasNext()


ix.next()



Returns true iff x has a next element
Throws NoSuchElementException if there is no next element
Returns next element otherwise
Optional Method

ix.remove()



Removes last element returned by ix.next()
Throws UnsupportedMethodException if method not implemented
Throws IllegalStateException if ix.next() not yet called or did not
return an element
Data Structures
34
SNU
IDB Lab.
Example using an Iterator

By iterator (more general)
Iterator ix = x.iterator();
while (ix.hasNext())
examine(ix.next());
vs

By index (only for indexed data structure)
for (int i=0; i<x.size(); i++)
examine(get(i));
Data Structures
35
SNU
IDB Lab.
An Iterator for ArrayLinearList (1/3)

By using a top-level class


Implemented as a separate class from “Iterator” interface
Iterator class must access ArrayLinearList class data member
class ArrayLinearListIterator implements Iterator {
private ArrayLinearList list;
private int nextIndex;
public ArrayLinearListIterator(ArrayLinearList theList) {
list = theList;
nextIndex = 0;
}
public boolean hasNext()
{ return nextIndex < list.size; } // access list’s data member directly
// …
}
Data Structures
36
SNU
IDB Lab.
An Iterator for ArrayLinearList (2/3)

By using a member class



Implemented as a member class (nested class) of list class
Can access private data members of enclosing class
Can define the iterator in the same file
public class ArrayLinearListWithIterator implements LinearList {
public Iterator iterator()
{return new ArrayLinearListIterator();}
private class ArrayLinearListIterator implements Iterator {
public boolean hasNext()
{ return nextIndex < size; }
// …
}
// … all ArrayLinearList members and operations
}
Data Structures
37
SNU
IDB Lab.
An Iterator for ArrayLinearList (3/3)

Using a member class is better than using a top-level class
because list and iterator implementation can be separated
ArrayLinearListWithIterator
isEmpty():boolean
size():int
get(index:int):Object
remove(index:int):Object
iterator():Iterator
...
Data Structures
ArrayLinearListIterator
hasNext():boolean
next():Object
remove():void
uses
38
SNU
IDB Lab.
Merits of an Iterator

It is often possible to implement the method next() so that its complexity
is less than that of get()





Public Object get(int Index)
{ checkIndex(index); return element[Index]}
Public Object next()
{ if (nextIndex < list.size) return list.element[nextIndex++];
else throw new NoSuchElementException(“No next element”)}
TP page 45
Iterators provide a uniform way to sequence through the elements of a
data structure regardless of the data structure
Iterators provide left-to-right access vs Get() gives bidirection
Data Structures
39
SNU
IDB Lab.
Table of Contents






Data Objects and Structures
The Linear List Data Structure
Array Representation
Vector Representation
Multiple Lists in a Single Array
Performance
Data Structures
40
SNU
IDB Lab.
java.util.Vector




One of most widely used data structure class in java
Can think as array with variable length!
Have many operations similar to that of LinearList
Operations








boolean
boolean
Object
boolean
int
boolean
int
void
Data Structures
add(Object o)
add(int index, Object o)
remove(int index)
remove(Object o)
size()
isEmpty()
indexOf(Object o)
removeAllElements()
41
SNU
IDB Lab.
Remember “LinearList” interface
public interface LinearList
{ public void
add(int index, Object obj);
public Object
remove(int index);
public boolean isEmpty();
public int
size();
public Object
get(int index);
public int
indexOf(Object elem);
public String
toString();
}
Data Structures
42
SNU
IDB Lab.
Array vs. Vector in Java

Object[] oa = new Object[3]; //using array





oa[0]
oa[1]
oa[2]
oa[3]
=
=
=
=
“A”;
“B”;
“C”;
“D”; // size increasing must be done manually
Vector v = new Vector(3); //using vector




v.add(“A”)
v.add(“B”)
v.add(“C”)
v.add(“D”) // size is increased automatically (new size is now 6)
Data Structures
43
SNU
IDB Lab.
Linear List using Vector
LLAVS
Public class LinearListAsVectorSubclass extends Vector
implements LinearList
{ // Program 5.13}

LLAV
Public class LinearListAsVector
{// Program 5.14: element = new Vector(initialSize)}

Data Structures
44
SNU
IDB Lab.
Table of Contents






Data Objects and Structures
The Linear List Data Structure
Array Representation
Vector Representation
Multiple Lists in a Single Array
Performance
Data Structures
45
SNU
IDB Lab.
Multiple Lists in a Single Array
1 2 3
front[1]

last[1]
…
…
front[2]
last[2]
7 8 9
front[3]
last[3]
Map all of lists into a single array element whose length
is the maximum possible


4
May need shift left or right sub-array when inserting an element
in list I
Utilize the allocated array space
Data Structures
46
SNU
IDB Lab.
Table of Contents






Data Objects and Structures
The Linear List Data Structure
Array Representation
Vector Representation
Multiple Lists in a Single Array
Performance
Data Structures
47
SNU
IDB Lab.
Performance Measurement

Implement and measure the 4 classes in the textbook




ALL in page 162-173
FALL in page 167
LLAV in page 179-180
LLAVS in page 177
operation
get
insert
remove
LinearListAsVector
best- average worst- best- average worstcase
case
case
case
5.6ms 26.2ms
70s
140s
6.9ms
71s
142s
5.6ms 31.2ms 5.8s
11.8s 8.6ms
5.7s
11.7s
20.8ms 51.2ms 5.8s
11.8s 18.4ms
5.8s
11.8s
LinearListAsVectorS
ubclass
18.6ms 48.2ms
class
ArrayLinearList
FastArrayLinearList
5.8s
11.8s
22.4ms
5.8s
(List is constructed with the default initial capacity of 10)
Data Structures
48
11.8s
SNU
IDB Lab.
Summary

Ch.5 ~ Ch.7: Linear List

Ch. 5 – array representation



ADT LinearList, Java’s Interface & Abstract Class
Array representation: Increasing array size, Iterator
Vector representation
Ch. 6 – linked representation
 Ch. 7 – simulated pointer representation
※ In succeeding chapters - matrices, stacks, queues, dictionaries,
priority queues


Java’s linear list classes

java.util.ArrayList, java.util.Vector, java.util.LinkedList
Data Structures
49
SNU
IDB Lab.
JDK class: java.util.ArrayList
public class ArrayList extends AbstractList {
constructors
ArrayList(): Constructs an empty list with initial size 10
ArrayList(int cap): Constructs an empty list with initial size cap
methods
boolean add(Object obj): Adds obj to the end of the list;
Always returns true
Object get(int i): Returns i-th element of the list
boolean isEmpty(): Returns true iff the list is empty, false otherwise
boolean remove(Object obj): Removes obj from the list ;
Returns true iff obj was in the list
}
Data Structures
50
SNU
IDB Lab.
JDK class: java.util.vector
public class Vector extends AbstractList {
constructors
Vector():
Constructs an empty vector with initial size 10
Vector(int cap): Constructs an empty vector with initial size cap
methods
void addElement(Object obj): Adds obj to the end of the vector
Object elementAt(int i):
Returns i-th element of the vector
boolean isEmpty(): Returns true iff the vector is empty, false otherwise
boolean remove(Object obj): Removes obj from the vector;
Returns true iff obj was in the vector
}
Data Structures
51
SNU
IDB Lab.