1.前言
我们将LinkdList视作链表, 底层设计了内部类Node类, 我这里依然没有用到泛型, 其实加上泛型依然很简单, 即将Node节点的数据域的类型由Int转换为E(<E>), 我在此不做赘述.同时实现了增删查改, 遍历等操作.
2.链表(无哨兵)的代码实现
public class LinkListTest implements Iterable<Integer>{ //头指针 static Node head; //内部类 private static class Node{ //数据域 int value; //指针域 Node next; public Node(int value, Node nest) { this.value = value; this.next = nest; } } //头插法 public void addHead(int value) { Node p = new Node(value, null); p.next = head; head = p; } //遍历链表 : 方式1 public void Traversal1() { Node p = head; while (p != null) { System.out.println("该节点的值是" + p.value); p = p.next; } } //获取指定索引位置上的节点的值 public int get(int index) { Node p = findIndex(index); return p.value; } //返回指定索引的节点 private Node findIndex(int index) { int count = 0; Node p = head; while (count < index) { if (p == null) { throw new IllegalArgumentException(); } p = p.next; count++; } return p; } //找到尾节点 private Node findLast() { //如果是空链表, 压根找不到最后的节点 if (head == null) { return null; } Node p; //当p.next == null时, 则p指向了尾节点 for (p = head; p.next != null; p = p.next) { ; } return p; } //尾插法 public void addLast(int value) { Node last = findLast(); //如果是一个空链表 if (last == null) { addHead(value); return; } last.next = new Node(value, null); } public void Insert(int index, int value) { //如果插入的是第一个节点 if (index == 0) { addHead(value); return; } //先找到index位置处的前一个节点 Node p = findIndex(index - 1); p.next = new Node(value, p.next); } //删除最后一个节点 public void removeFrist() { //如果是空链表 if (head == null) { throw new RuntimeException(); } //找到头节点 Node p = findIndex(0); head = p.next; } public void remove(int index) { //如果是空链表 if (head == null) { throw new RuntimeException(); } //如果要删除的是最后一个节点, 那么调用removeFrist()方法 if (index == 0) { removeFrist(); return; } Node p = findIndex(index - 1); p.next = p.next.next; } //使用迭代器进行遍历 @Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { Node q = head; @Override public boolean hasNext() { if (q != null) { return true; } return false; } @Override public Integer next() { int value = q.value; q = q.next; return value; } }; } //使用函数式接口进行链表的遍历 public void Traverse2(Consumer<Integer> consumer) { for (Node p = head; p != null; p = p.next) { consumer.accept(p.value); } } }
3. 注
- foreach循环的底层使用了迭代器.所以如果一个类的对象想要使用foreach循环遍历，则其类必须实现Iterable接口，并重写其中的抽象方法(iterable()).在其return语句中实现了匿名内部类，重写了Iterator接口的两个重要的抽象方法，hasNext()和next().不断迭代将next函数返回的值赋值给临时变量element.
- 在Traverse2方法中，我们使用了函数式接口来进行链表的遍历
public void Traverse2(Consumer<Integer> consumer) { for (Node p = head; p != null; p = p.next) { consumer.accept(p.value); } } @Test public void test3() { LinkListTest l = new LinkListTest(); l.addLast(12); l.addLast(23); l.addLast(34); l.addLast(45); l.addLast(56); l.addLast(67); l.Traverse2(value -> { System.out.println("该节点的值为" + value); }); l.Traverse2(System.out :: println); }
形参是一个消费型的函数式接口，实参我们可以传入接口的实现类的对象(lambda表达式或者方法引用实现).
