特性
开始节点--> 数据元素 ... --> 终端节点
操作
clear、isEmpty、length、get、insert、remove、indexOf
public interface IList {
// 线性表置空操作
public void clear();
// 判断线性表是否为空操作
public boolean isEmpty();
// 获取线性表中元素的长度操作
public int length();
// 获取指定位置上面的元素操作
public Object get(int i);
// 在指定位置上面插入元素的操作
public void insert(int i, Object x);
// 删除指定位置上面的元素的操作
public void remove(int i);
// 查找指定元素的位置首次出现的位置操作
public int indexOf(Object x);
// 显示线性表中的内容操作
public void display();
}
类型
顺序表
顺序存储， 逻辑上相邻的数据元素，在物理存储上也是相邻的。 不便于插入和删除
public class SqList implements IList {
// 线性表存储空间
private Object[] listElem;
// 线性表的当前长度
private int curLen;
// 顺序表类的构造函数，构造一个存储空间容量为maxSize的线性表
public SqList(int maxSize) {
// TODO Auto-generated constructor stub
curLen = 0;
listElem = new Object[maxSize];
}
// 将一个已经存在的线性表置成空表
public void clear() {
// TODO Auto-generated method stub
// 置顺序表的当前长度为0
curLen = 0;
}
// 判断线性表中的数据元素的个数是否为0，若为0则返回true，否则返回false
public boolean isEmpty() {
// TODO Auto-generated method stub
return curLen == 0;
}
// 求线性表中的数据元素的个数并返回其值
public int length() {
// TODO Auto-generated method stub
// 返回顺序表的当前长度
return curLen;
}
// 读取到线性表中的第i个数据元素并由函数返回其值，其中i的取值范围为0≤i≤length()-1，若i不在此范围则抛出异常
public Object get(int i) {
// TODO Auto-generated method stub
if (i < 0 || i >= curLen) {
throw new RuntimeException("第" + i + "个元素不存在");
}
return listElem[i];
}
// 在线性表的第i个数据元素之前插入一个值位x的数据元素
public void insert(int i, Object x) {
// TODO Auto-generated method stub
// 判断表是否满了
if (curLen == listElem.length) {
throw new RuntimeException("存储空间已经满了，无法插入新的元素");
}
// 插入的位置不合法
if (i < 0 || i > curLen) {
throw new RuntimeException("插入的位置不合法");
}
// 必须要从最后一个元素开始依次逐个后移动，直到第i个数据元素移动完毕为止。
for (int j = curLen; j > i; j--) {
listElem[j] = listElem[j - 1];
}
listElem[i] = x;
curLen++;
}
public void remove(int i) {
// TODO Auto-generated method stub
if (i < 0 || i > curLen - 1) {
throw new RuntimeException("删除的位置不合法");
}
for (int j = i; j < curLen; j++) {
listElem[j] = listElem[j+1];
}
curLen--;
}
// 返回线性表中首次出现指定的数据元素的位序号，若线性表中不包含此数据元素，则返回-1
public int indexOf(Object x) {
// TODO Auto-generated method stub
for (int i = 0; i < curLen; i++) {
if (listElem[i].equals(x)) {
return i;
}
}
return -1;
}
// 输出线性表中的数据元素
public void display() {
// TODO Auto-generated method stub
for (int i = 0; i < curLen; i++) {
System.out.print(listElem[i] + " ");
}
System.out.println();
}
// 测试
public static void main(String[] args) {
SqList sqList = new SqList(10);
sqList.insert(0, "a");
sqList.insert(1, "z");
sqList.insert(2, "d");
sqList.insert(3, "m");
sqList.insert(4, "z");
int order = sqList.indexOf("z");
if (order!=-1) {
System.out.println("顺序表中第一次出现的值为z的数据元素的位置为："+order);
}else {
System.out.println("顺序表中不包括z元素");
}
}
}
链表
链式存储，单向链表，节点保存下一个节点的引用，便于插入和删除
public class Node {
// 存放结点的值
private Object data;
// 后继结点的引用
private Node next;
// 无参数时的构造函数
public Node() {
// TODO Auto-generated constructor stub
this(null, null);
}
// 带有一个参数时的构造函数
public Node(Object data) {
this(data, null);
}
// 带有两个参数时的构造函数
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}