舒の随想日记

为了复习链表的相关知识，用JAVA写了一个简单的链表实现。
Chain.java:

public class chain {
	private int length;
	private node first;

	public chain() {
		length = 0;
	}

	public boolean isEmpty() {
		return length == 0;
	}

	public int getLength() {
		return length;
	}

	public node getLast() {
		node current = first;
		while (current.getNext() != null) {
			current = current.getNext();
		}
		return current;
	}

	public void clear() {
		while (first != null) {
			first = first.getNext();
		}
		length = 0;
	}

	public Object find(int k) {
		if (k < 1) {
			return -1;
		}
		node current = first;
		int index = 1;
		while (index < k && current != null) {
			current = current.getNext();
			index++;
		}
		if (current != null) {
			return current.getData();
		}
		return -1;
	}

	public int search(Object x) {
		node current = first;
		int index = 1;
		while (current != null && !(current.getData().equals(x))) {
			current = current.getNext();
			index++;
		}
		if (current != null) {
			return index;
		}
		return -1;
	}

	public void output() {
		node current = first;
		while (current != null) {
			System.out.print(current.getData() + "  ");
			current = current.getNext();
		}
		System.out.println();
	}

	public void append(Object x) {
		node y = new node();
		y.setData(x);
		y.setNext(null);
		if (length == 0) {
			first = y;
		} else {
			node current = getLast();
			current.setNext(y);
		}
		length++;
	}

	public void add(int k, Object x) {
		if (k < 0) {
			noPosition();
			return;
		}
		node p = first;
		for (int i = 1; i < k && p != null; i++) {
			p = p.getNext();
		}
		if (k > 0 && p == null) {
			noElement();
			return;
		}
		node y = new node();
		y.setData(x);
		if (k > 0) {
			y.setNext(p.getNext());
			p.setNext(y);
		} else {
			y.setNext(first);
			first = y;
		}
	}

	public void delete(int k) {
		if (k < 1 || first == null) {
			noElement();
			return;
		}
		node p = first;
		if (k == 1) {
			first = first.getNext();
		} else {
			node q = first;
			for (int i = 1; i < k - 1 && q != null; i++) {
				q = q.getNext();
			}
			if (q == null || q.getNext() == null) {
				noElement();
				return;
			}
			p = q.getNext();
			q.setNext(p.getNext());
		}
		length--;
	}

	private void noElement() {
		System.out.println("No such element.");
	}

	private void noPosition() {
		System.out.println("No such position.");
	}
}

class node {
	private Object data;
	private node next;

	public Object getData() {
		return data;
	}

	public void setData(Object x) {
		data = x;
	}

	public node getNext() {
		return next;
	}

	public void setNext(node n) {
		next = n;
	}
}

ChainMain.java:

public class chainMain {
	public static void main(String[] args) {
		chain c = new chain();
		System.out.println(c.isEmpty() ? "Empty" : "Not empty");
		// Initialize a chain with 1 to 10
		for (int i = 1; i <= 10; i++) {
			c.append(i);
		}
		System.out.println(c.isEmpty() ? "Empty" : "Not empty");
		System.out.println("The length of the chain is " + c.getLength());
		// Show the chain,it should be: 1,2,3,...,10
		c.output();
		// Add an element at the beginning
		c.add(0, 100);
		c.output();
		// Add an element which should be the 3rd
		c.add(2, 300);
		c.output();
		// Find the 5thelement and output it
		System.out.println("The 5th element is " + c.find(5));
		System.out.println("6 is in the " + c.search(6) + "th position.");
		System.out.println("Before deleting the 7th element:");
		c.output();
		// Delete the 7th element
		c.delete(7);
		System.out.println("After deleting the 7th element:");
		c.output();
		// Clear all the chain
		c.clear();
		System.out.println(c.isEmpty() ? "Empty" : "Not empty");
	}
}
/*Output:
	Empty
	Not empty
	The length of the chain is 10
	1  2  3  4  5  6  7  8  9  10
	100  1  2  3  4  5  6  7  8  9  10
	100  1  300  2  3  4  5  6  7  8  9  10
	The 5th element is 3
	6 is in the 8th position.
	Before deleting the 7th element:
	100  1  300  2  3  4  5  6  7  8  9  10
	After deleting the 7th element:
	100  1  300  2  3  4  6  7  8  9  10
	Empty
*/