DS Ch 5 (1 unit) Linear list by Array

(1)

Ch5. Linear Lists –

Array Representation

(2)

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

(3)

Table of Contents

Data Objects and Structures

The Linear List Data Structure

Vector Representation

Multiple Lists in a Single Array

Performance

(4)

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

g, o, o, d is four elements of good

(5)

Data Structures

Definition: Data structure

Data object +

Relationships that exist among instances and elements

Relationships among instances of integer

369 < 370

280 + 4 = 284

Relationships among elements that comprise an instance 369

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

(6)

Relationships

e₀ is the zero’th (or front) element

e_n-1 is the last element

e_i immediately precedes e_i+1

(8)

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)

(9)

LinearList operations

Suppose L = (a, b, c, d, e, f, g)

size() : Determine list size

L.size() = 7

get(index) : Get element with given index

get(0) = a get(2) = c get(4) = e get(-1) = error get(9) = error

indexOf(element) : Determine the index of an element

indexOf(d) = 2 indexOf(a) = 0 indexOf(z) = -1

remove(index) : Remove and return element with given index.

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

(10)

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

(11)

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

(12)

Interface in Java

A named collection of method definitions

Does not provide any implementation (no nonabstract methods)

A class implements an interface

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

(13)

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)

(14)

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

(15)

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 }

(16)

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”

(17)

Use a one-dimensional array element[]

L = (a, b, c, d, e)

Store element i of linear list into element[i]

0 1 2 3 4 5 6

a b c d e

(19)

Various mapping strategies

Right to Left mapping location (i) = last - i

a b

c d

e

Mapping that skips every other position

a b c d e

Wrap around mapping location (i) = (7 + i) % 15

a b c

d e

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

(20)

Add/Remove An Element

a b c d e

a g b c d e

add(1,g)

Add

a g c d e

remove(3)

Remove

size = 5 size = 6 size = 5

(21)

Declaring Array in Java

Primitive Data Types

int[] anArray;

anArray = new int[10];

int anArray[];

anArray = new int[10];

Non-Primitive Data Types

Auto[] KoreanCar;

KoreanCar = new Auto[10];

Auto KoreanCar[];

KoreanCar = new Auto[10];

int[] anArray= new int[10];

int anArray[] = new int[10];

Auto[] KoreanCar = new Auto[10];

Auto KoreanCar[] = new Auto[10];

(22)

“element” array of type “Object”

Syntax: Object[] element or Object element[]

element[] hold references to elements of any user-defined data type

Data type of element is unknown

Cannot put elements of primitive data types (int, float, double, char)

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

(23)

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;

(24)

Space Complexity (1)

Increase the array size 1 by 1

element = new char [6]

MaxListSize=6

newArray = new char[7];

newLength=7

Space needed during array copying

2 * newLength – 1 = 2 * maxListSize + 1

a b c d e f

(25)

Space complexity (2)

The array length is normally doubled wherever the array becomes full.

a b c d e f

newArray = new char[12]; newLength = 12

a b c d e f

maxListSize increased by *2 newLength

Space needed = 1.5 * newLength = 3 * maxListSize

element maxListSize = 6

(26)

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 + … + 2^k = θ(2^k+1 – 1) = θ(2n – 3) = θ(n)

… 8 7 6 5 4 3 2 1

# of adds

…

■■■■■■■■ →■■■■■■■■□□□□□□□□ 8

■■■■■■■□ 0

■■■■■■□□ 0

■■■■■□□□ 0

■■■■ → ■■■■□□□□ 4

■■■□ 0

■■ → ■■□□ 2

■ → ■□ 1

Cost Process

(27)

How Big Should The New Array Be? (2)

By increasing the length by 1, the complexity of becoming an array with size n is θ

(n²)

After n-1 adds, the array size is now n

T(n) = 1 + 2 + 3 + … + (n – 1) = θ((n² – n) / 2) = θ(n²) n – 1

n – 1 → n

...

■■ → ■■□ 2

■ → ■□ 1

Cost (No of Copy) Process

(28)

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++;

(29)

Java’s Linear List Classes

size():int

elementAt(index:int):Object addElement(o:Object):void

removeElement(o:Object):boolean Vector

util util java java

size():int

get(index:int):Object add(o:Object):boolean remove(o:Object):boolean

ArrayList

size():int

get(index:int):Object add(o:Object):boolean remove(o:Object):boolean

LinkedList

연산속도는 ArrayList 가 조금 빠름

Vector 는 size 에 신경쓸 필요가 없음

내부구현 :

Vector vector

ArrayList array

LinkedList reference

(30)

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) { …….}

}

(31)

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

(32)

Implementing ArrayLinearList (2)

Inserting an Element

Move index ~ size-1 elements one position up (right)

Complexity = O(size – index + 1)

Insert the new element in position index

Increment size by 1

Decreasing the Length of element

To enable the linear list to free some of the array space when the list size becomes small

slight modification of the method remove

(33)

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 With iterator methods we can easily examine With iterator methods we can easily examine With iterator methods we can easily examine ArrayLinearList’’’’ssss all all all all elements

elements elements 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

(34)

Iterator: Methods

2 Main Methods

ix.hasNext()

Returns true iff x has a next element

ix.next()

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

(35)

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));

(36)

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

(37)

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 }

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

(38)

Using a member class is better than using a top-level class because list and iterator implementation can be separated

isEmpty():boolean size():int

get(index:int):Object

remove(index:int):Object iterator():Iterator

...

ArrayLinearListWithIterator

hasNext():boolean next():Object

remove():void

ArrayLinearListIterator

uses

(39)

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

(40)

Have many operations similar to that of LinearList

Operations

boolean add(Object o)

boolean add(int index, Object o)

Object remove(int index)

boolean remove(Object o)

int size()

boolean isEmpty()

int indexOf(Object o)

void removeAllElements()

(42)

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();

}

(43)

Array vs. Vector in Java

Object[] oa = new Object[3]; //using array

oa[0] = “A”;

oa[1] = “B”;

oa[2] = “C”;

oa[3] = “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)

(44)

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)}

(45)

Utilize the allocated array space

1 2 3 4 … … 7 8 9

front[1] last[1] front[2] front[3] last[3]

last[2]

(47)

Table of Contents

Performance

(48)

Performance Measurement

11.8s 5.8s

18.4ms 11.8s

5.8s 51.2ms

20.8ms

LinearListAsVector

11.7s 5.7s

8.6ms 11.8s

5.8s 31.2ms

5.6ms

FastArrayLinearList

worst- average case

best- case worst-

average case best-

case

142s 71s

6.9ms 140s

70s 26.2ms

5.6ms

ArrayLinearList

remove insert

operation get class

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

(49)

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