单链表
什么是链表？
链表是一种物理存储结构上非连续存储结构，连接顺序是通过链表链表当中的引用来实现的。也就是说一个节点内存着下一个节点的地址。但要注意的是，链表的最后一个节点的指向是 null 。如下图所示：
head 表示链表的第一个头节点。next 就是指向下一个节点的地址，也是下一个地址的引用。
链表的实现
链表的初始化
在实现链表的时候，每一个节点都有两个元素：链表的值和下一个地址的引用。所以初始化的代码就如下：
class ListNode{
public int val; //代表数字
public ListNode next; //ListNode 是一个节点的地址 所以类型就是节点类型
public ListNode(int val) {
this.val = val;
}
}
创建一个头节点
创建一个头节点，让其指向我们的链表，之后的增删改查就很方便。
public ListNode head;
创建链表
在进行链表的增删查改之前，我们可以先自己创建一个链表。代码如下：
public void CreateList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
this.head = listNode1;
}
这样就完成了对链表的创建。
打印链表
因为链表也是连着的，所以我们打印的时候就可以通过引用来打印，也就是让 head 往下走就行了，就是 head = head.next 当 head 为 null 的时候，就说明走到最后了，然后就不打印了，所以需要循环来解决。但是当这样循环之后，发现链表的头丢了，所以还应该定义一个变量来代替头节点来往后走。这样就完成了链表的打印。
public void display() {
//定义一个变量 cur 等于 head 不然最后头节点就丢了
ListNode cur = this.head;
while (cur != null){
System.out.print(cur.val+" ");
cur = cur.next;
}
System.out.println();
}
先创建链表，然后再打印。输出结果如下：
查找链表是否包含关键字 key
查找元素的时候，通过遍历就可以知道是否包含这个元素。所以直接遍历就好，如果有这个元素，就返回 true 没找到就返回 false 。代码如下：
public boolean contains (int key){
ListNode cur = this.head;
while(cur != null){
if(cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
使用我们之前创建的链表来测试 contains 方法。查找 23 和 89 。
MyLinkList myLinkList = new MyLinkList();
myLinkList.CreateList();
System.out.println(myLinkList.contains(23));
System.out.println(myLinkList.contains(89));
求单链表的长度
链表的结构就和我们上面所画的图一样，只要遍历就可以求到长度，遍历的结束标志就是：当前节点为 null 的时候，就可以结束循环。所以代码就可以写成这样：
public int size(){
int count = 0;
ListNode cur = this.head;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
还是使用前面的代码，所以输出结果就是：
头插法
头插就是在单链表的头节点前面再插入一个节点，然后再把插入的节点变为头节点就好了。代码如下：
public void addFirst(int data){
//插入的时候需要一个节点 就 new 一个
//一定要记住：绑定位置的时候，先绑定后面的，这样就不会把数据弄丢了
ListNode node = new ListNode(data);
node.next = head;
this.head = node;
}
执行结果如下：
尾插法
尾插法就是在尾部插入一个数据。插入的时候，要寻找尾节点。找到尾节点之后再插入。如果头节点为空，那么插入之后还是 null 就会导致异常，所以尾插第一次一定要判断是否为 null 。
寻找尾节点：cur.next = null;
当找到尾节点之后就可以插入了。代码如下：
public void addLast(int data){
ListNode node = new ListNode(data);
if(this.head == null){
this.head = node;
} else {
ListNode cur = this.head;
while (cur.next != null){
cur = cur.next;
}
cur.next = node;
}
}
插入结果如下：
找到给定位置的前一个节点的地址
找到这个位置是为了在随机位置插入一个元素的时候方便插入，因为要根据前一个位置的节点的 next 来指向插入的节点。代码如下：
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index - 1 != 0){
cur = cur.next;
index--;
}
return cur;
}
任意位置插入一个节点
插入一个节点的时候就是，先找到前一个节点，然后 next 指向要插入的这个节点。代码如下：
public void addIndex(int index,int data){
if(index < 0 || index > size()){
System.out.println("index 位置不合法");
return;
}
if(index == 0){
addFirst(data);
return;
}
if(index == size()){
addLast(data);
return;
}
ListNode cur = findIndex(index);
ListNode node = new ListNode(data);
node.next = cur.next;
cur.next = node;
}
示例：
public static void main(String[] args) {
MyLinkList myLinkList = new MyLinkList();
myLinkList.CreateList();
myLinkList.display();
myLinkList.addIndex(2,999);
myLinkList.display();
}
找到要删除的关键字的前驱
在进行删除操作的时候，比如说删除某个关键字。先从链表里面看看有没有这个关键字。如果有，返回这个关键字的节点，如果没有就返回 null 。代码如下：
public ListNode searchPerv(int key){
ListNode cur = this.head;
while (cur.next != null){
if(cur.next.val == key){
return cur;
}
cur = cur.next;
}
return null;
}
删除第一次出现关键字为key的节点
给一个关键字，删除值为 key 的节点，这里有两种情况，头节点为 key ，其余节点为 key 。针对不同的情况要有不同的思考方式。如果是其余节点，那么只需要找到前一个节点就好了，让前一个节点的 next 指向下一个节点就好了，如下图：
如果是头节点，那么只需让头节点指向下一个节点就行了。代码如下：
public void remove(int key){
if(this.head == null){
System.out.println("单链表为 null 不能删除");
return;
}
if(this.head.val == key){
this.head = this.head.next;
return;
}
ListNode cur = searchPerv(key);
if(cur == null){
System.out.println("未找到此元素");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
下面测试：
public static void main(String[] args) {
MyLinkList myLinkList = new MyLinkList();
myLinkList.CreateList();
myLinkList.display();
myLinkList.remove(12);
myLinkList.display();
myLinkList.remove(56);
myLinkList.display();
}
测试结果发现都可以删除。
删除所有值为 key 的节点（仅遍历一次）
因为要一次遍历就删除所有结点，所以我们这里用到前（prev）后（cur）双指针，也就是一个指向前一个节点，另外一个指向后一个节点。当然我们的方法还是先处理非头节点，再处理头节点。在处理的时候，如果 cur.val == key 那就让 prev.next = cur.next 再让 cur = cur.next 这样即完成了对节点的删除。代码如下：
public ListNode removeAllKey(int key){
if(this.head == null){
return null;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
//处理非头节点的 key
while (cur != null){
if(cur.val == key){
prev.next = cur.next;
cur = cur.next;
} else {
prev = cur;
cur = cur.next;
}
}
if(this.head.val == key){
this.head = this.head.next;
}
return this.head;
}
演示如下：
public static void main(String[] args) {
MyLinkList myLinkList = new MyLinkList();
myLinkList.CreateList();
myLinkList.display();
myLinkList.removeAllKey(45);
myLinkList.display();
}
清空链表
在链表当中，很多情况下是一个节点引用着其它内容，所以如果不把这个节点的引用置为 null 的话，就算不引用这个节点，这个节点引用的内容还会浪费内存，所以最好的方法就是把所有节点的引用全部置为 null 。代码如下：
public void clear(){
while (this.head != null){
ListNode curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}
演示如下：
public static void main(String[] args) {
MyLinkList myLinkList = new MyLinkList();
myLinkList.CreateList();
myLinkList.display();
myLinkList.clear();
myLinkList.display();
}
