12.9 链表 - 综合汇总----???

demo 本章节综合汇总信息，在这个demo都可以体现----看的有点懵～！！～

interface ILink<E> {									// 链表公共标准
	/**
	 * 向链表中进行数据的存储，每个链表所保存的数据类型相同，不允许保存null数据
	 * @param e 要保存的数据
	 */
	public void add(E e);
	/**
	 * 获取链表中集合元素的保存个数
	 * @return 元素个数
	 */
	public int size() ; 
	/**
	 * 判断当前是否为空链表（长度为0 ）
	 * @return 如果是空链表返回true，否则返回false
	 */
	public boolean isEmpty();
	/**
	 * 获取链表中的全部内容，该内容将以数组的形式返回
	 * @return 如果链表有内容则返回与保存元素个数相当的数组，如果没有内容保存返回null
	 */
	public Object[] toArray() ;
	/**
	 * 根据索引获取链表中的指定元素内容
	 * @param index 要获取元素的索引
	 * @return 指定索引位置的数据
	 */
	public E get(int index) ;
	/**
	 * 修改指定索引中的数据内容
	 * @param index 要修改的数据索引
	 * @param data 要替换的新内容
	 */
	public void set(int index, E data);
	/**
	 * 查询指定内容是否存在，要求查询对象所在类覆写equals()方法
	 * @param data 要查找的数据
	 * @return 数据存在返回true，否则返回false
	 */
	public boolean contains(E data);
	/**
	 * 删除指定内容的数据，需要利用equals()方法进行比较
	 * @param data 要删除的数据
	 */
	public void remove(E data);
	/**
	 * 清空链表中的所有元素
	 */
	public void clean();
}


class LinkImpl<E> implements ILink<E> {


	// 使用内部类的结构进行定义，这样外部类与内部类可以直接进行私有成员访问
	private class Node<E> {								// 内部类封装，对外部不可用
		private E data;									// 节点保存数据
		private Node<E> next;							// 保存节点引用----???
		public Node(E data) {							// 创建节点时保存数据
			this.data = data;
		}
		/**
		 * 保存新创建的节点，保存的依据是判断当前节点的next属性是否为空
		 * @param newNode 要保存的新节点
		 */
		public void addNode(Node<E> newNode) { 			// 保存新的Node数据
			if (this.next == null) { 					// 当前节点的下一个节点为null
				this.next = newNode; 					// 保存当前节点
			} else {
				this.next.addNode(newNode);				// 递归到合适的位置保存数据
			}
		}
		/**
		 * 将链表中的全部元素保存到对象数组之中
		 */
		public void toArrayNode() {
			// 将当前节点的数据取出保存到returnData数组之中，同时进行索引自增
			LinkImpl.this.returnData[LinkImpl.this.foot++] = this.data;
			if (this.next != null) { 					// 还有下一个数据
				this.next.toArrayNode();				// 递归调用
			}
		}
		/**
		 * 根据节点索引获取元素
		 * @param index 要获取的索引编号，该索引编号一定是有效编号
		 * @return 索引对应的数据
		 */
		public E getNode(int index) {
			if (LinkImpl.this.foot++ == index) { 		// 索引相同
				return this.data; 						// 返回当前数据
			} else {									// 继续向后获取数据
				return this.next.getNode(index);
			}
		}
		/**
		 * 修改指定索引对应的数据内容
		 * @param index 要修改的索引
		 * @param data 要替换的内容
		 */
		public void setNode(int index, E data) {
			if (LinkImpl.this.foot++ == index) { 		// 索引相同
				this.data = data; 						// 修改数据
			} else {
				this.next.setNode(index, data);			// 后续节点操作
			}
		}
		/**
		 * 判断指定的数据是否存在
		 * @param data 要查找的数据
		 * @return 数据存在返回true，否则返回false
		 */
		public boolean containsNode(E data) {
			if (this.data.equals(data)) { 				// 对象比较
				return true;							// 数据存在
			} else {
				if (this.next == null) { 				// 没有后续节点
					return false; 						// 没有找到数据
				} else { 								// 后续节点判断
					return this.next.containsNode(data);
				}
			}
		}
		/**
		* 删除指定数据对应的节点内容
		* @param previous 要删除节点的上一个节点
		* @param data 要删除的数据
		*/
		public void removeNode(Node previous, E data) {
			if (this.data.equals(data)) {				// 数据内容比较
				previous.next = this.next; 				// 【删除】空出当前节点
			} else {									// 数据内容不匹配
				if (this.next != null) { 				// 有后续节点
					this.next.removeNode(this, data); 	// 向后继续删除
				}
			}
		}

	}





	// --------------- 以下为Link类中定义的结构 ------------------
	private Node<E> root ;							// 保存根节点信息 
	private int count ; 							// 保存元素个数
	private int foot; 								// 数组操作脚标
	private Object[] returnData; 					// 返回数据保存

	@Override
	public void add(E e) {							// 方法覆写							
		if (e == null) { 							// 保存的数据为nul时
			return; 								// 方法调用直接结束
		}
		// 数据本身是不具有节点先后的关联特性的，要想实现关联处理就必须将数据包装在Node类之中
		Node<E> newNode = new Node<E>(e); 			// 创建一个新的节点
		if (this.root == null) { 					// 现在没有根节点
			this.root = newNode; 					// 第一个节点作为根节点
		} else { 									// 根节点存在
			this.root.addNode(newNode);				// 由Node类保存新节点
		}
		this.count ++ ; 							// 保存元素个数自增
	}

	@Override
	public int size() {
		return this.count;							// 返回元素个数
	}

	@Override
	public boolean isEmpty() {
		return this.count == 0;						// 判断集合长度是否为0
	}
	
	@Override
	public Object[] toArray() {
		if (this.isEmpty())	{						// 空集合
			throw new NullPointerException("集合内容为空") ;
		}
		this.foot = 0 ; 							// 脚标清零
		this.returnData = new Object [this.count] ;	// 根据已有长度开辟数组
		this.root.toArrayNode() ;					// 利用Node类进行递归数据获取
		return this.returnData ;					// 返回全部元素
	}
	
	@Override
	public E get(int index) {
		if (index >= this.count) { 					// 索引不在指定的范围之内
			throw new ArrayIndexOutOfBoundsException("不正确的数据索引");
		}
		this.foot = 0; 								// 重置索引的下标
		return this.root.getNode(index);			// 交由Node类查找
	}
	
	@Override
	public void set(int index, E data) {
		if (index >= this.count) { 					// 索引不在指定的范围之内
			throw new ArrayIndexOutOfBoundsException("不正确的数据索引");
		}
		this.foot = 0; 								// 重置索引的下标
		this.root.setNode(index, data); 			// Node类修改数据
	}
	
	@Override
	public boolean contains(E data) {
		if (data == null) {
			return false; 							// 没有数据返回false
		}
		return this.root.containsNode(data); 		// 交由Node类判断 
	}
	
	@Override
	public void remove(E data) {
		if (this.contains(data)) { 					// 判断数据是否存在
			if (this.root.data.equals(data)) { 		// 根节点为要删除节点
				this.root = this.root.next; 		// 修改根节点引用
			} else { 								// 交由Node类负责删除
				this.root.next.removeNode(this.root, data);
			}
			this.count--;							// 元素数量减少 
		}
	}
	
	@Override
	public void clean() {
		this.root = null ; 							// 断开根节点引用
		this.count = 0 ; 							// 元素个数清零
	}
}

public class JavaDemo {
	public static void main(String args[]) {
		ILink<String> link = new LinkImpl<String>();	// 实例化链表对象
		//System.out.println("数据保存前链表元素个数：" + link.size());
		link.add("魔乐科技软件学院");						// 链表中保存数据
		link.add("www.mldn.cn");						// 链表中保存数据
		link.add("www.yootk.com");						// 链表中保存数据
		System.out.println(link.contains("www.mldn.cn"));	// 数据查询
		System.out.println(link.contains("张老师"));	// 数据查询

		//System.out.println("数据保存后链表元素个数：" + link.size());
//		Object results [] = link.toArray() ;			// 获取全部保存数据
//		for (Object obj : results) {
//			String str = (String) obj ;					// 确定为String类型，强制转型
//			System.out.print(str + "、");				// 输出对象
//		}
//		link.set(1, "魔乐科技软件学院（MLDN）:www.mldn.cn");	// 修改内容
//		System.out.println(link.get(1));				// 获取第2个元素
//		System.out.println(link.get(3));				// 错误的索引
	}
}