Linear List

Teknik InformatikaUniversitas Muhammadiyah Malang

SP - 2013

Algoritma & Struktur Data

Representasi Linear List dengan Array dan

Linked list

Tujuan Instruksional

• Mahasiswa mampu :• Memahami struktur data dari linear list• Mampu merepresentasikan linear list menggunakan array dan linked list• Mengimplementasikan linear list ke dalam program

Struktur Data

• Struktur data terdiri dari obyek data dan operasi-operasi.• Obyek data adalah sekumpulan instance (model/sampling)• Contoh obyek data :

integer = {0, +1, -1, +2, -2, +3, -3, …}

daysOfWeek = {S,M,T,W,Th,F,Sa}

myDataObject = {apple, chair, 2, 5.2, red, green, Jack}

Struktur Data

• Struktur data dibedakan menjadi 2 jenis :1. Linear list

direpresentasikan dengan : array dan linked list2. Struktur data hirarki

Direpresentasikan dengan : tree dan graph

Linear Lists

• Disebut juga dengan ordered list.• Bentuk instance dari linear list :

(e0, e1, e2, …, en-1)

where ei denotes a list elementn >= 0 is finite (list size is n)

Linear Lists

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

Linear List Examples/Instances

Students in COP3530 =(Jack, Jill, Abe, Henry, Mary, …, Judy)

Exams in COP3530 =(exam1, exam2, exam3)

Days of Week = (S, M, T, W, Th, F, Sa)

Months = (Jan, Feb, Mar, Apr, …, Nov, Dec)

Struktur data Operations

• Operasi : aksi yang dapat dilakukan pada obyek data.• Operasi-operasi yang umum pada obyek data : penambahan elemen,

penghapusan elemen, pengaksesan elemen, dll.

Linear List Operations—size()

determine list size

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

size = 5

Linear List Operations—get(theIndex)

get element with given index

L = (a,b,c,d,e)get(0) = aget(2) = cget(4) = eget(-1) = errorget(9) = error

Linear List Operations—indexOf(theElement)

determine the index of an element

L = (a,b,d,b,a)indexOf(d) = 2indexOf(a) = 0indexOf(z) = -1

Linear List Operations—remove(theIndex)

remove and return element with given index

L = (a,b,c,d,e,f,g)remove(2) returns cand L becomes (a,b,d,e,f,g)

index of d,e,f, and g decrease by 1

Linear List Operations—remove(theIndex)

remove and return element with given index

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

remove(-1) => error

remove(20) => error

Linear List Operations—add(theIndex, theElement)

add an element so that the new element has a specified index

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

add(0,h) => L = (h,a,b,c,d,e,f,g)index of a,b,c,d,e,f, and g increase by 1

Linear List Operations—add(theIndex, theElement)

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

add(2,h) => L = (a,b,h,c,d,e,f,g)index of c,d,e,f, and g increase by 1

add(10,h) => error

add(-6,h) => error

Latihan

Diketahui L=(a,b,c,d). L adalah sebuah array linier list. Tentukan hasil yang didapatkan ketika dilakukan perintah berikut ini :

a) isEmpty()b) size()c) get(0), get(2),get(6),get(-3)d) indexOf(a), indexOf(c), indexOf(q)e) remove(0), remove(2), remove(3)f) add(0,e), add(2,f), add(3,g), add(4,h), add(6,h), add(-3,h)

Data Structure Specification

Language independentAbstract Data Type

JavaInterfaceAbstract Class

Linear List Abstract Data Type

AbstractDataType LinearList

{

instances

ordered finite collections of zero or more elements

operations

isEmpty(): return true if 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

indexO f(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

}

Linear List as Java Interface

An interface may include constants and abstract methods (i.e., methods for which no implementation is provided).

Linear List as Java Interface

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

Implementing An Interface

public class ArrayLinearList implements LinearList{ // code for all LinearList methods must be provided here }

Linear List As An Abstract Class

An abstract class may include constants, variables, abstract methods, and nonabstract methods.

Linear List As Java Abstract Class

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

Extending A Java Class

public class ArrayLinearList extends LinearListAsAbstractClass{ // code for all abstract classes must come here}

0 1 2 3 4 5 6

Linear List Array Representation

use a one-dimensional array element[]

a b c d e

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

Store element i of list in element[i].

Representation Used In Text

put element i of list in element[i]

use a variable size to record current number of elements

0 1 2 3 4 5 6

a b c d e

size = 5

Add/Remove An Element

a b c d e

size = 5

a g b c d e

size = 6

add(1,g)

Data Type Of Array element[]

Data type of list elements is unknown.

Define element[] to be of data type Object.

Cannot put elements of primitive data types (int, float, double, char, etc.) into our linear lists.

Increasing Array Length

Length of array element[] is 6.

a b c d e f

newArray = new Object[15];

First create a new and larger array

Increasing Array Length

Now copy elements from old array to new one.

a b c d e f

a b c d e f

Increasing Array Length

Finally, rename new array.element = newArray;

element.length = 15

a b c d e f

element[0]

Class ArrayLinearList

• Merupakan hasil implements dari interface LinearList.

Create An Empty List

ArrayLinearList a = new ArrayLinearList(100), b = new ArrayLinearList(), c;LinearList d = new ArrayLinearList(1000), e = new ArrayLinearList(), f;

Using A Linear ListSystem.out.println(a.size());a.add(0, new Integer(2));b.add(0, new Integer(4));System.out.println(a);b.remove(0);if (a.isEmpty())

a.add(0, new Integer(5));

Array Of Linear Lists

LinearList [] x = new LinearList [4];x[0] = new ArrayLinearList(20);x[1] = new Chain();x[2] = new Chain();x[3] = new ArrayLinearList();for (int i = 0; i < 4; i++) x[i].add(0, new Integer(i));

The Class ArrayLinearList

/** array implementation of LinearList */

package dataStructures;

import java.util.*; // has Iterator interface

import utilities.*; // has array resizing class

public class ArrayLinearList implements LinearList

{

// data members

protected Object [] element; // array of elements

protected int size; // number of elements in array

// constructors and other methods come here

}

A Constructor

/** create a list with initial capacity initialCapacity * @throws IllegalArgumentException when * initialCapacity < 1 */ public ArrayLinearList(int initialCapacity) { if (initialCapacity < 1) throw new IllegalArgumentException ("initialCapacity must be >= 1"); // size has the default initial value of 0 element = new Object [initialCapacity]; }

Another Constructor

/** create a list with initial capacity 10 */ public ArrayLinearList() {// use default capacity of 10 this(10); }

The Method isEmpty

/** @return true iff list is empty */ public boolean isEmpty() {return size == 0;}

The Method size()

/** @return current number of elements in list */ public int size() {return size;}

The Method checkIndex

/** @throws IndexOutOfBoundsException when * index is not between 0 and size - 1 */ void checkIndex(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException ("index = " + index + " size = " + size); }

The Method get

/** @return element with specified index * @throws IndexOutOfBoundsException when * index is not between 0 and size - 1 */ public Object get(int index) { checkIndex(index); return element[index]; }

The Method indexOf /** @return index of first occurrence of theElement, * return -1 if theElement not in list */ public int indexOf(Object theElement) { // search element[] for theElement for (int i = 0; i < size; i++) if (element[i].equals(theElement)) return i; // theElement not found return -1; }

The Method remove public Object remove(int index) { checkIndex(index); // valid index, shift elements with higher index Object removedElement = element[index]; for (int i = index + 1; i < size; i++) element[i-1] = element[i]; element[--size] = null; // enable garbage collection return removedElement; }

The Method add public void add(int index, Object theElement) { if (index < 0 || index > size) // invalid list position throw new IndexOutOfBoundsException ("index = " + index + " size = " + size); // valid index, make sure we have space if (size == element.length) // no space, double capacity element = ChangeArrayLength.changeLength1D(element, 2 * size);

The Method add

// shift elements right one position for (int i = size - 1; i >= index; i--) element[i + 1] = element[i]; element[index] = theElement; size++; }

Faster Way To Shift Elements 1 Right

System.arraycopy(element, index, element, index + 1, size - index);

Convert To A String public String toString() { StringBuffer s = new StringBuffer("["); // put elements into the buffer for (int i = 0; i < size; i++) if (element[i] == null) s.append("null, "); else s.append(element[i].toString() + ", "); if (size > 0) s.delete(s.length() - 2, s.length()); // remove last ", " s.append("]"); // create equivalent String return new String(s); }

Linear list Linked-Lists Representation

Definisi

• Linked list : linear list yang dibangun dari satu atau lebih node.• Node terdiri dari dua bagian : data field dan pointer.• Data field: bagian dari list node untuk menyimpan data.• Pointer : bagian dari list node untuk menunjuk node berikutnya.

Node

Link atau pointer

data field

Single linked list

• Yaitu Linked list yang memiliki satu pointer.• Pointer bantu : firstnode

Linked Representation

pointer (or link) in e is null

c a e d b

use a variable firstNode to get to the first element a

firstNode

Normal Way To Draw A Linked List

link or pointer field of node

data field of node

a b c d e

null

firstNode

Linked Lists vs Array

• Menyimpan koleksi elemen secara non-contiguously.• Elemen dapat terletak pada lokasi memory yang saling

berjauhan. Bandingkan dengan array dimana tiap-tiap elemen akan terletak pada lokasi memory yang berurutan.

• Mengizinkan operasi penambahan atau penghapusan elemen ditengah-tengah koleksi dengan hanya membutuhkan jumlah perpindahan elemen yang konstan. • Bandingkan dengan array. Berapa banyak elemen yang

harus dipindahkan bila akan menyisipi elemen ditengah-tengah array?

A0 A1 A2 A3

Chain

•A chain is a linked list in which each node represents one element.• There is a link or pointer from one element to the next.• The last node has a null pointer.

a b c d e

null

firstNode

Latihan

Diketahui L=(a,b,c,d). L adalah sebuah linked lists.. Tentukan hasil yang didapatkan ketika dilakukan operasi berikut ini :

a) isEmpty()b) size()c) get(0), get(2),get(6),get(-3)d) indexOf(a), indexOf(c), indexOf(q)e) remove(0), remove(2), remove(3)f) add(0,e), add(2,f), add(3,g), add(4,h), add(6,h), add(-3,h)(Gambarkan rangkaian node pembentuk linked list tersebut kondisi awal dan akhir tiap operasi)

Node Representation

package dataStructures;

class ChainNode{ // package visible data members Object element; ChainNode next;

// constructors come here}

next

element

Constructors Of ChainNode

ChainNode() {}null

null

null

element

next

element

ChainNode(Object element)

{this.element = element;}

ChainNode(Object element, ChainNode next)

{this.element = element;

this.next = next;}

get(0)

checkIndex(0);desiredNode = firstNode; // gets you to first nodereturn desiredNode.element;

a b c d e

null

firstNode

get(1)

checkIndex(1);desiredNode = firstNode.next; // gets you to second nodereturn desiredNode.element;

a b c d e

null

firstNode

get(2)

checkIndex(2);desiredNode = firstNode.next.next; // gets you to third node

return desiredNode.element;

a b c d e

null

firstNode

get(5)

checkIndex(5); // throws exceptiondesiredNode = firstNode.next.next.next.next.next; // desiredNode = nullreturn desiredNode.element; // null.element

a b c d e

null

firstNode

NullPointerException

desiredNode = firstNode.next.next.next.next.next.next;

// gets the computer mad // you get a NullPointerException

a b c d e

null

firstNode

Remove An Element

remove(0)

a b c d e

null

firstNode

firstNode = firstNode.next;

a b d e

null

firstNode

c

remove(2)

first get to node just before node to be removed

cc

beforeNode = firstNode.next;

b

beforeNode

remove(2)

now change pointer in beforeNode

beforeNode.next = beforeNode.next.next;

beforeNode

a b c d e

null

firstNode

add(0,’f’)

a b c d e

null

firstNode

f

newNode

Step 1: get a node, set its data and link fields

ChainNode newNode =

new ChainNode(new Character(‘f’), firstNode);

add(0,’f’)

a b c d e

null

firstNode

f

newNode

Step 2: update firstNode

firstNode = newNode;

One-Step add(0,’f’)

a b c d e

null

firstNode

f

newNode

firstNode = new ChainNode( new Character(‘f’), firstNode);

add(3,’f’)

• first find node whose index is 2

a b c d e

null

firstNode

fnewNode

beforeNode

c

• next create a node and set its data and link fields

ChainNode newNode = new ChainNode(new Character(‘f’),

beforeNode.next);

• finally link beforeNode to newNodebeforeNode.next = newNode;

Two-Step add(3,’f’)

beforeNode = firstNode.next.next;

beforeNode.next = new ChainNode(new Character(‘f’),

beforeNode.next);

a b c d e

null

firstNode

fnewNode

beforeNode

c