Linear List – Array Representation An interface may include constants and abstract methods (i.e., methods for which no implementation is provided).
Linear (or Ordered) Lists instances are of the form
(e0, e1, e2, …, en-1)
where ei denotes a list element
n >= 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
A data object is a set of instances; an instance of a linear list is an ordered set of elements.
Linear List Examples
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)
Notice that Days of Week is used as an example of both a data object and of a linear
list. 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.
Linear List Operations—Length() determine list size
L = (a,b,c,d,e)
length = 5
Linear List Operations—Find(theIndex,x) get element with given index
L = (a,b,c,d,e)
Find(0,x) x=a , return True
Find(2,x) x=c , return True
Find(-1,x) return False
Find(9,x) return False
Linear List Operations—Search(theElement) determine the index of an element
L = (a,b,d,b,a)
Search(d) = 2
Search(a) = 0
Search(z) = -1
The 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 list
Linear List Operations—remove(theIndex) remove and return element with given index
L = (a,b,c,d,e,f,g)
remove(2) returns c
and L becomes (a,b,d,e,f,g)
index of d,e,f, and g decrease by 1
Linear List Operations—Delete(theIndex,x) remove and return element with given index
L = (a,b,c,d,e,f,g)
Linear List Operations—Insert(theIndex, theElement)
add an element so that the new element has a specified index
L = (a,b,c,d,e,f,g)
Insert(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—Insert(theIndex, theElement)
L = (a,b,c,d,e,f,g)
Insert(2,h) => L = (a,b,h,c,d,e,f,g)
index of c,d,e,f, and g increase by 1
Insert(10,h) => error
Insert(-6,h) => error
Data Structure Specification
Language independent
Abstract Data Type
C++
Class
Java
Interface
Abstract Class
Linear List Abstract Data Type
Example of Linear List
Linear List – Array Representation An interface may include constants and abstract methods (i.e., methods for which no implementation is provided).
Linear List – Array Representation
Implemetation of LinearList
LinearList – Find, Search
An abstract class may include constants, variables, abstract methods, and nonabstract methods.
So an abstract class is mor 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.
LinearList -- Delete
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();
}
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 isn’t required (though permissible) to declare each method abstract. This is because all methods listed in an interface are, by default, abstract.
LinearList -- Insert
LinearList -- Output
public 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).
Comments