模拟实现 java 中单链表的实现，方便后续对 java 中的 LInkedList 进行理解。
MySingleList类：
public class MySingleList {/*** 定义节点类*/static class ListNode {// 节点值private int val; // 下一个节点的引用private ListNode next; public ListNode(int val) {this.val = val;}}// 头节点private ListNode head;/*** 头插法*/public void headInsert(int value) {// 申请节点ListNode node = new ListNode(value);// 头插node.next = head;head = node;}/*** 尾插法*/public void tailInsert(int value) {// 申请节点ListNode node = new ListNode(value);// head 为空if (head == null) {// head 直接指向 nodehead = node;return;}ListNode cur = head;// 找最后一个节点while (cur.next != null) {cur = cur.next;}cur.next = node;}/*** 任意位置插入*/public void randomInsert(int index, int value) {// 判断下标是否合理judge(index);// 判断是否是头插或尾插if (isInsert(index, value)) {return;}// 中间位置插入ListNode cur = head;// 找到插入位置的前一个位置for (int i = 0; i < index - 1; i++) {cur = cur.next;}// 插入ListNode node = new ListNode(value);node.next = cur.next;cur.next = node;}/*** 判断下标是否合理*/private void judge(int index) {if (index < 0 || index > size()) {throw new IndexOFBoundException("下标: " + index + "错误!");}}/*** 判断插入位置是否是头插或尾插*/private boolean isInsert(int index, int value) {if (index == 0) { // 头插headInsert(value);return true;} else if (index == size()) { // 尾插tailInsert(value);return true;} else {return false;}}/*** 查找 value 是否在链表中存在*/public boolean contains(int value) {ListNode cur = head;while (cur != null) {if (cur.val == value) {return true;}cur = cur.next;}return false;}/*** 删除链表中第一次出现 value 的节点*/public void remove(int value) {// head 为空或要删除的节点是 headif (isNullOrHead(value)) {return;}// 获取要删除节点的前一个节点ListNode preNode = findFirstDeletePreNode(value);// 判断 preNode 为空if (preNode == null) {System.out.println("没有这个元素对应的节点");return;}// 删除节点ListNode delNode = preNode.next;preNode.next = delNode.next;}/*** 要删除的节点为空或是第一个节点*/private boolean isNullOrHead(int value) {if (head == null) { // head 为空return true;} else if (head.val == value) { // head 的 val 和 value 相同// head 后移head = head.next;return true;} else {return false;}}/*** 查找要删除 value 节点*/private ListNode findFirstDeletePreNode(int value) {ListNode cur = head;while (cur.next != null) {// 找到了要删除节点的前驱if (cur.next.val == value) {return cur;}cur = cur.next;}// 没找到return null;}/*** 删除所有值为 value 的节点*/public void removeAllValue(int value) {// 判空if (head == null) return;ListNode prev = head;ListNode cur = head.next;while (cur != null) {// 判断 cur.val 是否和 value 相等if (cur.val == value) {// 相等则让 prev.next 指向 cur.nextprev.next = cur.next;} else {// prev 移动到 cur 的位置prev = cur;}// cur 移动到 cur.nextcur = cur.next;}// 判断第一个节点的值是否和 value 相等if (head.val == value) {head = head.next;}}/*** 获取单链表的长度*/public int size() {ListNode cur = head;int count = 0;while (cur != null) {count++;cur = cur.next;}return count;}/*** 清空单链表*/public void clear() {// 把 head 置为 nullthis.head = null;}/*** 打印数组中的元素*/public void display() {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");// 指向下一个值cur = cur.next;}System.out.println();}
}IndexOFBoundException类：
public class IndexOFBoundException extends RuntimeException {public IndexOFBoundException() {}public IndexOFBoundException(String message) {super(message);}
}Test类
public class Test {public static void main(String[] args) {MySingleList mySingleList = new MySingleList();/*mySingleList.headInsert(1);mySingleList.headInsert(2);mySingleList.headInsert(3);*///mySingleList.display();mySingleList.tailInsert(1);mySingleList.tailInsert(2);mySingleList.tailInsert(3);mySingleList.tailInsert(4);mySingleList.tailInsert(5);mySingleList.tailInsert(6);mySingleList.display();mySingleList.randomInsert(0, 111);mySingleList.randomInsert(7, 111);mySingleList.randomInsert(3, 111);//mySingleList.randomInsert(12, 111);mySingleList.display();mySingleList.remove(2);mySingleList.display();mySingleList.removeAllValue(111);mySingleList.display();}
}
