线性结构是最简单，也是最常用的数据结构之一。线性结构的特点是：在数据元素的有限集中，除第一个元素无直接前驱，最后一个元素无直接后继以外，每个数据元素有且仅有一个直接前驱元素和一个直接后续元素。
数组
/***二次封装属于我们自己的数组的准备工作*/publicclassArray{privateint[]data;privateintsize;publicArray(intcapacity){data=newint[capacity];size=0;}//无参构造函数，默认数组的容量是10publicArray(){this(10);}publicintgetSize(){returnsize;}publicintgetCapacity(){returndata.length;}publicbooleanisEmpty(){returnsize==0;}
OverridepublicStringtoString(){StringBuilderbuilder=newStringBuilder();builder.append(String.format("Arraysize=%d,capacity=%d\n",size,data.length));builder.append("[");for(inti=0;isize;i++){builder.append(data);if(i!=size-1){builder.append(",");}}builder.append("]");returnbuilder.toString();}}添加元素//在所有元素后添加新元素publicvoidaddLast(inte){//要先判断是否有空间来容纳新元素/*if(size==data.length){thrownewIllegalArgumentException("AddLastfailed,arrayisfull");}data[size]=e;size++;*/add(size,e);}//在所有元素前添加新元素publicvoidaddFirst(inte){add(0,e);}//在index位置插入元素publicvoidadd(intindex,inte){if(size==data.length){thrownewIllegalArgumentException("Addfailed,arrayisfull");}if(index0
indexsize){thrownewIllegalArgumentException("AddFailed,0=index=sizeisrequired");}//index位置后的元素向右移动for(inti=size;iindex;i--){data=data[i-1];}data[index]=e;size++;}查询元素
//获取index位置的元素publicintget(intindex){if(index0
index=size){thrownewIllegalArgumentException("Getfailed,indexisillegal");}returndata[index];}
//查找数组中是否有元素e,有就返回下标，没有就返回-1publicbooleancontains(inte){for(inti=0;isize;i++){if(data==e){returntrue;}}returnfalse;}//查找数组中元素e所在索引publicintfind(inte){for(inti=0;isize;i++){if(data==e){returni;}}return-1;}修改元素
//设置index位置元素值为epublicvoidset(intindex,inte){if(index0
index=size){thrownewIllegalArgumentException("Getfailed,indexisillegal");}data[index]=e;}删除元素
//删除指定位置元素publicintremove(intindex){if(size==0){thrownewIllegalArgumentException("Removefailed,arrayisempty");}if(index0
index=size){thrownewIllegalArgumentException("Removefailed,indexisillegal");}intret=data[index];for(inti=index+1;isize;i++){data[i-1]=data;}size--;returnret;}publicintremoveFirst(){returnremove(0);}publicintremoveLast(){returnremove(size-1);}publicvoidremoveElement(inte){intindex=find(e);if(index!=-1){remove(index);}}动态数组调整数组大小思路
准备一个新数组，长度是原来数组的2倍
将原来数组中的元素复制到新数组中
将data指向newData,完成扩容
完成扩容，capacity是原来的2倍,size不变，数组中数据不变
代码//动态调整数组大小privatevoidresize(intnewCapacity){E[]newData=(E[])newObject[newCapacity];for(inti=0;isize;i++){newData=data;}data=newData;}添加元素
//在index位置插入元素publicvoidadd(intindex,Ee){/*if(size==data.length){thrownewIllegalArgumentException("Addfailed,arrayisfull");}*/if(size==data.length){resize(data.length*2);}if(index0
indexsize){thrownewIllegalArgumentException("AddFailed,0=index=sizeisrequired");}//index位置后的元素向右移动for(inti=size;iindex;i--){data=data[i-1];}data[index]=e;size++;}删除元素
//删除指定位置元素publicintremove(intindex){/*if(size==0){thrownewIllegalArgumentException("Removefailed,arrayisempty");}*/if(size==data.length/2){resize(data.length/2);}if(index0
index=size){thrownewIllegalArgumentException("Removefailed,indexisillegal");}Eret=data[index];for(inti=index+1;isize;i++){data[i-1]=data;}size--;data[size]=null;//loiteringobjectsreturnret;}addLast()时间复杂度分析
假设capacity=n，（n+1）次进行addLast操作，会触发resize，总共进行（2*n+1）次基本操作。
平均情况下，每次addLast操作，进行2次基本操作。这样均摊计算，时间复杂度是O(1)。所以addLast的均摊复杂度是O(1)。同理，removeLast的均摊复杂度是O(1)。
复杂度震荡capcity为n，此时size=n：
进行addLast()操作，由于需要resize()，时间复杂度为O(n)；
再进行removeLast()操作，由于需要resize()，时间复杂度为O(n)；
再进行addLast()操作，由于需要resize()，时间复杂度为O(n)
...
这就是复杂度震荡。
解决复杂度震荡的方法：lazy，即在size==capacity/4，才将capacity减半。
//删除指定位置元素publicintremove(intindex){/*if(size==0){thrownewIllegalArgumentException("Removefailed,arrayisempty");}*//*if(size==data.length/2){resize(data.length/2);}*/if(size==data.length/4data.length/2!=0){resize(data.length/2);}if(index0
index=size){thrownewIllegalArgumentException("Removefailed,indexisillegal");}Eret=data[index];for(inti=index+1;isize;i++){data[i-1]=data;}size--;//data[size]=null;//loiteringobjects,使用泛型时，进行此操作returnret;}时间复杂度分析操作时间复杂度添加操作平均时间复杂度：O(n)addLast(e)O(1)addFirst(e)O(n)add(index)O(n)删除操作平均时间复杂度：O(n)removeLast(e)O(1)removeFirst(e)O(n)remove(index,e)O(n)修改操作set(index,e)O(1)查找操作get(index)O(1)contains(e)O(n)find(e)O(n)链表链表结点
/***链表结点*/publicclassNodeE{publicEe;publicNodenext;publicNode(Ee,Nodenext){this.e=e;this.next=next;}publicNode(Ee){this(e,null);}publicNode(){this(null,null);}
OverridepublicStringtoString(){returne.toString();}}publicclassLinkedListE{privateNodehead;privateintsize;publicLinkedList(){head=null;size=0;}publicbooleanisEmpty(){returnsize==0;}publicintgetSize(){returnsize;}
OverridepublicStringtoString(){StringBuilderbuilder=newStringBuilder();Nodecur=dummyHead.next;while(cur!=null){builder.append(cur+"-");cur=cur.next;}builder.append("NULL");returnbuilder.toString();}}插入元素在链表头插入元素
//在链表头添加元素publicvoidaddFirst(Ee){Nodenode=newNode(e);node.next=head;head=node;size++;}在链表中间插入元素
//在链表index位置[从0开始]插入元素//这项操作在链表中并不常用publicvoidadd(intindex,Ee){if(index0
index=size){thrownewIllegalArgumentException("Indexisillegal");}if(index==0){addFirst(e);}else{Nodeprev=head;for(inti=0;iindex-1;i++){prev=prev.next;}Nodenode=newNode(e);node.next=prev.next;prev.next=node;size++;}}虚拟头结点
publicLinkedList(){dummyHead=newNode(null,null);size=0;}//在链表index位置[从0开始]插入元素//这项操作在链表中并不常用publicvoidadd(intindex,Ee){if(index0
indexsize){thrownewIllegalArgumentException("Indexisillegal");}Nodeprev=dummyHead;for(inti=0;iindex;i++){prev=prev.next;}Nodenode=newNode(e);node.next=prev.next;prev.next=node;size++;}//在链表头添加元素publicvoidaddFirst(Ee){add(0,e);}publicvoidaddLast(Ee){add(size,e);}查询元素
//获取链表index位置[从0开始]元素//这项操作在链表中并不常用publicEget(intindex){if(index0
index=size){thrownewIllegalArgumentException("Indexisillegal");}Nodecur=dummyHead.next;for(inti=0;iindex;i++){cur=cur.next;}return(E)cur.e;}publicEgetFirst(){returnget(0);}publicEgetLast(){returnget(size-1);}
//查找链表中是否有元素epublicbooleancontains(Ee){Nodecur=dummyHead.next;while(cur!=null){if(cur.e.equals(e)){returntrue;}cur=cur.next;}returnfalse;}修改元素
//修改链表index位置[从0开始]元素publicvoidset(intindex,Ee){if(index0
index=size){thrownewIllegalArgumentException("Indexisillegal");}Nodecur=dummyHead.next;for(inti=0;iindex;i++){cur=cur.next;}cur.e=e;}删除元素
//删除链表index位置[从0开始]元素publicEremove(intindex){if(index0
index=size){thrownewIllegalArgumentException("Indexisillegal");}Nodeprev=dummyHead;for(inti=0;iindex;i++){prev=prev.next;}NodedelNode=prev.next;prev.next=delNode.next;delNode.next=null;size--;return(E)delNode.e;}publicEremoveFirst(){returnremove(0);}publicEremoveLast(){returnremove(size-1);}时间复杂度分析操作时间复杂度添加操作平均时间复杂度：O(n)addlast()O(n)addFirst()O(1)add(index,e)O(n/2)=O(n)删除操作平均时间复杂度：O(n)removeLast()O(n)removeFirst()O(1)remove(index,e)O(n/2)=O(n)修改操作O(n)set(index,e)O(n)查找操作O(n)get(index)O(n)contains(e)O(n)预览时标签不可点收录于话题#个上一篇下一篇