1、单链表和数组的区别
数组：数组的存储空间是连续的，需要事先申请空间确定大小，通过下标查找数据，所以查找速度快，但是增加和删除速度慢
链表：离散存储，不需要事先确定大小，通过头指针加遍历查找数据，查找数据慢，但是增加和删除速度快
【举例】
把内存空间看成一个教室，同学代表数据
【数组】
- 申请空间
int[] seat = new int[5]表示我从教室（内存空间）申请第一排座位（数组），座位按1，2，3.....的顺序标记，seat[1]表示坐在第一个位置的同学（数据），同学只能坐第一排。
-
存储数据
-
来了第一个同学（
1）他坐在了第1个位置（int[0] = 1)， -
来了第二个同学（
4) 他屁事多，他要做第6个位置（int[5] = 4），此时老师骂人了，那里不让做（数组越界异常),无奈，第二个同学选择了第4个位置(int[3] = 4) -
接下来五个同学都坐满了
-
-
查找
查找数据就不用说了吧，对号入座，老师很快就可以按座位号（下标）叫第几个同学回答问题
- 删除
这个就有点麻烦了，第二个同学不认真，老师叫他滚出去，这时候座位号应该减少一个，那么第三个同学就要往左移一格(int[1] = int[2]),后面依次往左移一格，最后int[4]空出来了,所以应该把最后一个座位还给教室（归还给内存），所以说这个还是比较麻烦的（ps：我是按照c语言思想讲这里的，只学过Java的同学可能难以接受）需要移动座位，很麻烦
【链表】
-
申请空间
链表不需要事先申请空间
-
添加数据（这里讲的是有头节点的链表，方便写代码）
-
老师先让班长（头节点）找好位置（可用内存），老师只知道班长的座位号（地址），这时候班长找好了位置，告诉了老师，老师对班长说：吩咐下去，叫每一个同学记好在他们后一个进教室的同学的座位（地址）
-
第一个同学M进来，按照自己的心情找了个空座位（可用内存），班长（头节点）记录了他的座位
-
第二同学N进来，也按照自己的心情找了个空座位（可用内存），第一个同学记录了第二个同学的座位
......以此类推
-
-
查找数据（每个同学只知道他们下一个进来的同学）
-
老师对班长（头节点）说：点名，第3个进来的同学回答问题
-
班长说：我后面进来的是同学M，找到了M
-
M说：我后面进来的是同学N，找到了N
-
N说：我后面进来的同学是X，找到了第三个进来的同学X
-
老师说：就是你了，同学X回答问题
-
-
删除数据
- 第2个进教室的同学调皮捣蛋，老师让他滚出去
- 重复查找数据步骤，班长——>M——>N(找到第二进来的同学)
- 让N滚动，此时，在M后进入的同学就是X了，只要记住座位号就可以了
- 不要移动座位，很方便
-
插入数据
- 同学N改过自新了，重新申请做在第二个位置
- 重复查找步骤，班长——>M（找到第一个进来的同学）
- M记住他的下一个同学是N
- N记住他的下一个同学是X
- 不要移动座位，很方便
2、代码实现
数据结构这种东西，太玄学了，我当初学的c语言版本，学了好久就是不明白，突然有一天就脑袋就开窍了，估计是菩萨保佑
现在来用java代码实现
1、定义链表
public class SingleLinkedList<T>{
//记录链表长度
private int size;
//头节点，不存数据，方便实现增删代码的
private Node head;
/**
* 成员内部类，节点类，相当于例子中的同学和座位号的集合题
* 我觉得这个类不应该暴露给外部
*/
private class Node{
private Node next;
private T t;
Node(Node next,T t){
this.next = next;
this.t = t;
}
Node(T t){
this(null,t);
}
Node(){
Node next = null;
t = null;
}
}
//链表构造方法
public SingleLinkedList(){
//初始化头节点，不存数据，方便实现增删代码的
this.head = new Node();
this.size = 0;
}
/**
* 此处省略了方法，单独拿出来给大家讲解
* .........
*/
}
2、获取长度
//获取长度
public int getSize(){
return size;
}
3、添加节点
//添加节点
public void add(T t){
Node newNode = new Node(t);
Node temp = this.head;
while(temp.next != null){
temp = temp.next;
}
temp.next = newNode;
size++;
}
4、插入节点
//插入节点，先判断节点是否合法
public void insert(T t,int index){
if(index <= 0 || index > this.size){
throw new RuntimeException("index参数不合法");
}
Node newNode = new Node(t);
Node temp = this.head;
//要明白到底循环几次
for (int i = 1; i < index; i++) {
temp = temp.next;
}
//注意顺序
newNode.next = temp.next;
temp.next = newNode;
size++;
}
5、取节点数据
//取节点数据
public T getValue(int index){
if(index <= 0 || index > this.size){
throw new RuntimeException("index参数不合法");
}
Node temp = this.head;
//要明白到底循环几次
for (int i = 0; i < index; i++) {
temp = temp.next;
}
return temp.t;
}
6、删除节点
//删除节点
public void delete(int index){
if(index <= 0 || index > this.size){
throw new RuntimeException("index参数不合法");
}
Node temp = this.head;
//要明白到底循环几次
for (int i = 1; i < index; i++) {
temp = temp.next;
}
temp.next = temp.next.next;
//java垃圾回收机制gc自动回收内存
size--;
}
7、遍历
//遍历
public void showData(){
Node temp = this.head;
//要明白到底循环几次
for (int i = 0; i < this.size; i++) {
temp = temp.next;
System.out.print("["+temp.t+"]-->");
}
}
【总结】
个人代码水平有限，仅作参考