Java 08 | 数据结构 - 单向链表 Singly Linked List
链表 Linked List 前面有介绍以array为基础搭建的列表,支持自动扩容, 各种插入,删除速度都很快. 这里再介绍另一种方案, 链表, 也可以实现列表自动扩容. 带链接的节点 链表的核心组成是带链接的节点, 每个节点就像火车车厢, 有钩子连接下一节车厢. 以int节点为例: public class IntNode { public int item; public IntNode next; public IntNode(int i, IntNode n) { item = i; next = n; } } next就是这个链接, 每一个节点就是其上一个节点的next. 使用嵌套类 这个节点作为一个相对独立的数据结构, 我们更希望让他单独作为一个类来维护. 再另外创建一个名为LinkedList的class与用户进行交互. 这样还有另一个好处就是提供一个命名为LinkedList的类给用户交互,用户更直观地知道自己是在调用链表。如果直接与node类交互,用户可能会困扰. 但同时考虑到这个node类只有LinkedList会调用,所以我们可以把node类嵌套进LinkedList中。 public class LinkedList<XXX> { private class OneNode { public XXX item; public OneNode next; public OneNode(XXX i, OneNode n) { item = i; next = n; } } private OneNode first; private int size; public LinkedList(XXX x) { first = new OneNode(x, null); size = 1; } //下面是各种方法....