1Data Structuresdata objectset or collection of instancesinteger = {0, +1, -1, +2, -2, +3, -3, …}daysOfWeek = {S,M,T,W,Th,F,Sa}Data Objectinstances may or may not be relatedmyDataObject = {apple, chair, 2, 5.2, red, green, Jack}Data StructureData object +relationships that exist among instancesand elements that comprise an instanceAmong instances of integer369 < 370280 + 4 = 284Data StructureAmong elements that comprise an instance3693 is more significant than 63 is immediately to the left of 69 is immediately to the right of 6The relationships are usually specified by specifying operations on one or more instances.add, subtract, predecessor, multiplyData StructureLinear (or Ordered) Listsinstances are of the form(e0, e1, e2, …, en-1)where eidenotes a list elementn >= 0 is finitelist size isn2Linear ListsL = (e0, e1, e2, e3, …, en-1)relationshipse0is the zero’th (or front) elementen-1is the last elementeiimmediately precedes ei+1Linear 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)Linear List Operations—size()determine list sizeL = (a,b,c,d,e)size = 5Linear List Operations—get(theIndex)get element with given indexL = (a,b,c,d,e)get(0) = aget(2) = cget(4) = eget(-1) = errorget(9) = errorLinear List Operations—indexOf(theElement)determine the index of an elementL = (a,b,d,b,a)indexOf(d) = 2indexOf(a) = 0indexOf(z) = -1Linear List Operations—remove(theIndex)remove and return element with given indexL = (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 13Linear List Operations—remove(theIndex)remove and return element with given indexL = (a,b,c,d,e,f,g)remove(-1) => errorremove(20) => errorLinear List Operations—add(theIndex, theElement)add an element so that the new element has a specified indexL = (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 1Linear 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 1add(10,h) => erroradd(-6,h) => errorData Structure SpecificationLanguage independent¾Abstract Data TypeJava¾Interface¾Abstract ClassLinear List Abstract Data TypeAbstractDataType LinearList{instancesordered finite collections of zero or more elementsoperationsisEmpty(): return true iff the list is empty, false otherwisesize(): return the list size (i.e., number of elements in the list)get(index): return the indexth element of the listindexO f(x): return the index of the first occurrence of x in the list, return -1 if x is not in the listremove(index): remove and return the indexth element, elements with higher index have their index reduced by 1add(theIndex, x): insert x as the indexth element, elementswiththeIndex >= index have their index increased by 1output(): 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).4Linear List as Java Interfacepublic interfaceLinearList{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 Interfacepublic classArrayLinearList 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.Linear List As Java Abstract Classpublic abstract classLinearListAsAbstractClass{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 classArrayLinearListextends LinearListAsAbstractClass{// code for all abstract classes must come here}Implementing Many Interfacespublic classMyInteger implements Operable, Zero,CloneableObject{// code for all methods of Operable, Zero,// and CloneableObject must be provided}5Extending Many ClassesNOT PERMITTED IN JAVAA Java class may implement as many interfaces as it wants but can extend at most 1 class.Data Structures In TextAll but 1 of our data structures are specified as Java interfaces.Exception is Graph in Chapter 17.Java specifies all of its data structures as