从数据结构上说，数组的内存空间是连续的，我们创建数组的时候系统就会为我们开辟固定数目的内存空间，如果内存不足，就会创建失败，例如创建数组的两种方式： int[] a=new int[3]; int[] b=new int[]{1,2,3}; 可以看到我们创建数组的时候已经指定了数组的大小，且不能动态更改数组的大小，是因为创建时候已经分配了连续的固定内存空间，每个元素占用两个字节，这样我们就可以通过连续的内存，去访问数组的元素；
链表的内存分配是动态的，链表的元素占用的空间包含元素占用的空间，还有指向上一个或者下一个元素的指针（双链表，单链表）；
这样我们可以得出各自的优缺点：
数组链表的优缺点： 数组占用空间小，链表元素还要包涵上一元素和下一个元素的的信息 数组的访问速度快，因为内存是连续的 数组内部元素可以随机访问，而链表依赖于上一个元素的信息
链表的插入删除操作由于数组，因为内存不连续，只需要更改元素的前后节点信息就行了，并不需要更改元素内存地址，而数组的连续内存想要插入和删除的话就要移动所有的内存地址 链表的内存利用率高于数组，链表内存是分散的一个元素占用一块空间，数组元素少于内存空间的话，会有部分的内存浪费； 链表的扩展性强，数组的创建完成内存大小就确定了，满了就没法扩展只能再次创建新的数组，而链表可以随意的增加扩展
效率：数组查询效率高，链表增，删效率高
下面是个单链表的实现：
public class LinkList<T> { public class Node{ //定义节点 private T data; private Node next; public Node(){ } public Node(T data,Node next){ this.data=data; this.next=next; } } private Node header;//头节点 private Node tail;//尾节点 private int size;//链表大小 //构造函数初始化数据 public LinkList(){ header=null; tail=null; } public LinkList(T element){ header=new Node(element,null); tail=header; size++; } //采用尾插法为链表添加新节点 private void add(T element) { if(header==null){ header=new Node(element,null); tail=header; }else{ Node newNode=new Node(element,null); tail.next=newNode; tail=newNode; } size++; } //在index位置插入节点element public void insert(T element,int index){ if(index<0||index>size){ throw new IndexOutOfBoundsException("线性表索引越界"); } if(header==null){ add(element); }else{ if(index==0){ addAtHeader(element); }else{ Node prev=getNodeByIndex(index-1); prev.next=new Node(element,prev.next); size++; } } } //采用头插法为链表添加新节点 private void addAtHeader(T element){ header=new Node(element,header); if(tail==null){ tail=header; } size++; } //返回指定位置index的节点 public T get(int index){ return getNodeByIndex(index).data; } private Node getNodeByIndex(int index) { if(index<0||index>size-1){ throw new IndexOutOfBoundsException("线性表索引越界"); } Node current=header; for(int i=0;i<size;i++,current=current.next){ if(i==index){ return current; } } return null; } //链表长度 public int length(){ return size; } //返回element在链表的位置，-1表示不存在 public int locate(T element){ Node current=header; for(int i=0;i<size;i++,current=current.next){ if(current.data==element){ return i; } } return -1; } //删除index位置的节点 public T delete(int index){ if(index<0||index>size-1){ throw new IndexOutOfBoundsException("线性表索引越界"); } Node del=null; if(index==0){ del=header; header=header.next; }else{ Node prev=getNodeByIndex(index-1); del=prev.next; prev.next=del.next; del.next=null; } size--; return del.data; } //从链表后面删除一个节点 public T remove(){ return delete(size-1); } //是否为空 public boolean empty(){ return size==0; } //清空链表 public void clear(){ header=null; tail=null; size=0; } public String toString(){ if(empty()){ return "[]"; }else{ StringBuilder sb=new StringBuilder("["); for(Node current=header;current!=null;current=current.next){ sb.append(current.data.toString()+", "); } int len=sb.length(); return sb.delete(len-2, len).append("]").toString(); } } public static void main(String[] args) { LinkList<String> list=new LinkList<String>(); list.insert("1", 0); list.add("2"); list.add("3"); System.out.println(list.toString()); list.insert("4", 1); System.out.println(list.toString()); list.delete(2); System.out.println(list.toString()); System.out.println("1在链表中的位置："+list.locate("1")); System.out.println("链表中索引2处的元素："+list.get(2)); } }