package com.github.sqlist;

public interface ISequence {
? ? // 在 pos 位置插入 val
? ? boolean add(int pos, Object data);

? ? // 查找關鍵字 key 找到返回 key 的下表，沒有返回 -1
? ? int search(Object key);

? ? // 查找是否包含關鍵字 key 是否在順序表當中（這個和search有點沖突）
? ? boolean contains(Object key);

? ? // 得到 pos 位置的值
? ? Object getPos(int pos);

? ? // 刪除第一次出現的關鍵字 key
? ? Object remove(Object key);

? ? // 得到順序表的長度
? ? int size();

? ? // 打印順序表
? ? void display();

? ? // 清空順序表以防內存泄漏
? ? void clear();
}

實現接口里的每個方法

package com.github.sqlist;

import java.util.Arrays;

/*
?* 順序表
?*/
public class MySequenceImpl implements ISequence {

? ? private Object[] elem;
? ? // 有效數據個數
? ? private int usedSize;
? ? private static final int DEFAULT_SIZE = 10;

? ? public SqList() {
? ? ? ? this.elem = new Object[DEFAULT_SIZE];
? ? ? ? this.usedSize = 0;
? ? }

? ? /**
? ? ?* 判斷是否為滿
? ? ?* @return 滿了返回true,否則返回false
? ? ?*/
? ? private boolean isFull() {
? ? ? ? return this.elem.length == this.usedSize;
? ? }

? ? /**
? ? ?* 在 pos 位置插入 val
? ? ?* @param pos
? ? ?* ? ? ? ?要插入的位置
? ? ?* @param data
? ? ?* ? ? ? ?要插入的值
? ? ?* @return
? ? ?* ? ? ? ?插入成功返回true，否則返回false
? ? ?*/
? ? @Override
? ? public boolean add(int pos, Object data) {
? ? ? ? // 1. 判斷pos位置的合法性
? ? ? ? if (pos < 0 || pos > this.elem.length) {
? ? ? ? ? ? return false;
? ? ? ? }

? ? ? ? // 2. 判斷是否滿了，如果滿了進行擴容
? ? ? ? if (isFull()) {
? ? ? ? ? ? this.elem = Arrays.copyOf(this.elem, 2*this.elem.length);
? ? ? ? }

? ? ? ? // 3. 把pos位置以及之后的數全部向后挪一個位置
? ? ? ? for (int i = this.usedSize-1; i >= pos; i--) {
? ? ? ? ? ? this.elem[i+1] = this.elem[i];
? ? ? ? }

? ? ? ? // 4. 在 pos 位置插入 val
? ? ? ? this.elem[pos] = data;

? ? ? ? // 5. 更新長度
? ? ? ? this.usedSize++;

? ? ? ? return true;
? ? }

? ? /**
? ? ?* 判斷是否為空
? ? ?* @return 表為空返回true，否則返回false
? ? ?*/
? ? private boolean isEmpty() {
? ? ? ? return this.usedSize == 0;
? ? }

? ? /**
? ? ?* 查找關鍵字 key 找到返回 key 的下表，沒有返回 -1
? ? ?* @param key 關鍵字的值
? ? ?* @return 查找成功返回true，失敗返回false
? ? ?*/
? ? @Override
? ? public int search(Object key) {
? ? ? ? // 1. 判斷是否為空
? ? ? ? if (isEmpty()) {
? ? ? ? ? ? return -1;
? ? ? ? }

? ? ? ? // 2. 遍歷查找
? ? ? ? for (int i = 0; i < this.elem.length; i++) {
? ? ? ? ? ? // 注意：判斷條件不能寫成：this.elem[i] == key
? ? ? ? ? ? if (this.elem[i].equals(key)) {
? ? ? ? ? ? ? ? return i;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return -1;
? ? }

? ? /**
? ? ?* 查找是否包含關鍵字 key 是否在順序表當中（這個和search有點沖突）
? ? ?* @param key 關鍵字的值
? ? ?* @return 查找成功返回true，失敗返回false
? ? ?*/
? ? @Override
? ? public boolean contains(Object key) {
? ? ? ? // 1. 判斷是否為空
? ? ? ? if (isEmpty()) {
? ? ? ? ? ? return false;
? ? ? ? }

? ? ? ? // 2. 遍歷查找
? ? ? ? for (int i = 0; i < this.elem.length; i++) {
? ? ? ? ? ? // 注意：判斷條件不能寫成：this.elem[i] == key
? ? ? ? ? ? if (this.elem[i].equals(key)) {
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return false;
? ? }

? ? /**
? ? ?* 得到 pos 位置的值
? ? ?* @param pos 得到的值的位置
? ? ?* @return 成功得到 pos位置的值返回true，否則返回false
? ? ?*/
? ? @Override
? ? public Object getPos(int pos) {
? ? ? ? // 1. 判斷位置是否合法
? ? ? ? if (pos<0 || pos>=this.elem.length) {
? ? ? ? ? ? return null;
? ? ? ? }

? ? ? ? // 2. 位置合法
? ? ? ? return this.elem[pos];
? ? }

? ? /**
? ? ?* 刪除第一次出現的關鍵字 key
? ? ?* @param key 關鍵字
? ? ?* @return
? ? ?*/
? ? @Override
? ? public Object remove(Object key) {
? ? ? ? // 1. 先查表看有沒有這個關鍵字
? ? ? ? // index:關鍵字下標
? ? ? ? int index = search(key);

? ? ? ? // 2. 若表里沒有這個關鍵字
? ? ? ? if (index == -1) {
? ? ? ? ? ? return null;
? ? ? ? }

? ? ? ? // 3. 表里有這個關鍵字
? ? ? ? Object data = this.elem[index];
? ? ? ? int i;
? ? ? ? // 刪除第一次出現的關鍵字 key,把key后面的數全部向前挪一個位置
? ? ? ? for (i = index; i < this.usedSize; i++) {
? ? ? ? ? ? elem[i] = elem[i+1];
? ? ? ? }
? ? ? ? this.usedSize--;
? ? ? ? this.elem[i+1] = null;
? ? ? ? return data;
? ? }

? ? /**
? ? ?* 得到順序表的長度
? ? ?* @return 順序表的長度
? ? ?*/
? ? @Override
? ? public int size() {
? ? ? ? return this.usedSize;
? ? }

? ? /**
? ? ?* 打印順序表
? ? ?*/
? ? @Override
? ? public void display() {
? ? ? ? for (int i = 0; i < this.usedSize; i++) {
? ? ? ? ? ? System.out.print(this.elem[i] + " ");
? ? ? ? }
? ? ? ? System.out.println();
? ? }

? ? /**
? ? ?* 清空順序表以防內存泄漏
? ? ?*/
? ? @Override
? ? public void clear() {
? ? ? ? for (int i = 0; i < this.usedSize; i++) {
? ? ? ? ? ? this.elem[i] = null;
? ? ? ? }
? ? }
}

測試方法的正確性

package com.github.sqlist;


public class TestDemo1 {
? ? public static void main(String[] args) {
? ? ? ? MySequenceImpl mySequence = new MySequenceImpl();

? ? ? ? for (int i = 0; i < 10; i++) {
? ? ? ? ? ? mySequence.add(i,i);
? ? ? ? }
? ? ? ? System.out.println("在最大值10的范圍內插入數據：");
? ? ? ? mySequence.display();
? ? ? ? System.out.println();

? ? ? ? for (int i = 10; i < 20; i++) {
? ? ? ? ? ? mySequence.add(i,i);
? ? ? ? }
? ? ? ? System.out.println("擴容：");
? ? ? ? mySequence.display();
? ? ? ? System.out.println();

? ? ? ? System.out.println("隨機位置插入數據：");
? ? ? ? mySequence.add(9,"list");
? ? ? ? mySequence.display();
? ? ? ? System.out.println();

? ? ? ? System.out.println("search查找一個數據："+mySequence.search("list"));
? ? ? ? System.out.println("contains查找一個數據："+mySequence.contains("list"));
? ? ? ? System.out.println();

? ? ? ? System.out.println("查找某一個位置對應的值："+mySequence.getPos(9));
? ? ? ? System.out.println();

? ? ? ? System.out.println("刪除一個數據："+mySequence.remove(8));
? ? ? ? mySequence.display();
? ? ? ? System.out.println();

? ? ? ? System.out.println("得到順序表的長度:"+mySequence.size());
? ? }
}

測試結果：