linear list

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 list

2. Struktur data hirarkiDirepresentasikan 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)

relationshipse0 is the zero’th (or front) elementen-1 is the last elementei immediately precedes ei+1

Linear List Examples/InstancesStudents 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) => errorremove(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 TypeAbstractDataType 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 Classpublic 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


Now copy elements from old array to new one.

a b c d e f

a b c d e f


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 List

System.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 ListsLinearList [] 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 enull

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 enull

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 enull

firstNode

get(1)

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

second nodereturn desiredNode.element;

a b c d enull

firstNode

get(2)

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

to third node return desiredNode.element;

a b c d enull

firstNode

get(5)

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

a b c d enull

firstNode

NullPointerException

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

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

a b c d enull

firstNode

Remove An Element

remove(0)

a b c d enull

firstNode

firstNode = firstNode.next;

a b d enull

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 enull

firstNode

add(0,’f’)

a b c d enull

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 enull

firstNode

f

newNode

Step 2: update firstNode

firstNode = newNode;

One-Step add(0,’f’)

a b c d enull

firstNode

f

newNode

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

add(3,’f’)

• first find node whose index is 2

a b c d enull

firstNodef

newNode

beforeNode

c

• next create a node and set its data and link fieldsChainNode 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 enull

firstNodef

newNode

beforeNode

c

Double Linked List

Definisi

• Linked list dengan dua pointer(next & prev)• Pointer next : menghadap ke node yang lebih

besar indexnya.• Pointer prev : menghadap ke node yang lebih

kecil indexnya.

Head & Tail

• Head : menunjuk pada node pertama.• Tail : menunjuk pada node terakhir.

• Pada node pertama, pointer prev mengarah ke null.

• Pada node terakhir, pointer next mengarah ke null.

Gambaran

last

Data/item

prev

next

Double Representation

class Node{

Object dData; // data itemNode next; // pointer nextNode prev; // pointer prev…..

}

Operasi

• Penambahan/penyisipan• Penghapusan

Penambahan Node

Penambahan Node

• Penambahan di awal• Penambahan di akhir• Penambahan sebelum node tertentu• Penambahan setelah node tertentu

Asumsi awal

Penambahan di Awal

• Pointer bantu : baru• Langkah :

– Baru.next = head– head.prev = Baru– head = baru

84

Penambahan di Awal(1)

last

85


last


86

last

87

Penambahan di Akhir

Asumsi linked list awal :

last

88

Penambahan di Akhir

1. Baru.prev = last

last

89

Penambahan di Akhir

2. last.next = Baru

last

90

Penambahan di Akhir

3. last = Baru

last

Penambahan Setelah Node x

• Pointer bantu : after

92

Penambahan Setelah Node xAsumsi linked list awal :

last

93

Penambahan Setelah Node x1. Node after;

after diarahkan ke posisi node 10, bisa dimulai dari head maupun last

last

94


2. Baru.prev = after

last

95


3. Baru.next = after.next

last

96


4. after.next.prev = Baru

last

97


5. after.next = Baru

last

98


Hasil akhir :

last

99

Penambahan Sebelum Node xAsumsi linked list awal :

last

100

Penambahan Sebelum Node x1. Node before;

before diarahkan ke posisi node 5, bisa dimulai dari head maupun last

last

101

Penambahan Sebelum Node x

2. Baru.prev = before.prev

last

102


3. Baru.next = before

last

103


4. before.prev.next = Baru

last

104


5. before.prev = Baru

last

105


Hasil akhir :

last

Penghapusan Node

107

Operasi Hapus Node (Delete)

• Hapus awal (Delete First)• Hapus akhir (Delete Last)• Hapus Node x

108

Asumsi Awal


last

109

Delete First

1. Node hapus; hapus = head;

last

110

Delete First

2. head.next.prev = null

last

111

Delete First

3. head = hapus.next

last

112

Delete First

last

113

Delete First

Hasil akhir :

last

114

Delete Last


last

115

Delete Last

1. Node hapus; hapus = last;

last

116

Delete Last

2. last.prev.next = null

last

117

Delete Last

3. last = hapus.prev

last

118

Delete Last

last

119

Delete Last

Hasil akhir :

last

120

Delete Node x

Asumsi linked list awal : Misalkan x = 3

lastlast

121

Delete Node x1. Node hapus;

hapus diarahkan pada posisi node 3, bisa mulai dari head maupun last

last

122

Delete Node x

2. hapus.prev.next = hapus.next;

last

123

Delete Node x

3. hapus.next.prev = hapus.prev;

last

124

Delete Node x

last

Circular List

Definisi

• Circular List : list yang berbentuk cirrcular/melingkar, node depan terhubung dengan node paling belakang.

Linked List: Insertion

Menyisipkan X pada lokasi setelah current.

a b c d

current

a b

xcurrent

c d x

tmp = new ListNode (x, current.next);

current.next = tmp;

Langkah-langkah menyisipkan yang lebih efisien

a b

xcurrent

a b

xcurrent

Pertanyaan:• Selama ini contoh menyisipkan dan menghapus

elemen dengan asumsi ada node current yang terletak sebelumnya. – Bagaimana menambahkan node pada urutan

pertama pada linked list? – Bagaimana menghapus elemen pertama pada linked

list?

Latihan

• Buatlah sebuah method untuk menghitung jumlah elemen dalam sebuah linked list!

public static int listSize (LinkedList theList){

}

Doubly-linked lists: Tiap list node menyimpan referensi node sebelum dan sesudahnya. Berguna bila perlu melakukan pembacaan linkedlist dari dua arah.

Variasi Linked Lists

A

head tail

prev

next

Variasi Linked Lists

• Circular-linked lists: Node terakhir menyimpan referensi node pertama. Dapat diterapkan dengan atau tanpa header node.

A B C

first

prev

next

Doubly-linked lists: InsertNext

newNode = new DoublyLinkedListNode(x);

1 newNode.prev = current;2 newNode.prev.next = newNode;……

x

ba

1

2

?

current

Doubly-linked lists: insertNext

1 newNode = new DoublyLinkedListNode(x);

2 newNode.prev = current;3 newNode.next = current.next;4 newNode.prev.next = newNode;5 newNode.next.prev = newNode;6 current = newNode;

A B

current

X

prev

next

newNode

1

32 5

4

6

Doubly-linked lists: DeleteCurrent1.current.prev.next = current.next;

2.current.next.prev = current.prev;

3.current = current.prev;

x

ba

current

1

2

3

Rangkuman• ListNode• List, LinkedList dan variasinya• Iterator class• Kelebihan & kekurangan dari linked list

– Growable– Overhead a pointer, new operator untuk membuat

node.– Hanya bisa diakses secara sequential.

Gambaran

a b c d e

firstNode

Daftar Pustaka

• L.N. Harnaningrum, Struktur Data menggunakan Java, Graha ilmu, 2010

• Siswanto, Algoritma & Struktur Data Linier, Graha Ilmu, 2010

• Ruli Manurung, Ade Azurat, Struktur Data dan Algoritma, Fasilkom UI, 2008

linear list

Documents