《数据结构》 (java版) 课件 牛小飞 4 线性表

4线性表本章内容线性表的定义线性表的数组描述线性表的链式描述线性表线性表(linearlist，list)是有限的数据集合，数据之间有线性次序关系。即线性表是一个数据序列：a0，a1，…，an-1线性表的长度是数据的个数长度为0的线性表叫做空表根据数据在线性表的位置，赋予数据唯一的编号(Index)，长度为n的线性表的数据编号为0、1、…、n–1对

ai而言，i≠0，1，ai-1是前驱(Predecessor

)，ai+1是后继(Successor

)称a0为表头(Head)，an-1为表尾(Tail)线性表线性表的图示形式：线性表是从实际应用抽象出来的数据结构:上体育课时排成的队列、根据下单时间形成的订单序列、根据学号大小编排的学生花名册等。线性表的操作线性表有若干操作：addremove...add操作向线性表增加编号为i的数据：a0，a1，…，ai-1，ai，…，an-1

⇒a0，a1，…，ai-1，a'i，a'i+1，…，a'n其中，a'i=x，a'i+1=ai，…，a'n=an-1add操作后，线性表的长度由n变为n+1

add(c，1)remove操作从线性表删除编号为i的数据：a0，a1，…，ai-1，ai，…，an-1

⇒a0

，a1，…，ai-1，a'i，a'i+1，…，a'n-2其中，a'i=ai+1，a'i+1=ai+2，…，a'n-2=an-1，

remove操作后，线性表的长度由n变为n-1

remove(1)packagelist;public

interfaceIList<T>{

intsize();

voidclear();

booleanisEmpty(); Tget(int

index); Tset(int

index,Tx);

voidadd(int

index,Tx); Tremove(int

index);

intindexOf(Tx);

Iterator<T>iterator();

}抽象数据类型线性表是一个抽象数据类型，由IList接口定义。线性表的实现需要解决三个问题：如何存放数据如何存放数据之间的关系如何高效的实现操作数组描述数组元素存放数据，数据的索引号和数组元素下标一一对应数组元素的相邻关系表示数据的前后关系数组是引用型数组：Object[]数组描述线性表：A，B，C，D简明画法：CArrayListCArrayList是使用数组描述实现的线性表。public

classCArrayList<T>implementsIList<T>,Iterable<T>,RandomAccess,Cloneable{

privateObject[]elements;//存储数据的数组

private

int

size;//数据个数

publicCArrayList(int

maxSize){//空表

elements=newObject[maxSize];

//size=0; }CArrayList的对象CArrayList<Integer>sl=newCArrayList<>(6);Object[]

elementsintsize：0length6...componentTypeObject∧∧CArrayList的对象简明画法：Object[]

elementsintsize：0∧∧∧∧∧∧索引号的合法性检查很多操作都涉及索引号，为了保证代码的健壮性，需要对输入的索引号进行合法性检查

private

voidrangeCheckForAdd(int

index){//add用

if(index<0||index>size)

throw

newIndexOutOfBoundsException(String.valueOf(index)); }

private

voidrangeCheck(int

index){//其它方法用

if(index<0||index>=size)

throw

newIndexOutOfBoundsException(String.valueOf(index)); }

public

intsize(){

return

size; }sizesize方法返回线性表的长度(数据个数)

public

booleanisEmpty(){

return

size==0; }isEmptyCArrayList从IList接口继承了isEmpty方法，这里进行了覆盖。也可以不覆盖。如果线性表为空表，isEmpty方法返回false，否则返回true。

default

booleanisEmpty(){

return

size()==0; }Tget(intindex)get方法返回编号为index的数据。

@SuppressWarnings("unchecked")

publicTget(int

index){ rangeCheck(index);

return(T)elements[index]; }Tset(intindex)set方法修改编号为index的数据，并返回修改前的数据。

@SuppressWarnings("unchecked")

publicTset(int

index,Tx){ rangeCheck(index); TOldValue=(T)elements[index];

elements[index]=x;

return

OldValue; }voidadd(intindex，Tx)add方法向线性表加入数据x，编号为index。add造成结构改变：某些数据的先驱和后继发生了变化。(a0,a1,...,aindex-1,aindex,aindex+1,...)(a0,a1,...,aindex-1,

x,

aindex+1,aindex+2,...)错误的做法a0a1a2a3a4a5例如，在位置2插入数据x。elements[2]=x;a0a1

a3a4a5x向后复制数据a0a1

a2

a2a3a4a5a0a1a2a3a4a5在位置2插入数据x。向后复制数据a0a1

a2

a2a3a4a5a0a1a2a3a4a5e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[6]=e[5]e[5]=e[4]e[4]=e[3]e[3]=e[2]e[k]

=e[k-1]k

=

size，...，index+1向后复制数据

private

voidmoveBackward(int

index){

for(int

i=size;i>index;--i)

elements[i]=elements[i-1]; }voidadd(intindex，Tx)判断index的合法性判断表是不是已满向后复制，腾出空间赋值++sizevoidadd(intindex，Tx)

public

voidadd(int

index,Tx){ rangeCheckForAdd(index); ensureCapacity(size+1);//确保有空间存放x

//moveBackward(index); System.arraycopy(elements,index,

elements,index+1,size-index);

elements[index]=x; ++size; }

public

static

native

voidarraycopy(Objectsrc,int

srcPos,Objectdest,int

destPos,

int

length);src：sourcedest:destinationsrcPosdestPos

srcPos+length-1System类的arraycopy方法Tremove(intindex)remove方法从线性表删除编号为index的数据，并返回这个数据。remove造成结构改变：某些数据的先驱和后继发生了变化。(a0,a1,...,aindex-1,aindex,aindex+1,...)(a0,a1,...,aindex-1,aindex+1,...)错误的做法删除位置2的数据a0a1a2

a3a4a5a0a1∧

a3a4a5∧∧∧∧∧∧∧∧向前复制数据删除位置2的元素a0a1a3

a4

a5

a5a0a1a2a3

a4

a5

∧∧∧∧∧∧∧∧向前复制数据

private

voidmoveForward(int

index){

for(int

i=index;i<size;++i)

elements[i]=elements[i+1]; }Tremove(intindex)判断下标的合法性向前移动(覆盖被删除的数据元素)--sizeTremove(intindex)

@SuppressWarnings("unchecked")

publicTremove(int

index){ rangeCheck(index); Tvalue=(T)elements[index];

//moveForward(index); System.arraycopy(elements,index+1,

elements,index,size-index-1);

elements[--size]=null;//防止内存泄漏

return

value; }intindexOf(Tx)给定一个值，输出这个值在线性表的位置。顺序查找算法：位置0到size-1的数据元素逐一与x比较，如果有相等的数据，则返回它所在的位置；如果所有的数据都不等于x，则返回-1。a0a1a2a3...asize-1∧...∧0123...size-1length-1intindexOf(Tx)

public

intindexOf(Tx){

for(int

i=0;i<size;i++){

if(elements[i].equals(x))

return

i;

//必须调用equals,不能elements[i]==x }

return-1; }xelements[i]

clear删除所有的数据，使线性表成为空表。a0a1a2a3...asize-1∧...∧0123...size-1length-1voidclear()

public

voidclear(){

size=0; }空表：size=0Object[]

elementsintsize：0a0a1a2a3...asize-1∧...∧0123...size-1length-1错误的做法

public

voidclear(){

for(int

i=0;i<size;i++)

elements[i]=null;//防止内存泄漏

size=0; }Object[]

elementsintsize：0∧∧∧∧...∧∧...∧0123...size-1length-1voidclear()a0a1a2a3a4a5a0a1a2a3a4a5∧∧∧原有的数组满了生成新的的数组，并复制原数组的数据。例如，将原数组a扩大为a的1.5倍：Arrays.copyOf(a,a.length+a.length/2)由数组a生成一个新数组，新数组的前length个数组元素复制于a，其它的数组元素=null。扩充容量

private

voidensureCapacity(int

minCapacity){

//overflow-consciouscode

if(minCapacity-elements.length>0)grow(minCapacity);}

private

voidensureCapacity(int

minCapacity){

if(minCapacity>elements.length)//有溢出则错误grow(minCapacity);}扩充容量有问题的写法：如果a>0，并且a的值=Byte.MAX_VALUE，则a+1<0如果a<0，并且a的值=Byte.MIN_VALUE，则a-1>0byte的范围-128～1270-12812701127-128-127-12-2+-128129255254溢出public

classTest{

public

static

voidmain(String[]args){ System.out.println(Byte.MAX_VALUE); System.out.println((byte)(Byte.MAX_VALUE+1)); System.out.println((byte)(Byte.MAX_VALUE+3)); System.out.println();

System.out.println(Byte.MIN_VALUE); System.out.println((byte)(Byte.MIN_VALUE-1)); System.out.println((byte)(Byte.MIN_VALUE-3)); }}127-128-126-128127125溢出

private

static

final

int

MAX_ARRAY_SIZE=Integer.MAX_VALUE-8;

private

voidgrow(int

minCapacity){

//overflow-consciouscode

int

oldCapacity=elements.length;

int

newCapacity=oldCapacity+(oldCapacity>>1);

if(newCapacity-minCapacity<0)

newCapacity=minCapacity;

if(newCapacity-MAX_ARRAY_SIZE>0)

newCapacity=hugeCapacity(minCapacity);

elements=Arrays.copyOf(elements,newCapacity); }扩充容量

private

static

inthugeCapacity(int

minCapacity){

if(minCapacity<0)//overflow

throw

newOutOfMemoryError();

return(minCapacity>MAX_ARRAY_SIZE)?Integer.MAX_VALUE:

MAX_ARRAY_SIZE;}扩充容量扩充容量代码参考了Java类库问题的规模：线性表的数据个数:size，记为n。size()、isEmpty()、get(intindex):O(1)算法复杂性分析

位置012......n-

1n次数nn-1

1

0平均次数（等概率）：(1/(n+1))*(n+n-1+...+1+0)=n/2，即O(n)add(intindex,Tx):主要操作是复制，复制次数n-index

最少复制次数？最多复制次数？算法复杂性分析remove(intindex):复制次数n-index-1最少复制次数？最多复制次数？

位置0

1

2...n

-

2n

-

1次数n

-

1n

-2...1

0平均次数（等概率）：(1/n)*(n-1+...+1+0)=(n-1)/2，即O(n)算法复杂性分析indexOf(Tx):主要操作是比较操作。查找成功：最少比较次数？最多比较次数？

位置012......n-2n-1次数12n-1n平均次数（等概率）：(1/n)*(n+...+1)=(n+1)/2，即O(n)查找失败：对任何不在线性表的x，都需要比较n次，即O(n)算法复杂性分析扩充容量:除了需要new新对象外，主要操作是复制原有的数据，需要复制n个数据，O(n)算法复杂性分析

publicIterator<T>iterator(){

return

newItr(); }

private

classItrimplementsIterator<T>{//内部类

private

int

cursor;//下一个数据的下标

//publicItr(){

//curPos=0;

//}

public

booleanhasNext(){

return

cursor!=size; }

@SuppressWarnings("unchecked")

publicTnext(){

return(T)elements[cursor++]; } }实现Iterable接口迭代器提供对线性表的遍历，即一个不多一个不少的给出线性表的数据intcursorObject[]

elementsintsizelength6...componentTypeObject[]实现Iterable接口

for(inti=0;i<sl.size();i++) System.out.print(sl.get(i)+""); System.out.println();

for(Iterator<Integer>i=sl.iterator();i.hasNext();) System.out.print(i.next()+""); System.out.println();

for(Integerele:sl) System.out.print(ele+""); System.out.println();

sl.forEach(System.out::print);实现了Iterable接口，可以使用如下的方式读取所有的数据:实现Iterable接口importjava.util.RandomAccess;public

classCArrayList<T>implementsIlist<T>,

RandomAccess{ //未实现了RandomAccess接口，用以下的方法

for(Iterator<Integer>i=sl.iterator();i.hasNext();) System.out.print(i.next()+""); System.out.println(); //实现了RandomAccess接口，用以下的方法

for(int

i=0;i<sl.size();i++) System.out.print(sl.get(i)); System.out.println();实现RandomAccess接口 publicstaticvoidmain(String[]args){ CArrayList<Integer>sl=newCArrayList<>(); sl.add(0,1); sl.add(0,2); sl.add(0,3); System.out.println(sl);StringtoString()list.CArrayList@23651e3f

publicStringtoString(){

returngetClass().getName()+"@"+Integer.toHexString(hashCode());}Object类有成员方法：Object的子类可以覆盖该方法，方便调试。

publicStringtoString(){ Stringstr=getClass().getName()+":";

for(int

i=0;i<size;i++)

str+=elements[i]+"";

return

str; }StringtoString() publicstaticvoidmain(String[]args){ CArrayList<Integer>sl=newCArrayList<>(); sl.add(0,1); sl.add(0,2); sl.add(0,3); System.out.println(sl);list.CArrayList:3

2

1

StringtoString()

protected

nativeObjectclone()throwsCloneNotSupportedException;Object类有成员方法：Objectclone()如果不覆盖clone方法而直接调用，则抛出异常。

@SuppressWarnings("unchecked")

publicObjectclone(){

try{CArrayList<T>v=(CArrayList<T>)super.clone();

return

v;}catch(CloneNotSupportedExceptione){

//thisshouldn'thappen,sinceweareCloneable

throw

newInternalError(e);}}public

classCArrayList<T>implementsIlist<T>,RandomAccess,Cloneable{Objectclone()clone方法采用“浅度”复制策略，生成一个新对象，新对象的各字段(成员变量)的值和母体相同。100Hello100HellocloneObjectclone()……elementssizeelementssizeObjectclone()

@SuppressWarnings("unchecked")

publicObjectclone(){

try{CArrayList<T>v=(CArrayList<T>)super.clone();

v.elements=Arrays.copyOf(elements,elements.length);

return

v;}catch(CloneNotSupportedExceptione){

//thisshouldn'thappen,sinceweareCloneable

throw

newInternalError(e);}}public

classCArrayList<T>implementsIlist<T>,RandomAccess,Cloneable{Objectclone()……elementssizeelementssizeObjectclone()……

public

booleanequals(Objectobj){

return(this==obj);}默认的equals判断是不是引用了同一个对象，引用了同一个对象当然相等。equals方法Object类有equals方法，该方法用于比较两个引用变量引用的对象是否相等

public

static

booleanequals(Object[]a,Object[]a2){

if(a==a2)

return

true;

if(a==null||a2==null)

return

false;

int

length=a.length;

if(a2.length!=length)

return

false;

for(int

i=0;i<length;i++){Objecto1=a[i];Objecto2=a2[i];

if(!(o1==null?o2==null:o1.equals(o2)))

return

false;}

return

true;}Arrays.equals两个数组相等的定义：

@SuppressWarnings("unchecked")

public

booleanequals(Objectobj){

if(obj==null)

return

false;

if(this==obj)

return

true;

if(obj

instanceofCArrayList<?>){//语法要求，不能写成CArrayList<T> CArrayList<T>rhd=(CArrayList<T>)obj;

if(this.size!=rhd.size)

return

false;

for(int

i=0;i<size;i++){

if(!elements[i].equals(rhd.elements[i]))

return

false; }

return

true; }

return

false; }CArrayList相等的定义数据个数相同对应位置的数据相等

public

native

inthashCode();Object类有成员方法：2个对象相等，它们的hashCode必须相等。2个对象不相等,它们的hashCode不必不相等。inthashCode()

public

inthashCode(){

returnInteger.hashCode(value);}

public

static

inthashCode(int

value){

return

value;}Integer.hashCode

public

inthashCode(){

int

h=hash;//hash的初值=0

if(h==0&&value.length>0){

char

val[]=value;

for(int

i=0;i<value.length;i++){

h=31*h+val[i];}

hash=h;}

return

h;}String.hashCode

public

static

inthashCode(Objecta[]){

if(a==null)

return0;

int

result=1;

for(Objectelement:a)

result=31*result+(element==null?0:element.hashCode());

return

result;}Arrays.hashCodeCArrayList的hashCode

public

inthashCode(){

returnArrays.hashCode(elements); }java类库：List、ListIterator接口java.util.ArrayList、java.util.Vector（线程安全）

数组的下标与数据的编号一一对应动态扩展

算法：向前、向后复制，顺序查找小结部分代码参考了java类库的ArrayList类，向作者表示感谢。致谢主要内容Node(结点)类单(向)链表：用引用变量表示后继关系的线性表实现方式性能分析带头结点的单(向)链表循环单(向)链表双向链表：用引用变量表示前驱和后继关系的线性表实现方式双向循环链表Node类privatestaticclassNode<T>{//嵌套类 Tdata; Node<T>next; ...}Node类对象之间的引用关系∧Node对象简称结点privatestaticclassNode<T>{//嵌套类 Tdata; Node<T>next; ...}线性表的链式描述a0a1a2a3使用结点存储(引用)数据结点之间的引用关系与线性表数据之间的先后关系一致线性表的链式描述4个数据=>4个结点，结点的字段data引用数据对象。若数据之间有先后关系，对应的结点之间有引用关系。SinglyLinkedList(单向链表)：由字段next可找到后继结点a0a1a2a3∧结点的相关约定结点的编号：1、2、3结点的命名：用存储的数据命名，结点a0、结点a1。首结点、尾结点前驱结点、后继结点a0a1a2a3∧CLinkedListpublic

classCLinkedList<T>implementsIList<T>,Iterable<T>,Cloneable{ privateNode<T>first; private

int

size;...

private

static

classNode<T>{//嵌套类

Tdata;

Node<T>next;

Node(Tdata,Node<T>next){

this.data=data;

this.next=next; } }}CLinkedList是使用单链表实现的线性表。CLinkedList对象firstNode对象size=3a0a1a2CLinkedList的对象∧firstsize=3a0a1a2∧简明画法/* CLinkedList(){

first=null; size=0; }*/构造器构造器构建空表。字段size=0，并且字段first=null判断线性表是否为空表，判断size==0，或first==nullfirst=∧size=0p=p.next;Node<T>p=first;pp=p.next;通过字段next可以找到后继结点。找后继结点first∧a0a1a2p=p.next;

=

∧

p=p.next;Node<T>p=first;pp=p.next;pp形象的表示：p跑向下一个结点找后继结点first∧a0a1a2p=p.next;pfor(Node<T>p=first;p!=null;p=p.next){

…//

处理数据}遍历链表：从头至尾，依次“访问”各个数据课堂练习first∧a0a1a2

private

classItrimplementsIterator<T>{

privateNode<T>cursor;

publicItr(){

cursor=first; }

public

booleanhasNext(){

return

cursor!=null; }

publicTnext(){ Tdata=cursor.data;

cursor=cursor.next;

return

data; } }迭代器first∧a0a1a2

public

intindexOf(Tx){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next{if(p.data.equals(x))//这种表达方式数据不能为null

return

index;

index++ }

return-1; }first∧a0a1a2intindexOf(Tx)

public

intindexOf(Tx){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){if(x.equals(p.data))//这种表达方式x不能为null

return

index; ++index; }

return-1; }intindexOf(Tx)

public

intindexOf1(Tx){

if(x==null){

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){

if(p.data==null)

return

index; ++index; } }else{

int

index=0;

for(Node<T>p=first;p!=null;p=p.next){

if(x.equals(p.data))

return

index; ++index; } }

return-1; }x可以是null，数据中也可以有nullintindexOf(Tx)first∧a0a1a2Tget(intindex)编号为index的数据存储于第index+1个结点。如何找到第index+1个结点？index=0:p所指的就是，执行0次p=p.nextindex=1:执行1次p=p.nextindex=2:执行2次p=p.nextp=first需要执行index次找后继结点的操作：p=p.next。 Node<T>p=first;

for(int

i=0;i<index;i++)

p=p.next;Tget(intindex)first∧a0a1a2循环结束后，p引用了第index+1个结点，它存储的是编号为index的数据。

publicTget(int

index){ rangeCheck(index); Node<T>p=first;

for(int

i=0;i<index;i++)

p=p.next;

return

p.data; }Tget(intindex) Node<T>p=first;

for(int

i=0;i<index-1;i++)

p=p.next;first∧a0a1a2下面的循环结束后：p引用了第几个结点？它是第index+1个结点的？课堂练习abcepqabceqp∧为结点加入新的后继结点∧∧新创建一个结点(用q引用它)，将它作为结点p的后继结点：abcepqq.next=p.next;p.next=q;或者：p.next=newNode<T>(e,p.next);

为结点加入新的后继结点∧∧q=new

Node<>(e,null);创建结点，存储x。将新结点加入链表，它的前驱结点是第index个结点，后继结点是前驱结点的后继结点。首先使p引用前驱结点，然后利用上面介绍的操作即可。注意：首结点没有前驱结点，需要特殊处理。voidadd(intindex,Tx)

public

voidadd(int

index,Tx){ rangeCheckForAdd(index);

if(index==0){//没有前驱结点:空表或加入的数据编号为index

first=newNode<T>(x,first);//加入后作为第1个结点 }else{ Node<T>p=first;

for(int

i=0;i<index-1;i++)

p=p.next;

p.next=newNode<T>(x,p.next); } ++size; }voidadd(intindex,Tx)acdbq.next=p.next;qpq=p;p=p.next;帮助GC：p.next=null;p.data=null;p删除结点的后继结点∧删除结点p的后继结点：找到第index+1个结点的前驱结点利用上面介绍的操作即可。注意：首结点没有前驱结点，需要特殊处理。Tremove(intindex)

publicTremove(int

index){ rangeCheck(index);//空表会抛异常 Node<T>p=first;

if(index==0){//没有前驱结点

first=first.next; }else{//有前驱结点

for(int

i=0;i<index-1;i++)

p=p.next; Node<T>q=p;

p=p.next;

q.next=p.next; }

//p指向待删除结点 Tvalue=p.data;

p.data=null;//帮助GC

p.next=null; --size;

return

value; }Tremove(intindex)voidclear()first=

public

voidclear(){

while(first!=null){//不断的删除第1个结点 Node<T>q=first;//q引用待删除的结点

first=first.next;//下一个结点

q.data=null;//帮助GC

q.next=null; }

size=0; }qfirsta0a1a2a0a1a2∧∧Node<T>pre=null;for(Node<T>p=first;p!=null;pre=p,p=p.next){….if(p.data….)}如果是空表，则pre=null，没有前驱结点如果满足条件的结点是第1个结点，

则pre=null，没有前驱结点prefirsta0a1a2p根据某条件找前驱结点∧ Node<T>p=null;//c的前驱结点 Node<T>c=first; Node<T>q;//q的后继结点

while(c!=null){//可替换成其他条件

q=cur.next;//记住c的后继结点 …处理c引用的结点

p=c;//准备处理下一个结点

c=q; }pfirsta0a1a3cqa2注意：表头(a0)和表尾(a3)结点的特殊性找前驱和后继结点∧a0a1a2firstsizefirstsize

@SuppressWarnings("unchecked")

privateCLinkedList<T>superClone(){

try{

return

(CLinkedList<T>)super.clone();}catch(CloneNotSupportedExceptione){

throw

newInternalError(e);}}Objectclone()∧

publicObjectclone(){ CLinkedList<T>v=superClone();

if(v.first==null)//空表

return

v;

//复制this的链表，赋予v

v.first=newNode<>(first.data,null);

for(Node<T>p=first.next,q=v.first;p!=null;p=p.next,q=q.next)

q.next=newNode<>(p.data,null);

return

v; } }pfirsta0a1a2qv.firsta0a1a2Objectclone()∧∧∧∧pqpq

public

booleanequals(Objectobj){

if(this==obj)

return

true;

if(obj

instanceofCLinkedList<?>){ CLinkedList<?>rhd=(CLinkedList<?>)obj;

if(this.size!=rhd.size)

return

false;

for(Node<?>p=first,q=rhd.first;p!=null;p=p.next,q=q.next){

if(!p.data.equals(q.data))

return

false; }

return

true; }

return

false; }equalsrhd.first∧b0b1b2first∧a0a1a2pqpppqqqisEmpty:O(1)size:O(1)indexOf:主要操作是找后继结点和比较。位置0123n

-

1移动次数0123n

-

1比较次数1234n查找成功：最少0次，最多n

-

1次。等概率的平均：O(n)查找不成功：移动n

-

1次，比较n次，O(n)算法复杂性分析add:主要操作是找后继结点，O(n)remove:主要操作是找后继结点，O(n)get:主要操作是找后继结点，O(n)算法复杂性分析......01234......length-1顺序存储和链式存储的区别first∧顺序的get和set:O(1)随机存取；链式的get和set:O(n)顺序存取add和remove的时间复杂度都是O(n)，但：顺序的add、remove的主要操作是复制数据：listElem[i]=listElem[i+1]，需要读、写内存链式的add、remove的主要操作是找后继结点：

p

=

p.next，需要读内存,写内存，p可以优化为使用寄存器，但需要注意内存体系结构的影响顺序存储和链式存储的区别如果要逐一读取表中的所有数据：顺序存储：for+get链式存储:使用迭代器顺序存储需要一次申请内存，必要时申请更大的内存，适合能预知数据量的场合。链式存储只在需要时申请内存，不需要时释放内存，适合动态数据集(变化较大的数据集）但是，需要更多的存储空间(一个结点比一个数据元素占用更大的存储空间)。顺序存储和链式存储的区别add和remove需要对编号0做特殊处理，原因是编号为0的结点没有前驱结点，一种解决方案是增加1个冗余结点“头结点”，使编号为0的结点也有前驱结点。头结点firstfirsta0a1a2注意：头结点不存储数据，但也可以根据需要，存储特殊的数据加入头结点的目的是为了解决add和remove方法需要判断index为0的情形带头结点的单(向)链表∧∧public

classLinkedListWithfirstNode<T>implementsIlist<T>{

privateNode<T>first;

int

size; LinkedListWithfirstNode(){

first=newNode<>(null,null);//头结点 }

private

static

classNode<T>{ Tdata; Node<T>next; Node(Tdata,Node<T>next){

this.data=data;

this.next=next; } }带头结点的单(向)链表空表：first∧∧

publicTget(int

index){ rangCheck(index); Node<T>p=first.next;//注意：开始的位置

//index次

for(int

i=0;i<index;i++)

p=p.next;

return

p.data; }get

public

voidadd(int

index,Tx){//对比CLinkedList rangeCheckForAdd(index);

//找前驱结点 Node<T>p=first;

//注意：开始的位置

for(int

i=0;i<index;i++)

p=p.next;

p.next=newNode<>(x,p.next); ++size; }add

publicTremove(int

index){//对比CLinkedList rangeCheck(index); Node<T>p=first;

//找到index的前驱

for(int

i=0;i<index;i++)

p=p.next;//循环结束后，p引用待删除结点的前驱 Node<T>q=p.next;//q引用待删除结点

p.next=q.next;//将待删除结点从链表中移除 Tvalue=q.data;

q.data=null;//帮助GC

q.next=null; --size;

return

value; }removefirst

public

voidclear(){

//不断删除first引用结点的后继结点，直到剩下头结点

while(first.next!=null){ Node<T>q=first.next;//q引用待删除结点

first.next=q.next;//将q引用的结点从链表中移除

q.data=null;//帮助GC

q.next=null; }

size=0; }clear∧a0a1a2firstfirst形式一：带头结点的单(向)循环链表构造器：public

classCircularLinkedListWithfirstNode<T>implementsIlist<T>,Cloneable{

privateNode<T>first;

int

size; CircularLinkedListWithfirstNode(){

first=newNode<>(null,null);

first.next=first;//循环 }a0a1a2firstfirst如何实现遍历？开始结点：p=first.next结束条件：p!=first带头结点的单(向)循环链表a0a1a2tailtail形式二：如何实现遍历？开始结点：p=tail.next.next结束条件：p!=tail.next带头结点的单(向)循环链表课堂练习因为要求tail始终引用尾结点，如果删除的结点是尾结点就需要对此进行特殊处理，应该如何处理？a0a1a2tail一、作用：方便定位一个结点的前驱结点和后继结点二、结点的形式aifirstlasta2a1a0三、链表的形式size=3双向链表空表：first=nulllast=null双向链表a0只有1个结点：firstlast

private

static

classNode<T>{Tdata;Node<T>next;Node<T>prev;Node(Node<T>prev,Telement,Node<T>next){

this.data=element;

this.next=next;

this.prev=prev;}}课堂练习给出Node<T>的定义：aipublic

classDoublelyLinkedList<T>implementsIlist<T>,Iterable<T>{ Node<T>first; Node<T>last;

int

size;…}课堂练习给出DoublelyLinkedList的定义：s.next=p.next;s.prev=p;

p.next=s;