带头结点的单链表【链表问题】

带头结点的单链表【链表问题】。

/*
 * 带头结点的单链表
 */
public class SinglyList {

	public Node head; // 创建头结点

	/*
	 * 构造函数1，只有一个头结点
	 */
	public SinglyList() {
		this.head = new Node();
	}

	/*
	 * 构造函数2，依次将values中的值填入单链表中
	 */
	public SinglyList(T[] values) {
		this(); // 构造一个空的单链表
		Node rear = this.head; // 为空的单链表设置头结点
		for (int i = 0; i < values.length; i++) {
			rear.next = new Node(values[i], null); // 尾插入节点
			rear = rear.next; // 尾指针指向尾节点
		}
	}

	/*
	 * 判断单链表是否为空，O（1）
	 */
	public boolean IsEmpty() {

		return this.head.next == null; // 因为这是带头结点的单链表，所以判断为空的条件是头结点以后为空
	}

	/*
	 * 得到单链表第i个节点的值，并返回
	 */
	public T get(int i) {
		Node cur = this.head.next; // 用cur指向当其节点
		for (int j = 0; cur != null && j < i; j++) { // 这里一定要注意，i是不能越界的(这里是指大于链表长度），很多新手都不注意这里，容易出错
			cur = cur.next;
		}
		return (i >= 0 && cur != null) ? cur.data : null; // 这里也设置了越界保险，当i（小于零，或者链表为空）都要返回空，否则返回对应元素
	}

	public void set(int i, T x) {

	}

	/*
	 * 求链表长度，复杂度为O(1)
	 */
	public int size() {

		int length = 1; // 头结点算是第一个节点
		Node p = head.next;
		while (p != null) {
			length++;
			p = p.next;
		}
		return length;

	}

	/*
	 * 将单链表制作成字符串形式，然后返回，这个方法，在测试的时候，非常有用
	 */
	public String toString() {
		String str = this.getClass().getName() + "("; // 返回类名
		for (Node p = this.head.next; p != null; p = p.next) { // 遍历单链表
			str += p.data.toString();
			if (p.next != null)
				str += ","; // 不到最后结点，要用分隔号隔开

		}
		return str + ")"; // 返回
	}

	/*
	 * 在指定位置进行插入,将x插入到第i个元素之后（这里第一个元素是指head），插入后x的序号为i(因为从0开始的)
	 */
	public Node insert(int i, T x) {
		if (x == null)
			throw new NullPointerException("x==null"); // 如果要插入的元素为空，则抛出空异常
		Node front = this.head;
		for (int j = 0; front.next != null && j < i; j++) // 寻找到第i个节点
			front = front.next;
		front.next = new Node(x, front.next); // 将x节点设为front之后
		// 一开始我很不习惯直接用这种方式(直接新建一个然后赋值），我一般是新建一个插入节点
		// 然后再赋值给front.next，但是后来发现上面这种方法更好，省去了起名字的麻烦，而且形式也很简单
		return front.next; // 返回插入结点
	}

	/*
	 * 插入操作，默认插入到最后一位 直接调用上一个插入方法， 因为上面插入方法中，有容错机制，当你的i大于链表长度时，它就默认在末尾插入
	 * 下面这个方法，显然就利用了这一点
	 */
	public Node insert(T x) {

		return insert(Integer.MAX_VALUE, x);

	}

	/*
	 * 删除第i位结点
	 */
	public T remove(int i) {
		Node front = this.head;
		for (int j = 0; front.next != null && j < i; j++)
			front = front.next; // 遍历并找到第i位元素，或者是最后一位（当i大于链表长度时）
		if (i >= 0 && front.next != null) { // 确认i的合法性，如果i小于0，会跳过上面的for语句
			T old = front.next.data;
			front.next = front.next.next; // 删除操作

			return old;
		}
		return null; // 如果没有执行上面的if语句，说明i小于0，或者大于链表长度，前者错误，后者不用删除
	}

	/*
	 * 根据关键字进行删除
	 */
	public T remove(T key) {
		Node p = this.head;
		if (head.data == key) {
			head = head.next;
			return key;
		}
		while (!p.next.data.equals(key) && p.next.next != null) {
			p = p.next;
		}
		if (p.next.data.equals(key)) {
			p.next = p.next.next;
			return key;
		}
		return null;

	}

	/*
	 * 清空链表
	 */
	public void clear() {
		this.head.next = null;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		String[] s = { "aa", "bb", "cc" };
		SinglyList test = new SinglyList(s);
		test.remove("aa");
		System.out.println(test.toString());

	}

}

1、对于上面的在第i个元素之后插入的方法，测试一下：

		String[] s = { "aa", "bb", "cc" };
		SinglyList test = new SinglyList(s);
		test.insert(2, "ee");
		System.out.println(test.toString());

显示结果如下：

ee插入到了第2个元素之后，但是如果是按序号来算的话，那么它就是2号（因为第一位是0号）

2、测试上面的移除操作

		String[] s = { "aa", "bb", "cc" };
		SinglyList test = new SinglyList(s);
		test.remove(1);
		System.out.println(test.toString());

结果显示：

删除了“bb”，这里的i是序号，不是个数（如果算上头结点的话）