单向链表与顺序表的区别在于单向链表的底层数据结构是节点块，而顺序表的底层数据结构是数组。节点块中除了保存该节点对应的数据之外，还保存这下一个节点的对象地址。这样整个结构就像一条链子，称之为“链表”
我们可以推理出单向链表和顺序表这两种数据结构特性对其本身操作的影响：
1、对读和改的影响：对于底层为数组的顺序表来说，读取(改写)数据是通过arr[n]的方式。而对于链表来说，操作第n个节点的数据必须要从第0个节点开始获取下一个节点的对象地址，直到第n个，如果运气不好要获取最后一个节点的数据，甚至要遍历整个链表所有的数据，其效率可想而知。
2、对插入的影响：对于底层为数组的顺序表来说，如果从首部或者中间位置插入一个数据，则其后的数据的物理内存地址全部都要往后移动一个单位，因为数组本身便是一连串的数据集合。而对于链表来说，如果要插入数据只需要对应位置前一位的对象地址以及在插入节点中加上后一位节点的对象地址即可。
下面我们通过代码的方式来实现我们自己的单向链表，我们首先先定义List接口：
1 packagecom.chen.arithmetic_test.list_test;2
3 /**
4 * Created by ChenMP on 2017/7/3.5 */
6 public interfaceList {7 //获得长度
8 public intsize();9 //插入元素
10 public boolean insert(int index, Object o) throwsException;11 //新增元素
12 public boolean add(Object o) throwsException;13 //删除元素
14 public boolean remove(int index) throwsException;15 //获取元素
16 public Object get(int index) throwsException;17 //判断线性表是否为空
18 public booleanisEmpty();19 }
编写节点类Node：
1 packagecom.chen.arithmetic_test.list_test;2
3 /**
4 * Created by ChenMP on 2017/7/4.5 */
6 public classNode {7
8 private Object nodeData; //当前节点数据
9 private Node nextNode; //保存下一个节点
10
11 publicNode() {12 super();13 }14
15 publicNode(Object nodeData) {16 this.nodeData =nodeData;17 }18
19 publicObject getNodeData() {20 returnnodeData;21 }22
23 public voidsetNodeData(Object nodeData) {24 this.nodeData =nodeData;25 }26
27 publicNode getNextNode() {28 returnnextNode;29 }30
31 public voidsetNextNode(Node nextNode) {32 this.nextNode =nextNode;33 }34 }
编写LinkList的实现类：
1 packagecom.chen.arithmetic_test.list_test;2
3 /**
4 * Created by ChenMP on 2017/7/4.5 */
6 public class LinkList implementsList {7 private Node fristNode;//开始节点
8 private Node lastNode;//结束节点
9 private int size;//List长度
10 private boolean isFixed;//是否限定List长度
11 private int fixedLength;//List定长
12
13 publicLinkList() {14 this.size = 0;15 this.fristNode = null;//第一次成功插入时定义
16 this.lastNode = null;17 this.isFixed = false;//不限定List长度
18 this.fixedLength = -1;//不限定长度
19 }20
21 public LinkList(intlength) {22 this.fristNode = null;//第一次成功插入时定义
23 this.lastNode = null;24 this.size = 0;25 this.isFixed = true;//限定List长度
26 this.fixedLength = length;//设置限定长度
27 }28
29 @Override30 public intsize() {31 return this.size;32 }33
34 @Override35 public boolean insert(int index, Object o) throwsException {36 if(index >size)37 throw new Exception("IndexOutOfBoundsException");38
39 if (index == size && this.isFixed && size>=this.fixedLength)40 throw new Exception("IndexOutOfBoundsException");41
42 Node previousNode = null; //遍历节点，用于存放更新节点的前一个节点
43 Node currentNode = this.fristNode; //遍历节点，用于存放当前节点
44 for (int i=1; i<=index; i++) {45 if (null == currentNode) //插入节点前有空节点
46 throw new Exception("IndexOutOfBoundsException");47
48 previousNode =currentNode;49 currentNode =previousNode.getNextNode();50 }51
52 if (null == currentNode) { //把节点插入到最后
53 currentNode = newNode(o);54
55 if (null != previousNode) { //fristNode不为空
56 previousNode.setNextNode(currentNode);57 } else { //fristNode不为空，更新fristNode
58 this.fristNode =currentNode;59 }60
61 this.lastNode =currentNode;62 size++;63 } else { //节点不为空，取代原节点数据
64 currentNode.setNodeData(o);65 }66
67 return true;68 }69
70 @Override71 public boolean add(Object o) throwsException {72 if (this.isFixed && size ==fixedLength)73 throw new Exception("IndexOutOfBoundsException");74
75 Node currentNode = newNode(o);76 if (0 == size) {//List中插入第一个元素
77 this.fristNode =currentNode;78 this.lastNode =currentNode;79 size++;80 } else{81 this.lastNode.setNextNode(currentNode);82 this.lastNode =currentNode;83 size++;84 }85
86 return true;87 }88
89 @Override90 public boolean remove(int index) throwsException {91 if(index < 0 || index >=size)92 throw new Exception("IndexOutOfBoundsException");93
94 Node previousNode = null; //遍历节点，用于存放删除节点的前一个节点
95 Node currentNode = this.fristNode; //遍历节点，用于存放删除节点
96 for (int i=1; i<=index; i++) {97 if (null == currentNode) //删除节点前有空节点
98 throw new Exception("IndexOutOfBoundsException");99
100 previousNode =currentNode;101 currentNode =previousNode.getNextNode();102 }103
104 previousNode.setNextNode(currentNode.getNextNode());105 currentNode = null;106 size--;107
108 return true;109 }110
111 @Override112 public Object get(int index) throwsException {113 if(index < 0 || index >=size)114 throw new Exception("IndexOutOfBoundsException");115
116 Node currentNode = this.fristNode; //遍历节点，用于存放查询节点
117 for (int i=1; i<=index; i++) {118 if (null == currentNode) //删除节点前有空节点
119 throw new Exception("IndexOutOfBoundsException");120
121 currentNode =currentNode.getNextNode();122 }123
124 returncurrentNode.getNodeData();125 }126
127 @Override128 public booleanisEmpty() {129 return this.size>0?false:true;130 }131
132 @Override133 publicString toString() {134 StringBuilder sb = newStringBuilder();135 Node currentNode = this.fristNode; //遍历节点，用于存放查询节点
136
137 while (null !=currentNode) {138 sb.append(currentNode.getNodeData()).append(",");139 currentNode =currentNode.getNextNode();140 }141 returnsb.toString();142 }143 }
编写测试代码：
1 packagecom.chen.arithmetic_test.list_test;2
3 importjava.util.LinkedList;4
5 /**
6 * Created by ChenMP on 2017/7/3.7 */
8 public classTestList {9
10 public static void main(String[] args) throwsException {11 List list = new LinkList(3);12 list.insert(0,0);13 //list.add(0);
14 list.add(1);15 list.add(2);16 //list.add(3);
17 System.out.print("测试定长list： " + list.toString() + "|| list长度为： " +list.size());18
19 System.out.println();20 List list2 = newSequenceList();21 list2.add(0);22 list2.add(1);23 list2.add(2);24 list2.add(3);25 System.out.print("测试不定长list： " + list2.toString() + "|| list长度为： " +list2.size());26
27
28 }29 }
通过我们自己实现的代码，相信我们再去看JDK中LinkList源码的时候一定能够很轻松的理解其原理实现。怀挺！！