没个节点只保存了下一个节点的地址，只能从头节点开始向后遍历。
创建一个单链表
public class SingleLinedList {
// 链表的头节点
private Node head = null;
// 当前链表中Node节点的个数 = 有效数值的个数
private int size = 0;
class Node {
int val; // 每个节点保存的值
Node next; // 当前节点的下一个节点地址。
}
如何遍历一个单链表？
从当前头节点开始，依次取出每个节点值，然后通过next引用走到下一个节点，直到走到链表的末尾（next = null）。
注意：遍历过程中不能直接使用head引用！！！直接使用head引用的话，遍历一次链表后，链表就丢了，此时需要使用过一个临时变量，暂存head的值。
public String toString() {
String ret = "";
Node x = head;
while (x != null) {
ret += x.val;
ret += "->";
x = x.next;
}
ret += "NULL";
return ret;
}
添加
头插法：
添加元素在链表
注意： 必须是先1后2 ，如果顺序反了会丢失原来的链表头节点。！！！
public void addFirst(int val) {
Node newNode = new Node();
// 保存值
newNode.val = val;
if(head != null) {
newNode.next = head;
}
// 无论是否为空，新节点都是插入后的链表头结点
head = newNode;
size ++;
}
在链表index位置插入：
单链表最核心的操作是：找前驱！！！
要把10新节点插入到索引为2的位置，首先要找到待插入位置的“前驱”。
同样的需要注意代码顺序！！！
public void add(int index,int val) {
// 1.若index位置非法的
if (index < 0 || index > size) {
System.err.println("add index illegal!");
return;
}
// 2.插入任意位置要找到前驱结点，但是链表中有一个结点没有前驱
// 头结点没有前驱！！！
if (index == 0) {
// 头插！
addFirst(val);
}else {
// 3.当前索引合法且不是在数组的头部插入,就要找到插入位置的前驱结点
Node newNode = new Node();
newNode.val = val;
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
// 此时prev一定指向了待插入节点的前驱
newNode.next = prev.next;
prev.next = newNode;
size ++;
}
}
尾插法：
public void addLast(int val) {
add(size,val);
}
查询
boolean contains(int val)：
是否包含指定值的结点
public int getByValue(int val) {
int index = 0;
for (Node x = head;x != null;x = x.next) {
if (x.val == val) {
// 第一个值为val的节点
return index;
}
index ++;
}
// 说明当前链表中根本就没有值为val的结点，返回-1,表示不存在
return -1;
}
get(int index)：
查询索引为index的元素值是多少。
public boolean contains(int val) {
int index = getByValue(val);
return index != -1;
if (index == -1) {
return false;
}
return true;
}
igetByValue(int val)：
查询第一个值为val的结点索引是多少
因为在修改和删除操作时也需要对index索引位置的合法性进行判断，所以单独创建一个方法判断index的合法性。
private boolean rangeCheck(int index) {
// size是当前有效元素的下一个索引
if (index < 0 || index >= size) {
return false;
}
return true;
}
public int get(int index) {
// 1.判断index的合法性
if (rangeCheck(index)) {
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x.val;
}
System.err.println("index illegal!get error");
return -1;
}
修改
set(int index,int newVal)：
修改索引为index位置的结点值为newVal
public int set(int index,int newVal) {
if (rangeCheck(index)) {
Node x = head;
for (int i = 0; i < index; i++) {
x = x.next;
}
int oldVal = x.val;
x.val = newVal;
return oldVal;
}
System.err.println("index illegal!set error");
return -1;
}
删除
（找前驱）
remove(int index)：
删除索引为index位置的元素
public int remove(int index) {
if (rangeCheck(index)) {
if (index == 0) {
// 删除头结点
Node x = head;
head = head.next;
size --;
x.next = null;
return x.val;
}else {
// 此时删除的是链表的中间结点
// 找前驱！
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
// prev就是待删除节点的前驱
// node节点就是待删除的结点
Node node = prev.next;
prev.next = node.next;
node.next = null;
size --;
return node.val;
}
}
System.err.println("remove index illegal!");
return -1;
}
removeValueOnce(int val)：
删除第一个值为val的元素
思路：
①先判断头节点的值是不是等于val
②head.val != val 时，我们现在要找到待删除的节点的前驱，保证程序中前驱节点一定不是待删除的节点。此时prev一定不是待删除结点,prev.val !=val,因此我们判断节点值是否等于待删除的结点，至少也是从当前结点的下一个开始的!
public void removeValueOnce(int val) {
if (head == null) {
System.err.println("链表为空，无法删除");
return;
}
if (head.val == val) {
// 此时头结点就是第一个值为val的结点
Node x = head;
head = head.next;
x.next = null;
size --;
}else {
// 当前头结点不是待删除的结点，需要遍历
// 这里同样找到待删除的前驱结点
// 能否知道前驱结点移动步数？
Node prev = head;
while (prev.next != null) {
// 至少还有后继结点
if (prev.next.val == val) {
// 此时prev.next就是待删除的结点
Node node = prev.next;
prev.next = node.next;
node.next = null;
size --;
return;
}
prev = prev.next;
}
}
}
removeAllValue(int val)：
删除链表中所有值为val的元素
思路和上面删除第一个值为val的元素只有一点点不同，问题的关键在于删除一个节点后，prev不能简单的向后移动，一定要确保删除后prev.next.val != val才能移动prev移动。
public void removeAllValue(int val) {
while (head != null && head.val == val) {
// 头节点就是待删除节点
Node x = head;
head = head.next;
x.next = null;
size --;
}
// 头节点一定不是待删除的节点
// 判空
if (head == null) {
// 链表删完了
return;
}else {
Node prev = head;
while (prev.next != null) {
// 至少还有后继结点
if (prev.next.val == val) {
// 此时prev.next就是待删除的结点
Node node = prev.next;
prev.next = node.next;
node.next = null;
size --;
}else {
// 只有当prev.next.val != val才能移动prev指针！
prev = prev.next;
}
}
}
}
