java链表简单介绍

  链表是一种物理存储单元上非连续、非顺序的存储结构；数据之间的逻辑顺序是靠链表中的指针来实现的。而链表本身由结点组成、结点可以在运动时动态生成；
   结点：由数据域和指针域组成。

  链表分为单向链表和双向链表


单向链表：每个结点由存储数据元素的数据域和指向下一结点的指针域组成。
例：单链表的结点结构

/**
	 * @param 单链表结点类
	 */
    //节点类的数据对象
	private Object obj;
	//对下一节点的引用
	private LinkNode next;
	//在创建节点对象时就传入节点中的数据对象
	public LinkNode(Object obj){
		this.obj=obj;
	}
	
	public Object getObj(){
		return obj;
	}
	
	public void setObj(Object obj){
		this.obj=obj;
	}
	
	public LinkNode getNext(){
		return next;
	}
	
	public void setNext(LinkNode next){
		this.next=next;
	}

而双向链表是单向链表的改进、因为在单向链表中，我们只能从前往后使用，不能从后往前使用；所以双向链表中、我们在结点中可以增加一个指向前结点的指针；这样，我们就可以随便地使用链表中的数据了。
结点表示:

private Object obj;
		//对下一节点的引用
		private DoubleLinkNode child;
		//对上一节点的插入
	    private DoubleLinkNode parent;
		//在创建节点对象时就传入节点中的数据对象
		public DoubleLinkNode(Object obj){
			this.obj=obj;
		}
		
		public Object getObj(){
			return obj;
		}
		
		public void setObj(Object obj){
			this.obj=obj;
		}
		
		public DoubleLinkNode getChild(){
			return child;
		}
		
		public void setChild(DoubleLinkNode child){
			this.child=child;
		}
		
		public DoubleLinkNode getParent(){
			return parent;
		}
		
		public void setParent(DoubleLinkNode parent){
			this.parent=parent;
		}

链表的使用：
链表最基本的使用就是实现查找、插入、删除、合并、排序、统计、或简单的计算。

其链表的插入：

/**
	 * 在指定地点插入节点
	 * 
	 * @param Index
	 * @param obj
	 */
	public void insertIndexObj(int index, Object obj) {
		// 判断插入的位置是否正确
		if (this.getLength() < index || index < 0) {
			// 抛出异常
			throw new java.lang.RuntimeException("下标越界" + index + "链表大小："
					+ this.getLength());
		} else {
			// 创建一个新的节点
			DoubleLinkNode newNode = new DoubleLinkNode(obj);
			// 调用方法，得到当前索引位置的结点
			DoubleLinkNode node = this.getLinkNode(index);
			// 插入操作前进行判断是否为空链表
			if (index == 0) {
				// 将头节点指向新节点
				front = newNode;
			} else {
				// 插入时，先得到其索引值位置的父节点
				DoubleLinkNode fNode = node.getParent();
				// 将新节点的上节点指针指向fNode
				newNode.setParent(fNode);
				// 将fNode节点的子节点指向新节点
				fNode.setChild(newNode);
			}
			// 将新节点的子节点指向当前索引值位置的节点
			newNode.setChild(node);
			// 将索引位置的节点的父节点指向新节点
			node.setParent(newNode);
		}
	}

如得到链表的长度：

/**
	 * 得到链表的长度
	 * 
	 * @return
	 */
	public int getLength() {
		int count = 0;
		if (null == front) {
			return count;
		}
		DoubleLinkNode node = front.getChild();
		// 遍历链表
		while (null != node) {
			count++;
			node = node.getChild();
		}
		return count + 1;
	}

评论

1 楼 小蘑菇的梦想 2013-04-30  

排序呢！！！！！！