线性表定义：
由零个或多个数据元素组成的有限序列。若元素存在多个，则第一个元素无前驱，最后一个无后继，其他元素都有且只有一个前驱和后继。线性表有两种物理存储结构：顺序存储结构和链式存储结构(顺序表和链表)。
我们先来研究下顺序表
顺序表定义：
是用一段地址连续的存储单元依次存储线性表的数据元素。
代码如下：
publicclassArrayList{
privateObject[]array=newObject[];//定义数组
privateintsize;//数组中元素的个数
}
是不是感觉很熟悉呢，其实，数组就是顺序表。接下来我们研究下怎么使用它。
代码如下：
publicclassArrayListT{
privatestaticObject[]array=newObject[10];//创建数组
privateintsize;//定义数组里元素的个数
//添加元素到表中(不指定位置)
publicbooleanadd(intvalue){
array[size++]=value;//这里也可以写成array[size]=value;size++;
returntrue;
}
//添加元素到指定位置
publicbooleanadd(intindex,Objectvalue){
if(size=array.length){//如果元素个数大于数组的长度
array=Arrays.copyOf(array,size+size1);//数组扩容1.5倍1是二进制中的移位，相当于除以2
}if(size==index){
array[size]=value;
}else{
//元素添加后元素后面的都要往后移一位
System.arraycopy(array,index,array,index+1,size-index);
array[index]=value;
}
size++;//添加元素后元素个数+1
returntrue;
}
//删除元素
publicbooleanremove(Tvalue){
for(inti=0;isize;i++){
if(value.equals(array[i])){
remove(i);
returntrue;
}
}
returnfalse;
}
//删除某个位置上的元素
publicvoidremove(intindex){
if(index!=--size){
//注意这里是将要删掉的元素覆盖
System.arraycopy(array,index+1,array,index,size-index);
}array[size]=null;//删除元素其实就是赋值给null，GC会回收。
}
//测试
publicstaticvoidmain(String[]args){
ArrayListTarr=newArrayList();
arr.add(3);
arr.add(4);
arr.add(5);
for(Objects:array){
System.out.println(s);
}
}
}
以上就是顺序表的一些简单实现，下面我们来看一下链表。链表分为单链表和双向链表，它们俩的实现原理相似，Java类库中的LinkedList就是双链表所实现的。
定义：链表（Linkedlist）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间。
单链表包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。
单链表代码定义：
publicclassSinglyLinkedListT{
privatestaticclassNodeT{
privateTvalue=null;//数据域
privateNodeTnext=null;//指针域(下一个结点的引用)
}
privateintsize=0;//结点个数
privateNodeThead=null;//定义头结点
privateNodeTtail=null;//定义尾结点
}
对其进行增删改查：
publicclassSinglyLinkedListT{
//创建结点类
privatestaticclassNodeT{
privateTvalue=null;//数据域
privateNodeTnext=null;//指针域(返回指向下一个Node的引用)
publicNode(Tvalue){
this.value=value;
}
}
privatestaticintsize=0;//结点个数
privateNodeThead=null;//定义头结点
privateNodeTtail=null;//定义尾结点
//添加元素方法(尾插入)
publicvoidadd(Tvalue){
if(head==null){//如果头结点为空
head=newNodeT(value);//头结点指向新的结点
tail=head;//尾结点也指向这个新结点
return;
}
tail.next=newNodeT(value);
tail=tail.next;
size++;
}
//添加元素方法（头插入）
publicvoidinsertBeforeHead(Tvalue){
if(head==null){
head=newNodeT(value);
tail=head;
size++;
}
NodeTnode=newNodeT(value);
node.next=head;
head=node;
size++;
}
//指定位置前增加
publicvoidinsert(intindex,Tvalue){
if(index=size
tail==null)
add(value);
elseif(index=0
head==null)
insertBeforeHead(value);
else{
NodeTcur=head;
inti=0;
while(i++index-1){//在指定位置后增加则将index-1改为indexcur=cur.next;
}
NodeTtemp=newNodeT(value);
temp.next=cur.next;
cur.next=temp;
size++;
}
}
//遍历
publicStringtoString(){
StringBuildersb=newStringBuilder();
NodeTnode=head;
while(node!=null){
sb.append(node.value).append(",");
node=node.next;
}
returnsb.toString();
}
//根据index删除元素，利用while找出index所指的结点
publicvoiddelete(intindex){
if(index=size)return;
if(index0)return;
if(index==0){
head=head.next;
size--;
if(size=1)tail=head;
return;
}
inti=0;
NodeTcur=head;
while(i++index-1){
cur=cur.next;
}
NodeTtemp=cur.next;
if(temp==tail)tail=cur;
cur.next=temp.next;
size--;
}
//删除指定的元素
publicvoiddelete(Tobj){
if(head==null)return;
if(head.value==obj){delete(0);return;}
NodeTpre=head,cur=head.next;
while(cur.value!=obj){
pre=cur;
cur=cur.next;
}
if(cur!=null){
if(cur==tail)tail=pre;
pre.next=cur.next;
size--;
}
}
//测试
publicstaticvoidmain(String[]args){
SinglyLinkedListlinkedlist=newSinglyLinkedList();
linkedlist.add("a1");
linkedlist.add("a2");
linkedlist.add("a3");
System.out.println(size);
linkedlist.insert(1,"haha");
System.out.println(linkedlist.toString());
}
}
总结：LinkedList是由双向链表实现的，对于随机访问get和set，ArrayList(顺序表)优于LinkedList，因为LinkedList要移动指针。对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
赞赏