数据结构-链表的简单操作实现
目录
0.链表前序工作
1.构建出一个链表
2.展示链表中的所有存储数据
3.查找关键字key是否在链表中
4.求链表的长度
5.头插法
6.尾插法
7.插入任意位置（规定第一个元素位置为0下标）
8.删除第一次出现的值为key的关键字
9.删除所有值为key的关键字
10.清空所有节点
0.链表前序工作
在进行链表的相关操作之前，首先需要进行链表的构造。
在一个链表节点中，有两个区域：
一个用来存储当前节点的数据-val；
另一个需要存储下一个节点的地址。
static class Node{public int val;//存储的数据public Node next;//存储下一个节点的地址；//提供一个构造方法public Node(int val){this.val = val;}}定义一个head，代表当前头节点的引用
public Node head;//代表当前链表头结点的引用1.构建出一个链表
构建一个链表将构建的链表节点串起来。
这里我们构建四个节点，
public void createLink(){Node node1 = new Node(1);Node node2 = new Node(1);Node node3 = new Node(1);Node node4 = new Node(1);node1.next = node2;node2.next = node3;node3.next = node4;head = node1;}2.展示链表中的所有存储数据
将存储在链表中的数据进行展示，这里定义一个节点cur，和head相同的指向。
随后将cur向后挪动，当cur的值不为空的时候，向后挪动打印；
当cur的值为空时，证明链表到达了末尾，已经没有元素，进而跳出while循环。
需要注意的内容：
（1）如果要将整个链表遍历完成 那么就要head == null;
（2）如果是遍历到链表的尾巴。条件是head.next == null；
public void display(){//如果要将整个链表遍历完成 那么就要head == null;//如果是遍历到链表的尾巴。条件是head.next == nullNode cur = head;while(cur != null){System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}3.查找关键字key是否在链表中
在链表中搜寻是否包含关键字key，
同样我们需要一个新的节点和头节点head指向相同的位置；
向后一直走，循环条件是节点的内容不为null，也就是（cur！=null）
存在结果返回true，否则返回false；
public boolean contains(int key){Node cur = head;while (cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}4.求链表的长度
链表的长度定义为size（），首先定义变量count等于0，同样定义一个cur节点和head指向相同位置，向后遍历，循环条件为cur != null。每循环一次，计数器数值加1，指针向后挪动一个位置。
public int size(){int count = 0;Node cur = head;while(cur != null){count++;cur = cur.next;}return count;}5.头插法
进行头插法，首先准备好一个新的节点node，用来存放传进来的数据data；
node的next指向head；
让head指向node。
public void addFirst(int data){Node node = new Node(data);node.next = head;head = node;}6.尾插法
首先判断是否为第一次插入，当头节点为null的时候，将head指向node节点，返回。
如果不是第一次插入节点，同样定义一个为cur的节点指向head；cur向后挪，直至走到链表最后，将cur的next指向新的节点node，完成尾插操作。
public void addLast(int data){Node node = new Node(data);//判断是不是第一次插入if(head == null){head = node;return;}Node cur = head;while(cur.next != null){cur = cur.next;}cur.next = node;}7.插入任意位置（规定第一个元素位置为0下标）
在链表中插入任意位置，需要传入两个值-位置下标、插入的数值.
判断要插入的位置是否合法：自己写一个方法检查下标：checkIndex
首先，如果插入下标为0下标-头插法；插入下标为链表的长度size-尾插法；
其他情况就是在链表的中间位置：
需要找到链表中需要插入位置的前一个位置的下标位置：findIndexSubOne。【因为我们在这里讨论的链表为单向不带头节点的链表，必须要找到需要元素需要插入位置的前一个位置，进而进行后续操作】。
得到插入到链表中前一个位置的下标，定义为cur；要插入的数据定义为node;
具体两步的指向如下图所示。
public void addIndex(int index,int data)throws ListIndexOutOfException{checkIndex(index);if(index == 0){addFirst(data);return;}if(index == size()){addLast(data);return;}Node cur = findIndexSubOne(index);Node node = new Node(data);node.next = cur.next;cur.next = node;}checkIndex
private void checkIndex(int index){if(index < 0 || index > size()){throw new ListIndexOutOfException("index位置不合法！");}}ListIndexOutOfException
public class ListIndexOutOfException extends RuntimeException{public ListIndexOutOfException() {}public ListIndexOutOfException(String message) {super(message);}
}findIndexSubOne
private Node findIndexSubOne(int index){Node cur = head;int count = 0;while (count != index -1){cur = cur.next;count++;}return cur;}8.删除第一次出现的值为key的关键字
删除第一次出现的值为key的关键字
首先当链表的表头就是我们要找的关键字：将头节点向后挪动，返回即可。
寻找到要删除节点的前一个节点：searchPrev(key)
public void remove(int key){if(head.val == key){head = head.next;return;}Node cur = searchPrev(key);//代表当前节点if(cur == null){return ;}Node del = cur.next;//代表要删除的节点cur.next = del.next;}
searchPrev(key)
private Node searchPrev(int key){if(head == null){return null;//一个节点都没有}Node cur = head;while(cur.next != null){if(cur.next.val == key){return cur;}cur = cur.next;}//代表根本没有要删除的节点return null;}9.删除所有值为key的关键字
在链表中删除所有值为key的关键字
首先判断链表中有无元素，如果头节点的指向为null的话，返回return;
在这里定义两个指针prev指向头的位置；
cur指向头的下一个位置。
这里选择先不进行对头结点的判定
public void removeAllKey(int key){if(head == null){return;}Node prev = head;Node cur = head.next;while (cur != null){if(cur.val == key){prev.next = cur.next;cur = cur.next;}else {prev = cur;cur = cur.next;}}if(head.val == key){head = head.next;}}10.清空所有节点
public void clear(){head = null;}