Link 单向单端链表

Link 提供以下API

addFirst,removeFirst

getLength

hasNext

next

reset

insertAfter

removeAfter

indexOf

 

Node 是辅助结构,为了简便，没有使用标准的set，get方法，并且假设存储的内容是非负整数。

该结构实现单向单端链表最简化结构，只提供相对于此数据结构实现起来非常方便的方法。如只提供insertAfter而没有提供insertBefore。
 

 

class Node {
	private int value;
	private Node next;

	Node(int value) {
		this.value = value;
	}

	int value() {
		return value;
	}

	void next(Node next) {
		this.next = next;
	}

	Node next() {
		return next;
	}
}

 

class Link {
	private Node first;
	private int length;
	private Node current;

	void addFirst(int value) {
		Node node = new Node(value);
		node.next(first);
		first = node;
		length++;
	}

	int removeFirst() {
		if(first == null) return -1;
		int result = first.value();
		first = first.next();
		length--;
		return result;
	}

	int getLength() {
		return length;
	}

	boolean hasNext() {
		return current == null? first != null : current.next() != null;
	}

	int next() {
		current = (current == null? first : current.next());
		return current.value();
	}

	void reset() {
		current = null;
	}

	void insertAfter(int value) {
		if(current == null) addFirst(value);
		else {
			Node node = new Node(value);
			node.next(current.next());
			current.next(node);
			length++;
		}
	}

	int removeAfter() {
		if(current == null) return removeFirst();
		if(current.next() == null) return -1;
		int result = current.next().value();
		current.next(current.next().next());
		return result;
	}

	int indexOf(int value) {
		int i = 0;
		Node temp = first;
		while(temp != null) {
			if(temp.value() == value) return i;
			temp = temp.next();
			i++;
		}
		return -1;
	}
}

 

 

 

 

 

 

 

评论

1 楼 baibai326 2008-05-21  

逻辑有问题……