Linear List
description
Transcript of 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
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 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
Penambahan di Awal(2)
last
Penambahan di Awal(3)
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
Penambahan Setelah Node x
2. Baru.prev = after
last
95
Penambahan Setelah Node x
3. Baru.next = after.next
last
96
Penambahan Setelah Node x
4. after.next.prev = Baru
last
97
Penambahan Setelah Node x
5. after.next = Baru
last
98
Penambahan Setelah Node x
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
Penambahan Sebelum Node x
3. Baru.next = before
last
103
Penambahan Sebelum Node x
4. before.prev.next = Baru
last
104
Penambahan Sebelum Node x
5. before.prev = Baru
last
105
Penambahan Sebelum Node x
Hasil akhir :
last
Penghapusan Node
107
Operasi Hapus Node (Delete)
• Hapus awal (Delete First)• Hapus akhir (Delete Last)• Hapus Node x
108
Asumsi Awal
Asumsi linked list 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
Asumsi linked list awal :
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