linear list

Download Linear List

Post on 06-Feb-2016

64 views

Category:

Documents

1 download

Embed Size (px)

DESCRIPTION

Algoritma & Struktur Data. Linear List. Teknik Informatika Universitas Muhammadiyah Malang SP - 201 3. Representasi Linear List dengan Array dan Linked list. Tujuan Instruksional. Mahasiswa mampu : Memahami struktur data dari linear list - PowerPoint PPT Presentation

TRANSCRIPT

PowerPoint Presentation

Linear List

Teknik InformatikaUniversitas Muhammadiyah MalangSP - 2013Algoritma & Struktur DataRepresentasi Linear List dengan Array dan Linked listTujuan InstruksionalMahasiswa mampu :Memahami struktur data dari linear listMampu merepresentasikan linear list menggunakan array dan linked listMengimplementasikan linear list ke dalam programStruktur DataStruktur 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 DataStruktur data dibedakan menjadi 2 jenis :Linear listdirepresentasikan dengan : array dan linked listStruktur data hirarkiDirepresentasikan dengan : tree dan graphLinear ListsDisebut 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 ListsL = (e0, e1, e2, e3, , en-1)

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

A data object is a set of instances; an instance of a linear list is an ordered set of elements.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)Size of Students in COP3530 is 240, Exams is 3, DOW is 7, and Months is 12. Notice that Days of Week is used as an example of both a data object and of a linearlist. As a data object, {S, M, T, } and {M, W, S, } describe the same data object with 7 allowable instances S, M, T, As a linear list (S, M, T, ) and (M, W, S, ) are two different instances of a linear list. Linear List itself may be viewed as data object, which is simply the set of all possible linear list instances.Struktur data OperationsOperasi : aksi yang dapat dilakukan pada obyek data.Operasi-operasi yang umum pada obyek data : penambahan elemen, penghapusan elemen, pengaksesan elemen, dll.Linear List Operationssize()determine list size

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

size = 5Linear List Operationsget(theIndex)get element with given index L = (a,b,c,d,e)get(0) = aget(2) = cget(4) = eget(-1) = errorget(9) = errorLinear List OperationsindexOf(theElement)determine the index of an element L = (a,b,d,b,a)indexOf(d) = 2indexOf(a) = 0indexOf(z) = -1The index of a nonexistent element is defined to be 1. When theElement is in the list an index between 0 and size()-1 is the result. So 1 would be an invalid index and is used to represent the case when theElement is not in the listLinear List Operationsremove(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 1Linear List Operationsremove(theIndex)remove and return element with given index

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

remove(-1) => errorremove(20) => errorLinear List Operationsadd(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 Operationsadd(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) => erroradd(-6,h) => errorLatihanDiketahui L=(a,b,c,d). L adalah sebuah array linier list. Tentukan hasil yang didapatkan ketika dilakukan perintah berikut ini :isEmpty()size()get(0), get(2),get(6),get(-3)indexOf(a), indexOf(c), indexOf(q)remove(0), remove(2), remove(3)add(0,e), add(2,f), add(3,g), add(4,h), add(6,h), add(-3,h)

Data Structure SpecificationLanguage independentAbstract Data TypeJavaInterfaceAbstract ClassLinear 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 InterfaceAn interface may include constants and abstract methods (i.e., methods for which no implementation is provided).

Linear List as Java Interfacepublic 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();}

Should add comments that describe the parameters, return value, and functionality of each method. Looks a lot like the abstract data type specification but the data types, return type specification, name of output method (toString) are all peculiar to Java.Implementing An Interfacepublic class ArrayLinearList implements LinearList{ // code for all LinearList methods must be provided here }Linear List As An Abstract ClassAn abstract class may include constants, variables, abstract methods, and nonabstract methods.So an abstract class is more general than an interface. In addition to having the permissible components of an interface (constants and abstract methods), we can have variables and nonabstract methods.Linear List As Java Abstract Classpublic 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();}In the case of a linear list, the main difference between the interface and abstract class specification is the use of the keyword interface vs the keywords abstract class. All methods of the abstract class have been declared as abstract to indicate that we are not providing their implementation here. In the case of an interface it isnt required (though permissible) to declare each method abstract. This is because all methods listed in an interface are, by default, abstract.Extending A Java Classpublic class ArrayLinearList extends LinearListAsAbstractClass{ // code for all abstract classes must come here}Since ArrayLinearList is not declared as an abstract class, it must provide an implementation for all abstract methods of the class it extends (I.e., of LinearListAsAbstractClass).0123456Linear List Array Representationuse a one-dimensional array element[]abcdeL = (a, b, c, d, e)Store element i of list in element[i].All array representations of a linear list use an array (say one-dimensional). Element.length = 15.Different array representations result when different mappings are used between list elements and array positions. The most intuitive and simple mapping is to map list element I into array position I.Representation Used In Textput element i of list in element[i]

use a variable size to record current number of elements0123456abcdesize = 5This is the representation used in the text.When this mapping is used, list operations such as isEmpty(), size(), get(index)Become easy to implement.Add/Remove An Elementabcdesize = 5agbcdesize = 6add(1,g)To add an element we must physically relocate elements that are to be to the right of the newly inserted element. We must also increment size by 1. The slide shows add(1,g). remove(1) is the reverse.To remove an element we must move elements to the right of the removed element left by 1 and reduce size by 1.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.To use this representation in Java, we must know/provide a data type and length of the array element[].Wrapper types Integer, Float, Double, etc provided in Java.Increasing Array LengthLength of array element[] is 6. abcdefnewArray = new Object[15];First create a new and larger arrayIncreasing Array LengthNow copy elements from old array to new one.abcdefabcdefIncreasing Array LengthFinally, rename new array.element = newArray;element.length = 15abcdefelement[0]Class ArrayLinearList Merupakan hasil implements dari interface LinearList.

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

For the second example, the class ArrayLinearList must implement the interface LinearList. c and f are actually set to null. So, they really are not referencing an empty linear list but the null list. If ArrayLinearList has methods that are not listed in LinearList then well need to typecast d,e,f to ALL before performing any of these additional methods ((ArrayLinearList) d).newMethod().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 ListsLinearList [] x = new LinearList [4];x[0] = new ArrayLinearList(20);x[1] = new Chain();x[2] = new Chain();x[3] = new ArrayLinearList();for