2.3 MyLinkedList类的成员方法
2.3.1 在链表开头插入一个新结点
在链表开头插入一个结点，首先需要根据 data 数据实例化一个结点。然后让这个新结点的 next 指针域存 head 的地址， 这样就让新的结点与后面的结点链接起来了，最后让 head 等于这个新结点，这样这个新结点就变成了第一个结点
//头插法 public void addFirst(int data) { Node nodeTmp = new Node(data); nodeTmp.next = this.head; this.head = nodeTmp; }
2.3.2 获取链表的最后一个结点
首先 head 不能移动，如果移动第一个结点就会因没有被指向而回收，那么后面结点也就会因为没有被指向而被回收，所以需要创建一个临时的结点类型的变量 src，将 head 指向的结点赋值给它，这样 head 和 src 同时指向了第一个结点，当src 移动到其他结点，第一个结点还是会被 head 所指向。src 通过循环一直等于下一个结点，当 src 存储的结点的 next 为 null 时就为最后一个结点
//获取链表的最后一个结点 private Node lastNode() { Node src = this.head; while (src.next != null) { src = src.next; } return src; }
注：这个方法是private修饰所以只能在 MyLinkedList类 中使用
2.3.3 在链表尾部插入一个新的结点
在链表尾部插入一个结点，首先需要这个链表是否为空，如果链表为 null ，尾插一个结点就相当于在链表开头插入一个结点。如果链表不为 null ，尾部插入一个结点就需要根据 data 数据实例化一个结点，然后通 lastNode 方法获取最后一个结点，让最后一个结点的 next 存储新结点的地址即可
//尾插法 public void addLast(int data) { if (head == null) { addFirst(data); return; } Node nodeTmp = new Node(data); Node last = lastNode(); last.next = nodeTmp; }
2.3.4 返回指定位置的前一个结点
首先判断位置是否合法，如果不合法直接返回 null ，否则用一个临时结点变量等于 head 指向的结点，然后通过循环 index - 1 次而找的指定位置的前一个结点
//返回指定位置的前一个结点 private Node prevNode(int index) { if (index > size() || index < 0) { return null; } Node src = this.head; while(index != 1) { src = src.next; index--; } return src; }
2.3.5 在链表指定位置插入一个新结点
第一步判断指定位置是否合法，如果不合法直接返回 false。否则进入第二步判断插入的位置是否为第一个结点位置，如果是就直接采用头插法在链表的开头插入一个结点。否则进入第三步判断插入的位置是否为最后一个结点的下一个位置，如果是就直接采用尾插法在链表的尾部插入一个结点。否则就在实例化一个 data 数据结点，调用 preNode 方法获取指定位置的前一个结点，在用一个临时变量去存储前一个结点的后一个结点，让前一个结点的 next 存储这个新的结点地址，再让这个新的结点的 next 存储后一个结点地址即可
//任意位置插入,第一个数据结点为0号下标 public boolean addIndex(int index,int data) { if (index > size() || index < 0) { return false; } else if (index == 0) { addFirst(data); } else if (index == size()) { addLast(data); } else { Node nodeTmp = new Node(data); Node prev = prevNode(index);//指定位置前一个结点 Node tmp = prev.next;//指定位置的结点 prev.next = nodeTmp; nodeTmp.next = tmp; } return true; }
注：if...else if...else if...else...这种多判断只会执行其中的一个
2.3.6 判断是否需要删除第一个结点
判断数据 key 是否与第一个结点数据域中的数据相同，如果相同则让head等于head.next，这样head就指向了下一个结点，也就删除了第一个结点
//判断第一个结点是否是指定的结点，如果是则删除第一个结点 private boolean judgeFistNode(int key) { if (key == this.head.data) { this.head = this.head.next; return true; } return false; }
2.3.6 删除第一次出现的指定数据的结点
首先判断这个链表是否为 null，否则就判断指定数据的结点是否为链表的第一个结点，否则就通过两个结点变量去找这个数据结点以及它的前一个结点，找到之后让它的前一个结点的 next 存储它后结点的地址然后直接return，因为只删除第一次输出的指定数据的结点。如果遍历完都没有找到这个数据结点则没有这个数据结点
//删除第一次出现关键字为key的节点 public void remove(int key) { if (this.head == null) { return; } boolean judge = judgeFistNode(key); if (judge == true) { return; } Node src = this.head; Node slow = this.head; while (src != null) { if (src.data != key) { slow = src; src = src.next; } else { slow.next = src.next; return; } } }
2.3.7 删除所有指定数据的结点
首先判断这个链表是否为 null， 否则就通过两个结点变量去找这个数据结点以及它的前一个结点，找到之后让它的前一个结点的 next 存储它后结点的地址，一直遍历完，因为要删除所有指定数据的结点。遍历完后在判断第一个结点是否为空，也就相当于如果第一个结点是要删除的结点，先不管它，先删后面的在删第一个结点
//删除所有值为key的节点 public void removeAllKey(int key) { if (this.head == null) { return; } Node src = this.head; Node slow = this.head; while (src != null) { if (src.data != key) { slow = src; src = src.next; } else { slow.next = src.next; src = src.next; } } judgeFistNode(key); }
2.3.8 查找链表中是否有指定的数据
直接将这个链表遍历一遍，如果有直接返回 true，否则返回 false
//查找是否包含关键字key是否在单链表当中 public boolean contains(int key) { Node src = this.head; while (src != null) { if (src.data == key) { return true; } src = src.next; } return false; }
2.3.9 获取链表的长度
直接将这个链表遍历一遍用一个整型变量计数即可
//得到单链表的长度 public int size() { Node src = this.head; int count = 0; while (src != null) { count++; src = src.next; } return count; }
2.3.10 打印链表
首先判断这个链表是否为 null ，如果为空直接打印 null。否则将这个链表遍历一遍，打印每个结点数据域中的数据
//打印链表 public void display() { if (this.head == null) { System.out.print("null"); } Node src = head; while (src != null) { System.out.print(src.data + " "); src = src.next; } System.out.println(); }
2.3.11 清空链表
直接让 head 指向 null，这样第一个结点就没有被指向了，会直接被编译器回收。第一个结点被回收了，第二个结点也就没有被指向了也会被回收，依次如此，直到将整个链表全部回收
//清除链表 public void clear() { this.head = null; }
