单链表是什么
【代码文件看末尾】
单链表是一种相对于线性表的一种存储方式，在线性表中我需要对我们的数据大小进行预先的评判，来给出我们的存储空间，这样会出现一个问题，我们无法预先确定数据的大小，如果我们的数据量比较小，但是默认开辟了很多空间，那么就造成了资源的浪费，那如果我们数据量很大而开辟空间不足，也不能满足我们的需求，而且对于线性表来说我们插入或者删除其中的元素会造成大量元素的移动，并且我们使用算法对线性表进行拓展空间的时候也会大量移动元素才能完成操作，所以相对的我们出现了链表的概念，什么是链表呢？
相对于线性表中存储的元素在物理地址中是连续的不同，我们的链表在屋里存储中是分散的，可能第一个元素在46号内存地址，第二个就在558号地址，为了使不同地址的元素之间能找到彼此，我们的每一个数据节点在存储数据的本身的情况下还需要存储下一个元素的指针，因为在java中不存在显示的指针，所以我们通过对象的应勇来访问下一个数据节点就行了。这样一环扣一环就形成了一个链条，也就是单链表
在单链表，我们需要首先构造一个Node类来表示每一个节点
每一个节点我们设计一个数据域(存储数据的属性)一个指针域(存储下一个对象)
class Node<dataType>{
private dataType nodeData；//构造数据域
private Node next；//指针，存储下一个数据节点的引用
}
这样我们就构造好了一个节点，为了规范引用，我们封装成一个JavaBean的样子，不直接操作属性，通过方法来操作。
class Node<dataType>{
private dataType nodeData；//构造数据域
private Node next；//指针，存储下一个数据节点的引用
public Node(dataType nodeData) //构造函数，新建一个节点可以没有下一个节点的指针但是必须要存数据吧~
this.nodeData = nodeData;
}
public Node getNext() {//获取下一个数据节点
return next;
}
public dataType getNodeData() {//获取当前节点存储的数据
return nodeData;
}
public void setNext(Node next) {//设置下一个节点
this.next=next;
}
public void setNodeData(dataType nodeData) {//设置当前节点的数据
this.nodeData=nodeData;
}
}
这样我们的一个Node节点就构造好了，我们指定了泛型，可以存储我们指定的数据~
有了节点我们就可以构造链表了，对于链表我们有两个基本的玩意儿就是头节点，因为我们需要一个头节点作为整个链表的开端，每次操作就可以从头节点开始，还需一个属性size，来存储我们链表的大小~
所以开始构造
public class LinkList<dataType> {
private int size;//链表长度属性
private Node head = new Node(null);//头节点，数据域是空的，默认指针（下一个对象）也是（指向）空的
}
对于链表我们可以参考java.util包给我们提供的LinkedList的方法来，但是我们必须实现以下基本操作
1、初始化
new 关键字就已经初始化了~此处也不需要什么参数，默认构造函数就行
2、插入操作
方法add(节点的数据) 在链表末尾插入新元素(Node)
public void add(dataType value) {
Node<dataType> tmp = head;//使用一个临时变量存储head节点
while (tmp.getNext() != null) {//对临时节点进行移动操作
tmp = tmp.getNext();
}//直到移动到末尾，此时tmp为链表最后一个节点（最后一个节点没有指针，指向空，既引用的对象是NULL）
tmp.setNext(new Node<dataType>(value)); //为最后一个节点设置下一个节点
this.size++;//链表长度+1
}
方法add(链表位置,节点的数据) 为链表指定位置添加新节点
public void add(int index, dataType value) {
if (index < 0 || index > this.size) {//判断位置是否合法，既下标是否小于0，或者超出最链表的大小
throw new ArrayIndexOutOfBoundsException("插入的位置不合法");
} else {
int counter = -1;//设置一个counter存储当先节点的下标，因为第一个head不能算进去所以从-1开始计算
Node tmp = head;//使用后临时节点保存head
while (tmp != null) {//遍历链表
if (counter == index - 1) {//指定检查下标是否与当前下标吻合，因为是插入操作，我们必须要找到插入点的前一个节点，吧前一个节点的NEXT指向新节点，然后将新节点的next指向原来插入点新节点的下一个节点。
Node node = new Node<dataType>(value);//新建节点存储节点的数据
Node nextNode = tmp.getNext();//使用nextnode表示当前节点的下一个节点，既本来是插入点的下一个节点
tmp.setNext(node);//当前tmp节点就是插入点前的节点，设置插入点前的节点的下一个节点为我们new 的节点
node.setNext(nextNode);//为新节点设置下一个节点为下一个节点
this.size++;//链表长度+1
break;
}
tmp = tmp.getNext();//遍历时的操作
counter++;//遍历时的操作
}
}
}
方法addFirst(新节点的值)//在头节点后面插入新节点
public void addFirst(dataType value) {
Node tmp = head.getNext();//使用临时节点存储原来的第一个节点
head.setNext(new Node<dataType>(value));//设置新的第一个节点
head.getNext().setNext(tmp);//新节点的下一个节点为原来的第一个节点
this.size++;//长度+1
}
方法addLast(新节点的值)//在链表尾部增加新节点和无位置参的add一样
public void addLast(dataType value) {
Node<dataType> tmp = head;
while (tmp.getNext() != null) {
tmp = tmp.getNext();
}
tmp.setNext(new Node<dataType>(value));
this.size++;
}
3、数据查找
方法get(获取数据的位置)
public dataType get(int index) {
if (index < 0 || index > this.size - 1) {//判断位置是否合法
throw new ArrayIndexOutOfBoundsException("获取的位置不合法");
} else {
Node<dataType> tmp = head;
int counter = -1;
while (tmp != null) {//遍历链表
if (counter == index) {
return (dataType) tmp.getNodeData();//返回数据域就行了
}
tmp = tmp.getNext();
counter++;
}
}
return null;
}
方法getFirst()获取第一个节点的数据
public dataType getFirst() {
return (dataType) head.getNext().getNodeData();//只需要返回数据域就行了
}
方法getLast()获取最后一个节点的数据
public dataType getLast() {
Node tmp = head;
while (tmp.getNext() != null) {
tmp = tmp.getNext();
}
return (dataType) tmp.getNodeData();
}
4、删除操作
方法clear()清空操作，清空整个链表只需要吧头节点的下一个指向空就行了，后面的节点由于没有被引用就会被java的垃圾回收机制给清理了~java万岁不需要手动回收内存~
public void clear() {
head.setNext(null);
}
remove(指定位置)删除指定位置的元素
public dataType remove(int index) {
if (index < 0 || index > this.size - 1) {
throw new ArrayIndexOutOfBoundsException("删除的位置不合法");
} else {
int counter = -1;
Node tmp = head;
while (tmp != null) {
if (counter == index - 1) {
Node removeNode = tmp.getNext();
tmp.setNext(tmp.getNext().getNext());//将删除点的next指向下一个的下一个就相当于略过了下一个就行了
this.size--;//长度-1
return (dataType) removeNode.getNodeData();//返回删除节点的数据
}
counter++;
tmp = tmp.getNext();
}
}
return null;
}
5、替换
方法set(替换位置,替换的数据)根据指定位置替换数据，很简单找到相应位置用setNodeData替换数据就行了
public dataType set(int index, dataType value) {
if (index < 0 || index > this.size - 1) {
throw new ArrayIndexOutOfBoundsException("修改的位置不合法");
} else {
int counter = -1;
Node tmp = head;
while (tmp != null) {
if (counter == index) {
dataType replacData = (dataType) tmp.getNodeData();
tmp.setNodeData(value);
return replacData;
}
tmp = tmp.getNext();
counter++;
}
}
return null;
}
6、拓展（链表转化为数组）
方法toArray()将链表转换数组，很简单，根据链表长度新建数组，然后遍历装进数组就行了
public Object[] toArray() {
Object[] array = new Object[this.size];
Node tmp = head;
int counter = -1;
while (tmp.getNext() != null) {
counter++;
tmp = tmp.getNext();
array[counter] = tmp.nodeData;
}
return array;
}
7、其他操作
获取链表长度
public int size() {
return this.size;
}
总结
如此我们就完成了整个链表的构造，我们发现在链表的实现中我们大量的用到了遍历，所以在查找数据的实惠相对的链表机会比顺序表慢，因为顺序表可以用下标直接引用，但是在需要大量删除或者添加操作的时候链表的效率明显就会比顺序表快，因为在增加或者删除数据的时候链表只需要改变一下各个节点的引用关系就行了，不需要像顺序表一样移动大量元素。
而且链表也无需考虑容量问题因为增加节点只需要引用就行了，也解决了顺序表的冗余问题，但是单链表依然存在一些问题，这些遗留的问题就留到下次笔记学习~~
本次代码下载地址
链接：https://pan.baidu.com/s/1cSZoWkFwvrCe_Xd6sp7juw 密码：5wp1
