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
Top Related