顺序表:
顺序表是用一组地址连续的存储单元来保存数据的，使用之前必须指定其长度，一但内存分配，不可动态改变大小。所以它具有随机存取，查找快速的特点，但是做插入或删除动作是，需要移动大量元素，效率较低。
- 长度固定，必须在分配内存之前确定数组的长度。
- 存储空间连续，即允许元素的随机访问。
- 存储密度大，内存中存储的全部是数据元素。
- 要访问特定元素，可以使用索引访问，时间复杂度为 O(1)。
- 要想在顺序表中插入或删除一个元素，都涉及到之后所有元素的移动，因此时间复杂度为 O(n)。
- 顺序表实现主要是是使用数组的扩容实现的，System.arraycopy（）
链表 :
链表，是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。每个数据结点单元有两部分组成，一个是数据域，存储数据值；另一个是指针域，指向下一个数据单元。当多个结点通过指针指向，关联起来，就形成了一个链，即链表（java没有指针概念，指针是指对象，即结点）。
链表可分为单链表、双链表、循环链表。
单链表就是沿着单方向的链表。例如a->b->c->d… 只能顺序往下连接下去，即只可以从A往下找元素，但是反之则不行。
对比：
链表是线性表的链式存储结构，它相比于顺序表，在插入和删除元素时，效率要高很多。
数组线性表类ArrayList 和链表类LinkedList 是实现List接口的两个具体类。ArrayList 数组储存元素，这个数组是动态创建的。如果元素个数超过了数组的容量，就创建一个更大的新数组，并将当前所有元素都复制到新数组中。LinkedList在一个链表中储存元素。
如果需要通过下标来随机访问元素，但是除了在末尾处之外，不能在其他位置插入或删除元素，那么使用ArrayList更高效。
需要在线性表任意位置上插入或删除元素，就应该选择LinkedList。线性表的大小可动态增大或减小，但数组一旦被创建，大小就是固定的。如不需要在线性表中插入或删除元素，那么数组是效率最高的数据结构。
ArrayList是一个实现List接口的大小可变的数组，向ArrayList中添加元素，容量自动增大，但不能自动减小，需使用trimToSize（）将数组容量减小到线性表的大小
若要提取元素或者在线性表的尾部插入和删除元素，ArrayList的效率比较高，若要在线性表任意位置上插入和删除元素，LinkedList效率较高。
链表基本算法
插入结点
假设要在单链表的a结点和b结点之间插入一个值为x的新结点。
如下图所示，指针s指向一个值为x的结点，为了插入s。
首先让s的next指针指向b，即s->next = p->next;
然后，让a的next指针指向s，即p->next = s;
删除结点
假设要删除单链表中的b结点。
首先，找到b结点前面的结点a。
如下图所示，p指针指向a结点。b的下一个结点就是p->next->next。
所以，只要让p的next指针跳过b结点，指向b的下一个结点就OK了，即p->next = p->next->next;
链表代码实现
1 package structure.link; 2 /** 3 * 4 * Description: 定义结点 5 * @author 6 */ 7 public class Node { 8 protected Node next;// 指针 9 protected int data;// 数据数值10 11 public Node(int data) {12 this.data = data;13 }14 15 // 显示16 public void display() {17 System.out.print(data + " ");18 }19 20 } 1 package structure.link; 2 /** 3 * 4 * Description: LinkList方法 5 * @author 6 */ 7 public class LinkList { 8 private Node first; // 头节点 9 private int pos = 0; // 节点位置 10 11 public LinkList() { 12 this.first = null; 13 14 } 15 16 // 插入一个头节点 17 public void addFirstNode(int data) { 18 Node node = new Node(data); 19 node.next = first; 20 first = node; 21 } 22 23 // 删除一个头结点,并返回头结点 24 public Node deleteFirstNode() { 25 Node tempNode = first; 26 first = tempNode.next; 27 return tempNode; 28 } 29 30 // 在任意位置插入节点 在index的后面插入 (插入在原链表index之前) 31 public void add(int index, int data) { 32 Node node = new Node(data); 33 Node current = first; // 现在的 34 Node previous = first; // 之前的（现在的前一个） 35 36 while (index != pos++) { 37 previous = current; 38 current = current.next; 39 } 40 node.next = current; 41 previous.next = node; 42 pos = 0; 43 } 44 45 // 删除任意位置的节点 46 public Node deleteByPos(int index) { 47 Node current = first; // 现在的 48 Node previous = first; // 之前的（现在的前一个） 49 while (index != pos++) { 50 if (current.next == null) { 51 break; 52 } 53 previous = current; 54 current = current.next; 55 } 56 if (current == previous) { 57 first = first.next; 58 } else { 59 previous.next = current.next; 60 pos = 0; 61 } 62 return current; 63 } 64 65 // 根据节点的data删除节点(仅仅删除第一个) 66 public Node deleteByData(int data) { 67 Node current = first; 68 Node previous = first; 69 while (data != current.data) { 70 if (current.next == null) { 71 break; 72 } 73 previous = current; 74 current = current.next; 75 } 76 if (current.data == data) { 77 first = first.next; 78 } else { 79 previous.next = current.next; 80 } 81 return current; 82 } 83 84 // 显示出所有的节点信息 85 public void displayAllNodes() { 86 Node current = first; 87 while (current != null) { 88 current.display(); 89 current = current.next; 90 } 91 System.out.println(); 92 } 93 94 // 根据位置查找节点信息 95 public Node findByPos(int index) { 96 Node current = first; 97 while (index != pos++) { 98 current = current.next; 99 }100 return current;101 }102 103 // 根据数据查找节点信息104 public Node findByData(int data) {105 Node current = first;106 while (data != current.data) {107 if (current.next == null)108 break;109 current = current.next;110 }111 return current;112 113 }114 115 }