The Java data structure implements the sequential representation example
- 2020-04-01 03:09:13
- OfStack
import java.util.Arrays;
public class LineList<E>{
private int size; //The length of the
private Object[] array; //The underlying array
private final int default_length=16; // The default The length of the
public LineList(){
size = 0;
// Use the default The length of the Constructing an array
array = new Object[default_length];
}
public LineList(int length){
if(length<0){
throw new IllegalArgumentException(" The initial The length of the illegal :"+length);
}
// Using the specified The length of the Constructing an array
array = new Object[length];
}
public LineList(E element,int length){
if(length<1){
throw new IllegalArgumentException(" The initial The length of the illegal :"+length);
}
// Using the specified The length of the Constructing an array
array = new Object[length];
//Initializes the first element
array[0] = element;
size++;
}
public LineList(E element){
// Use the default The length of the Initialize array
array = new Object[default_length];
//Initializes the first element
array[0] = element;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size==0;
}
public boolean contains(E e) {
if(indexOf(e) == -1){
return false;
}
return true;
}
public Object[] toArray() {
return Arrays.copyOf(array, size);
}
public void add(E e) {
extendCapacity(size+1);
array[size]=e;
size++;
}
private void extendCapacity(int length){
// The current array The length of the And the need of The length of the The lion
int minCapacity = Math.max(array.length, length);
//Determine whether capacity expansion is needed
if(minCapacity - array.length>0){
// An array of The length of the Add half
int newLength = array.length + array.length/2;
// If the new The length of the It's smaller than the demand , Will demand The length of the As an array The length of the
if(newLength < minCapacity){
newLength=minCapacity;
}
// An array of The length of the No more than Integer.Max_Value
if(newLength > Integer.MAX_VALUE - 8){
newLength = Integer.MAX_VALUE;
}
//Array capacity
array = Arrays.copyOf(array, newLength);
}
}
public void removeAll(E e) {
if(e==null){
for(int i=0;i<size;i++){
if(array[i]==null){
fastRemove(i);
}
}
}else{
for(int i=0;i<size;i++){
if(e.equals(array[i])){
fastRemove(i);
}
}
}
}
private void fastRemove(int index){
if(size-index-1>0){
//The array moves forward from index+1
System.arraycopy(array, index+1, array, index, size-1);
}
//The last element is empty
array[--size]=null;
}
public void clear() {
//Fills the array to null
Arrays.fill(array, null);
//Change the number of elements to 0
size=0;
}
@SuppressWarnings("unchecked")
public E get(int index) {
checkIndex(index);
return (E)array[index];
}
private void checkIndex(int index){
if(index>=size || index<0){
throw new IndexOutOfBoundsException(" The index of crossing the line ");
}
}
@SuppressWarnings("unchecked")
public E set(int index, E element) {
checkIndex(index);
E e = (E)array[index];
array[index]=element;
return e;
}
public void add(int index, E element) {
//Validation index
checkIndex(index);
//Do we need to expand capacity
extendCapacity(size+1);
//Copy the array
System.arraycopy(array, index, array, index+1, size-index);
array[index]=element;
}
@SuppressWarnings("unchecked")
public E remove(int index) {
checkIndex(index);
//The element that gets the index position
E e = (E)array[index];
fastRemove(index);
return e;
}
public int indexOf(E e) {
if(e==null){
for(int i=0;i<size;i++){
if(e==array[i]){
return i;
}
}
}
for(int i=0;i<size;i++){
if(e.equals(array[i])){
return i;
}
}
return -1;
}
public int lastIndexOf(E e) {
//Determines whether the element is null
if(e==null){
for(int i=size-1;i>=0;i--){
if(e==array[i]){
return i;
}
}
}
for(int i=size-1;i>=0;i--){
//If it's null, you'll get a NullPoint exception
//So you need to verify that it is Null
if(e.equals(array[i])){
return i;
}
}
return -1;
}
@SuppressWarnings("unchecked")
public LineList<E> subList(int fromIndex, int toIndex) {
//Determines whether the starting index has crossed the line
if(fromIndex<0 || fromIndex >=size){
throw new IndexOutOfBoundsException(" Start indexing out of bounds :"+fromIndex);
}
//Determines whether the closing index has crossed the line
if(toIndex >=size || fromIndex <0){
throw new IndexOutOfBoundsException(" End index overstep :"+toIndex);
}
//Determines whether the start and end indexes are correct
if(fromIndex > toIndex){
throw new IllegalArgumentException(" Incorrect parameter , The start index should be greater than or equal to the end index ");
}
LineList<E> list = new LineList<E>();
for(int i=fromIndex,j=toIndex;i<=j;i++){
list.add((E)array[i]);
}
return list;
}
}