模拟LinkedList实现的链表(无哨兵)

1.前言

我们将LinkdList视作链表, 底层设计了内部类Node类, 我这里依然没有用到泛型, 其实加上泛型依然很简单, 即将Node节点的数据域的类型由Int转换为E(<E>), 我在此不做赘述.同时实现了增删查改, 遍历等操作.

2.链表(无哨兵)的代码实现

java">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;}//遍历链表 : 方式1public 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;}//使用迭代器进行遍历@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node q = head;@Overridepublic boolean hasNext() {if (q != null) {return true;}return false;}@Overridepublic 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);}}@Testpublic 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表达式或者方法引用实现).