目录 

1.车厢类

2.火车类

2.1.在链表任意位置index处插入节点

2.2.在链表头部添加节点

2.3.在链表尾部添加节点

2.4.在链表任意位置index处删除节点

2.5.删除链表头部节点

2.6.删除链表尾部节点

2.7.toString()方法

3.总代码实现

1.车厢类

/*** 车厢类*/
class Node {//存储具体元素int data;//存储下一个节点的地址Node next;//构造方法public Node(int data) {this.data=data;}public Node(int data, Node next) {this.data = data;this.next = next;}
}

2.火车类

/*** 带头单链表（头节点不存储具体元素）*/
public class SingleLinkedListWithHead {//虚拟头节点 在内存中实实在在存在的节点，有一个引用指向private Node dummyHead = new Node(-1); //-1 表示这个节点的data值无意义，这个节点就是来连接/脱钩其他节点的。若data不赋值，int默认就是0，而有时0恰好又是需要存储的元素，而负数较少见。
//    只声明一个Node类的引用，无具体节点，在内存中没开空间
//    private Node dummyHead;//单链表中具体节点的个数（不包含虚拟头节点）private int size;//具体方法实现//...
}

2.1.在链表任意位置index处插入节点

/*** 在链表任意位置index处插入节点* @param index* @param data*/
public void addIndex(int index, int data) {if(index < 0 || index > size) {System.err.println("add index illegal!");return;}//此时无论index为何值，都存在前驱节点Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}//prev就指向了待插入的前驱节点Node node = new Node(data);node.next = prev.next;prev.next = node;size++;
}

2.2.在链表头部添加节点

/*** 在链表头部添加节点* @param data*/
public void addFirst(int data) {addIndex(0, data);
}

2.3.在链表尾部添加节点

/*** 在链表尾部添加节点* @param data*/
public void addLast(int data) {addIndex(size, data);
}

2.4.在链表任意位置index处删除节点

/*** 在链表任意位置index处删除节点* @param index* @return 返回删除前的节点值*/
public int removeIndex(int index) {if(index < 0 || index >= size) {System.err.println("remove index illegal!");return -1;}Node prev = dummyHead;//先找到待删除节点的前驱for (int i = 0; i < index; i++) {prev = prev.next;}//prev指向了待删除节点的前驱Node node = prev.next;prev.next = node.next;node.next = null;size--;return node.data;
}

2.5.删除链表头部节点

/*** 删除链表头部节点* @return*/
public int removeFirst() {return removeIndex(0);
}

2.6.删除链表尾部节点

/*** 删除链表尾部节点* @return*/
public int removeLast() {return removeIndex(size - 1);
}

2.7.toString()方法

public String toString() {String ret = "";Node node = dummyHead.next;while (node != null) {ret += node.data + "->";node = node.next;}ret += "NULL";return ret;
}

3.总代码实现

/*** 车厢类*/
class Node {//存储具体元素int data;//存储下一个节点的地址Node next;//next是自定义的Node引用类型，存储Node类型的对象的地址，即车厢地址//所有类以及数组都是引用类型，所有引用数据类型存储的都是一个类的对象的地址(起个别名)//所有引用类型的默认值都是NULL//当new一个对象时，它才有意义//构造方法 alt+insert 但此电脑无法使用public Node(int data) {this.data=data;}public Node(int data, Node next) {this.data = data;this.next = next;}
}/*** 火车类 带头单链表（头节点不存储具体元素）*/
public class SingleLinkedListWithHead {//虚拟头节点 在内存中实实在在存在的节点，有一个引用指向private Node dummyHead = new Node(-1); //-1 表示这个节点的data值无意义，这个节点就是来连接/脱钩其他节点的。若data不赋值，int默认就是0，而有时0恰好又是需要存储的元素，而负数较少见。
//    只声明一个Node类的引用，无具体节点，在内存中没开空间
//    private Node dummyHead;//单链表中具体节点的个数（不包含虚拟头节点）private int size;/*** 在链表任意位置index处插入节点* @param index* @param data*/public void addIndex(int index, int data) {if(index < 0 || index > size) {System.err.println("add index illegal!");return;}//此时无论index为何值，都存在前驱节点Node prev = dummyHead;for (int i = 0; i < index; i++) {prev = prev.next;}//prev就指向了待插入的前驱节点Node node = new Node(data);node.next = prev.next;prev.next = node;size++;}/*** 在链表头部添加节点* @param data*/public void addFirst(int data) {addIndex(0, data);}/*** 在链表尾部添加节点* @param data*/public void addLast(int data) {addIndex(size, data);}/*** 在链表任意位置index处删除节点* @param index* @return*/public int removeIndex(int index) {if(index < 0 || index >= size) {System.err.println("remove index illegal!");return -1;}Node prev = dummyHead;//先找到待删除节点的前驱for (int i = 0; i < index; i++) {prev = prev.next;}//prev指向了待删除节点的前驱Node node = prev.next;prev.next = node.next;node.next = null;size--;return node.data;}/*** 删除链表头部节点* @return*/public int removeFirst() {return removeIndex(0);}/*** 删除链表尾部节点* @return*/public int removeLast() {return removeIndex(size - 1);}public String toString() {String ret = "";Node node = dummyHead.next;while (node != null) {ret += node.data + "->";node = node.next;}ret += "NULL";return ret;}
}