link.java

这里面包含有栈

package org.huhuiyu.datastructures;

/**
 * 链表类
 */
public class Link<T> {
	private Node<T> head; // 头节点
	private int count = 0; // 节点计数

	public Link() {
	}

	/**
	 * 添加节点数据
	 * 
	 * @param nodeData
	 *            要添加的节点数据
	 * @return 添加数据是否成功
	 */
	public boolean add(T nodeData) {
		boolean result = true;
		Node<T> add = new Node<T>(nodeData);
		if (isEmpty()) {
			// 如果链表是空的，就直接将添加的节点为头节点
			head = add;
		}
		else {
			// 否则就添加到结尾的位置
			Node<T> last = getNodeAt(count);
			last.setNext(add);
		}
		count++;
		return result;
	}

	/**
	 * 添加节点到指定位置
	 * 
	 * @param position
	 *            节点位置，必须满足1到size()+1的闭区间
	 * @param nodeData
	 *            添加的节点
	 * @return 添加是否成功
	 */
	public boolean add(int position, T nodeData) {
		boolean result = true;
		Node<T> add = new Node<T>(nodeData);
		if (isEmpty() || position == 1) {
			// 链表为空或者插入的位置是1都表示替换头节点为新添加的节点
			add.setNext(head);
			head = add;
			count++;
		}
		else if (position > 1 && position <= count + 1) {
			// 如果添加的位置合法，就取出要添加的节点的前一节点和相邻的节点
			Node<T> nodeBefore = getNodeAt(position - 1);
			Node<T> nodeAfter = nodeBefore.getNext();
			// 设定前一个节点的链接为添加的节点
			nodeBefore.setNext(add);
			// 将相邻的节点设定为添加节点的链接节点完成插入的动作
			add.setNext(nodeAfter);
			count++;
		}
		else {
			result = false;
		}
		return result;
	}

	/**
	 * 移除指定位置的节点
	 * 
	 * @param position
	 * @return 被移除的节点的数据
	 */
	public T removeAt(int position) {
		T data = null;
		if (isEmpty()) { // 空链表不用删除
			return null;
		}
		else if (position == 1) { // 删除头的方法
			data = head.getData(); // 获取头的数据
			head = head.getNext(); // 将头指向头的链接
			count--;
			return data;
		}
		else if (position > 1 && position <= count) {
			// 要删除的节点的前一个节点
			Node<T> nodeBefore = getNodeAt(position - 1);
			// 要删除的节点
			Node<T> nodeRemove = nodeBefore.getNext();
			// 要删除的节点的后一个节点
			Node<T> nodeAfter = nodeRemove.getNext();
			// 将前一个节点的连接指向后一个节点就完成了删除的任务
			nodeBefore.setNext(nodeAfter);
			data = nodeRemove.getData();
			count--;
			return data;
		}
		else { // 超出索引范围也不用删除
			return null;
		}
	}

	/**
	 * 获取链表存放的节点数量
	 * 
	 * @return 链表存放的节点数量
	 */
	public int size() {
		return count;
	}

	/**
	 * 获取链表是否为空
	 * 
	 * @return 是否为空链表
	 */
	public boolean isEmpty() {
		return count == 0;
	}

	/**
	 * 清空链表
	 */
	public void clear() {
		head = null;
		count = 0;
	}

	/**
	 * 获取指定位置的的节点数据
	 * 
	 * @param position
	 *            节点位置，必须满足1=<position<=count+1
	 * @return 指定节点的数据
	 */
	private Node<T> getNodeAt(int position) {
		Node<T> find = head;
		for (int i = 1; i < position; i++) {
			find = find.getNext();
		}
		return find;
	}

	/**
	 * 显示链表数据
	 */
	public void display() {
		for (Node<T> node = head; node != null; node = node.getNext()) {
			System.out.println(node.getData());
		}
	}

	public static void main(String[] args) {
		Link<Integer> link = new Link<Integer>();
		System.out.println("isEmpty:" + link.isEmpty());
		for (int i = 1; i < 10; i++) {
			link.add(i * 10);
		}
		System.out.println("size():" + link.size());
		link.display();
		System.out.println("++++++++++++++++");
		System.out.println("删除的数据是:" + link.removeAt(1));
		link.display();
		System.out.println("++++++++++++++++");
		System.out.println("添加数据:" + link.add(1, 10));
		link.display();
		System.out.println("++++++++++++++++");
		System.out.println("添加数据:" + link.add(100));
		link.display();
		link.clear();
		System.out.println("isEmpty:" + link.isEmpty());
	}
}