Java实现单向链表

27 May 2014

概要

早先发过一篇用C实现的单向链表——《实用的单向链表》，今天用Java实现了一遍。下面将具体讲述在编写这段代码时的一些思考。

面向对象

如果从单向链表的角度而言，其原理（结构）都是相同的，但使用Java和C实现的一个巨大的不同在于Java是一门面向对象的语言，需要考虑如何将链表的实现封装成为类。

我们不能向C语言那样，建立一个结构体，再加上一句typedef做出类似面向对象一样的封装。在Java中哪些成员变量或方法要声明为private、public等等都需要去设计和思考（至少多出这么一步）。另外，Java会生成实例，并用这个实例的方法去操作，这里不在像C语言那样一切都是分离的，Java要围绕着实例来进行。

代码

public class Node {
	private Object element;
	private Node next;
	
	public Node() {
		this.next = null;
	}
	
	public void setElement(Object element) {
		this.element = element;
	}
	
	public Object getElement() {
		return element;
	}
	
	public Node getNext() {
		return next;
	}
	
	public Node newNode(Object element) {
		Node newNode = new Node();
		newNode.element = element;
		return newNode;
	}
	
	public void insert(Node target, Object element) {
		Node newNode = newNode(element);
		newNode.next = target.next;
		target.next = newNode;
	}
	
	public Node find(Object element) {
		Node currentNode = this;
		while (currentNode.next != null) {
			currentNode = currentNode.next;
			if (currentNode.element.equals(element))
				return currentNode;
		}
		return null;
	}
	
	private Node preNode(Node target) {
		Node currentNode = this;
		while (currentNode.next != null) {
			if (currentNode.next.equals(target))
				return currentNode;
			currentNode = currentNode.next;
		}
		return null;
	}
	
	public void delete(Node target) {
		Node preNode = preNode(target);
		preNode.next = target.next;
		target.next = null; //make sense?
	}
	
	public void showNode() {
		Node currentNode = this;
		while (currentNode.next != null) {
			currentNode = currentNode.next;
			System.out.print(currentNode.element + " ");
		}
	}
}

这里就不展示测试的代码了。在编写find和preNode方法时，有一点引起了我的兴趣，如果没有找到任何的结果，是返回null，还是抛出一个空指针异常呢（throw new NullPointerException("No such element!");）？

关于null处理的思考

这里考虑到的是如果返回null，调用者需要事先判断返回结果是否为null，而如果采取抛出异常来处理，那么直接使用try-catch块即可方便的解决。

这个问题真的有一点见仁见智的感觉，在网上搜寻了一些回答，都各有各的道理。

比如CSDN的这一讨论，有一位回答者说：

如果你要作为封装使用，建议你抛异常

如果你只是被使用的的一个基本方法，返回个null就可以了，让调用者去判断。

似乎比较有道理，再来看一看神牛Byvoid的解答——《如何处理C++构造函数中的错误——兼谈不同语言的错误处理》：

我的观点是，用异常来表示真正的、而且不太可能发生的错误。所谓不太可能发生的错误，指的是真正难以预料，但发生了却又不得不单独处理的，譬如内存耗尽、读文件发生故障。而在一个字符串中查找一个子串，如果没有找到显然应该是用一个特殊的返回值（如-1），而不应该抛出一个异常。

一句话来概况就是不要用异常代替正常的控制流，只有当程序真的「不正常」的时候，才使用异常。反过来说，当程序真正发生错误了，一定要使用异常而不是返回一个错误代码，因为错误代码总是倾向于被忽略。如果要保证一个以返回值来表示错误代码的函数的错误正确地向上传递，需要在每个调用了可能产生错误的函数后面都判断一下是否发生了错误，一旦发生了不可解决的错误，就要终止当前函数（并释放当前函数申请的资源），然后向上传递错误。这样一来错误处理代码会被重复地写好几遍，十分冗杂。

这个解释更加具体，即真正不易发生的事情在用异常（很明显，我的代码那部分不属于这一范围）。再提取其中心观点：不要用异常代替正常的控制流，只有当程序真的「不正常」的时候，才使用异常。

在segmentfault看到的这一个回答更是讲到了NullObject模式，当然这种用法是使用在更加复杂的情况中。

列举上述回答，仅仅是作为一个参考，但综上可得，在我的代码中：

它仅仅是一个基本方法。
它并不是那些不易发生的事情。
它还没有复杂到使用那些高级的处理方法（如NullObject模式）。

所以，代码中我返回了null，并使调用者去处理这一流程。

小结

一小段代码的实现虽然看似简单，但一些细节的思考也会让人有所收获。这就像重构，通过对自己代码的思考，获得新的经验（温故而知新），提高自身的编程素养。

我想这一点对任何程序员来说都是至关重要的。

java 19

Java 19