/** * 节点类 */ class DataNode { public String data; //存放节点数据 这里为了方便是String类型,实际的链表应该是泛型或者Object类型 public DataNode next; // 存放下一个节点 public DataNode(String data) { this.data = data; } /** * 重写toString 方便用json的格式打印出来 */ @Override public String toString() { return "{" + "\"data\":\"" + data + "\","+ "\"next\":" + next + "}"; } }
class SingleLinkedList { private final DataNode header; // 头部节点 public SingleLinkedList(){ this.header = new DataNode("链表头部"); } public void add(String data) { // 1.找到链表最后一个节点对象 保存到变量 tempNode DataNode tempNode = header; while (tempNode.next != null) { tempNode = tempNode.next; } // 2.将新生成的节点指向链表最后的一个节点 tempNode.next = new DataNode(data); } public int size() { int tempIndex = 0; DataNode tempNode = header; while (tempNode.next != null) { tempNode = tempNode.next; tempIndex ++; } return tempIndex; } /** * 移除指定位置的数据 */ public String get(int index) { // 1.找到位置为 i 的节点对象 保存到变量 tempNode DataNode tempNode = header.next; int tempIndex = 0; while (true) { if (tempNode == null) { throw new RuntimeException("访问不到的下标:"+ index); } else if (tempIndex == index){ break; } tempNode = tempNode.next; tempIndex ++ ; } return tempNode.data; } /** * 移除指定数据,只移除第一个 */ public void remove(String data) { // 1.找到数据为 data 的节点对象 保存到变量 tempNode DataNode tempBeforeNode = header; DataNode tempNode; while (true) { tempNode = tempBeforeNode.next; if (tempNode == null) { throw new RuntimeException("在链表中找不到数据:"+ data); } else if (tempNode.data.equals(data)){ break; } tempBeforeNode = tempBeforeNode.next; } // 2.将 tempNode 后面的节点指向 tempUpNode tempBeforeNode.next = tempNode.next; } /** * 移除指定位置的数据 */ public void remove(int index) { // 1.找到位置为 i 的节点对象 保存到变量 tempNode DataNode tempBeforeNode = header; DataNode tempNode; int tempIndex = 0; while (true) { tempNode = tempBeforeNode.next; if (tempNode == null) { throw new RuntimeException("访问不到的下标:"+ index); } else if (tempIndex == index){ break; } tempBeforeNode = tempBeforeNode.next; tempIndex ++ ; } // 2.将 tempNode 后面的节点指向 tempUpNode tempBeforeNode.next = tempNode.next; } public String toString() { if (header.next == null) { return "{}"; } else { return header.next.toString(); } } }
public class SingleLinkedListDemo { public static void main(String[] args) { SingleLinkedList singleLinkedList = new SingleLinkedList(); System.out.println("打印出空链表: " + singleLinkedList); singleLinkedList.add("大哥刘备"); singleLinkedList.add("二哥曹操"); singleLinkedList.add("三哥关羽"); singleLinkedList.add("四弟张飞"); System.out.println("添加数据后打印出链表: " + singleLinkedList); System.out.println("链表大小: " + singleLinkedList.size()); System.out.println("链表第一个数据: " + singleLinkedList.get(0)); singleLinkedList.remove(0); System.out.println("移除第一个数据后打印出链表: " + singleLinkedList); singleLinkedList.remove("四弟张飞"); System.out.println("移除第'四弟张飞'后打印出链表: " + singleLinkedList); } }
测试结果
打印出空链表: {} 添加数据后打印出链表: {"data":"大哥刘备","next":{"data":"二哥曹操","next":{"data":"三哥关羽","next":{"data":"四弟张飞","next":null}}}} 链表大小: 4 链表第一个数据: 大哥刘备 移除第一个数据后打印出链表: {"data":"二哥曹操","next":{"data":"三哥关羽","next":{"data":"四弟张飞","next":null}}} 移除第'四弟张飞'后打印出链表: {"data":"二哥曹操","next":{"data":"三哥关羽","next":null}}
对这个是不是一眼就看懂了,其实上一个节点和下一个节点可以看成父子关系,对照着这个格式化后的数据在脑子里过一遍下面的操作:
1. 获取链表的第一个数据
2. 移除链表的第一个数据
3. 移除'四弟张飞'