Java实现线性表-顺序表示和链式表示

顺序表示和链式表示的比较：1.读写方式：顺序表可以顺序存取，也可以随机存取；链表只能从表头顺序存取元素；2.逻辑结构与物理结构：顺序存储时，逻辑上相邻的元素其对应的物理存储位置也相邻；链式存储时，逻辑上相邻的元素，其物理存储位置则不一定相邻；3.查找、插入和删除操作：按值查找，当线性表在无序的情况下，两者的时间复杂度均为o（n）；而当顺序表有序时，可采用折半查找，此时时间复杂度为o（log n）；按位查找，顺序表支持随机访问，时间复杂度为o（1）；而链表的平均时间复杂度为o（n）。顺序表的插入和删除操作平均需要移动半个表长的元素；链表的插入、删除操作时，只需修改相关节点的指针即可。4.空间分配：顺序存储一般是基于静态存储分配，一单存储空间装满就不能扩充；链式存储的节点空间只有在需要的时候申请分配，只要内存有足够的空间即可分配。顺序表示的实现：public class ArrayList<E> {
final int defaultSize=0;
int maxSize; //线性表的最大长度
int length; //线性表当前长度
Object[] arrayList; //存储线性表的数组

/*
* 构造函数
*/
public ArrayList（int size）{
initList（size）;
}

//按给定size初始化顺序表
public void initList（int size） {
if（size < 0）{
throw new RuntimeException（"数组大小错误：" + size）;
}else{
this.maxSize= size;
this.length=0;
this.arrayList = new Object[size];
}
} //表长
public int length（） {
return length;
} //按值查找
public int locateElem（Object e） {
for（int i=0 ;i<length;i++）{
if（arrayList[i] == e）{
return i;
}
}
return -1;
} //按位查找
public Object getElem（int i） {
if（i<0 || i>=length ）{
throw new RuntimeException（"参数出错："+i）;
}
if（length ==0）{
throw new RuntimeException（"顺序表为空"）;
}
return arrayList[i];
} //插入
public void insert（int i, Object e） {
if（i<0 || i>length+1 ）{
throw new RuntimeException（"新元素插入位置有误："+i）;
}
if（i >= maxSize）{
throw new RuntimeException（"顺序表已满，不能再插入新的元素"）;
}
for（int j=length;j<i; j--）{
arrayList[j]=arrayList[j-1];
}
arrayList[i]=e;
length++;
} //删除
public void delete（int i, Object e） {
if（i<0 || i > length-1）{
throw new RuntimeException（"需删除元素位置有误："+i）;
}
if（length == 0）{
throw new RuntimeException（"顺序表为空，不能删除元素"）;
}
for（int j=i;j<length-1;j++）{
arrayList[j] = arrayList[j+1];
}
arrayList[length-1]="";
length--;
} //判空
public boolean isEmpty（） {
return length==0 ？ true : false;
} //删除顺序表
public void destroyList（） {
this.arrayList=null;
this.length=0;
this.maxSize=0;
}
}单链表表示的实现：class Node<E>{
E e; //数据
Node<E> next; //下一个节点

Node（）{}

Node（E e）{
this.e = e;
this.next = null;
}
}public class LinkedList<E> {
private Node<E> header = null; //头结点
int size=0; //链表大小

public LinkedList（） {
this.header = new Node<E>（）;
} //得到链表的长度
public int length（） {
return size;
} //按值查找节点，返回该节点的位置
public int locateElem（E e） {
Node<E> temp = header;
int count = 1;
while（temp.next ！= null && temp.e ！= e）{
temp = temp.next;
count ++;
}
return count;
} //找到第index个位置的节点
public Node<E> getNode（int index） {
if（index > size || index < 0）{
throw new RuntimeException（"索引值有错：" + index）;
}
Node<E> temp = new Node<E>（）;
temp = header;
int count=1;
while（count ！= index）{
temp = temp.next;
count ++;
}
return temp;
} //尾添加
public boolean addToLast（E e） {
if（size == 0）{
header.e = e;
}else{
Node<E> newnode = new Node<E>（e）; //根据需要添加的内容封装为节点
Node<E> last = getNode（size）; //得到最后一个节点
last.next = newnode;
}
size ++;
return true;
}

//头添加
public boolean addTofirst（E e） {
if（size == 0）{
header.e = e;
}else{
Node<E> newnode = new Node<E>（e）; //根据需要添加的内容封装为节点
newnode.next = header.next;
header.next = newnode;
}
size ++;
return true;
} //插入到第index个的位置
public boolean insert（int index, E e） {
Node<E> newnode = new Node<E>（e）; //根据需要添加的内容封装为节点
Node<E> cnode = getNode（index-1）; //得到第index-1个节点
newnode.next = cnode.next;
cnode.next = newnode;
size++;
return true;
} //删除第index个节点
public boolean delete（int index） {
Node<E> prinode = getNode（index-1）; //得到被删除的节点的前一个节点
Node<E> delnode = prinode.next; //得到被删除的节点
prinode.next = delnode.next;
size --;
return true;
} //判空
public boolean isEmpty（） {
return size==0 ？ true : false;
} public void destroyList（） {
header = null;
size = 0;
}

//输出
public String toString（）{
StringBuilder s = new StringBuilder（"["）;
Node<E> temp = header;
for（int i=0; i < size;i++）{
s.append（temp.e.toString（）+" "）;
temp = temp.next;
}
s.append（"]"）;
return s.toString（）;
}
}双链表表示的实现class TNode<E>{
E e;
TNode<E> prior, next;

TNode（）{}
TNode（E e）{
this.e = e;
prior = null;
next = null;
}
}public class DoubleLinkedList<E> {
private TNode<E> header = null; //头结点
int size=0; //链表大小

public DoubleLinkedList（）{
this.header = new TNode<E>（）;
}

//尾添加
public boolean addToLast（E e） {
if（size == 0）{
header.e = e;
}else{
TNode<E> TNode = new TNode<E>（e）; //根据需要添加的内容封装为节点
TNode<E> last = getNode（size）; //得到最后一个节点
last.next = TNode;
TNode.prior=last;
}
size ++;
return true;
}

//找到第index个位置的节点
public TNode<E> getNode（int index）{
if（index > size || index < 0）{
throw new RuntimeException（"索引值有错：" + index）;
}
TNode<E> temp = new TNode<E>（）;
temp = header;
int count =1;
while（count ！= index）{
temp = temp.next;
count ++;
}
return temp;
}

//插入到第index个的位置
public boolean insert（int index,E e）{
TNode<E> TNode = new TNode<E>（e）;
TNode<E> cnode = getNode（index-1）; //找到第index-1个位置的节点
TNode.next=cnode.next;
TNode.prior = cnode;
cnode.next.prior = TNode;
cnode.next = TNode;
size++;
return true;
}

//删除第index个节点
public boolean delete（int index）{
TNode<E> delnode = getNode（index）;
delnode.prior.next=delnode.next;
delnode.next.prior= delnode.prior;
size--;
return true;
}
}本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-07/119877.htm