概念
- 與向量(Vector)的循秩訪問(call-by-rank)不同的是列表采用的是循位置訪問(call-by-position)
- 列表采用的是動(dòng)態(tài)存儲機(jī)制,通過引用或指針來確定元素的實(shí)際物理地址
無序列表實(shí)現(xiàn)
1.類型聲明
public class ListNode<T> {
public T data;
public ListNode pred;//前繼
public ListNode succ;//后繼
public ListNode(){
}
public ListNode(T e,ListNode p,ListNode s){
this.pred=p;
this.succ=s;
this.data=e;
ListNode insertAsdpred(T e);
ListNode insertAsSucc(T e);
}
public class List<T>{
private int size;
private ListNode <T>header;//頭哨兵
private ListNode<T>trailer;//尾哨兵
public List(){
header=new ListNode<T>();
trailer=new ListNode<T>();
header.succ=trailer;
header.pred=null;
trailer.succ=null;
trailer.pred=header;
size=0;
}
2.查找接口
//在結(jié)點(diǎn)p之前的n個(gè)前驅(qū)中,找到等于e的最后者
ListNode find(T e,int n,ListNode p){
while(n--){
if(e==(p=p.pred).data){
return p;
return null;
}
復(fù)雜度是O(n)
3.前插入
//新元素e作為當(dāng)前節(jié)點(diǎn)的前驅(qū)插至列表
ListNode insertAsPred(T e){
ListNode x=new ListNode(e,this.pred,this);
this.pred.succ=x;
x.succ=this;
return x;
}
4.后插入
//新元素e作為當(dāng)前節(jié)點(diǎn)的后繼插至列表
ListNode insertAsSucc(T e){
ListNode x=new ListNode(e,this,this.succ);
this.succ.pred=x;
this.succ=x;
return x;
}
5.刪除操作
//刪除指定節(jié)點(diǎn)p
T remove(ListNode p){
p.pred.succ=p.succ;
p.succ.pred=p.pred;
return p.data;
size--;
}
6.析構(gòu)操作
int clear(){
int oldsize=size;
while(size>0){
remove(header.succ);
}
return oldsize;
}
7.唯一化
//剔除無序列表中重復(fù)元素,返回被刪除元素?cái)?shù)量
int deduplicate(){
int oldsize=size;
if(size<2){
return 0;
}
ListNode p=header;//從頭哨兵開始
rank r=0;
while(trailer!=(p=p.succ)){
ListNode q=find(p.data,r,p);
q ? remove(q):r++);
}
return oldsize-size;
}
復(fù)雜度O(n^2)
有序列表的實(shí)現(xiàn)
1.唯一化
int uniquify(){
int oldsize=size;
if(size<2){
return 0;
}
ListNode p,q;//依次指向緊鄰的各對節(jié)點(diǎn)
for(p=header,q=p.succ;trailer != q; p = q, q = q->succ){
if (p->data == q->data)
{
remove(q);
q = p;
}
return oldsize-size;
}
2.查找
//在節(jié)點(diǎn)p的n個(gè)前驅(qū)中酒唉，找到不大于e的最后者
ListNode search(T e,int n,ListNode p){
while(0<n--){
if((p=p.pred).data<=e)
break;
return p;
}
