链表——一个可能很有趣的东西

       据书上说，链表是一种物理存储单元上非连续、非顺序的存储结构，而它的数据元素的逻辑顺序是通过链表的指针连接次序实现的。听着好深奥，其实和C语言的链表基本相同（可惜木有好好学C），它是由一系列的节点组成，而每个节点包括两个部分：数据域（存储数据），指针域（存储下一个节点的地址）。链表又有单向链表、双向链表和循环链表之分，其实也就是一个指针的指向问题：

                1.单向链表：前面一个节点指向后面一个节点。

                2.双向链表：前一个节点指向后一个节点，后一个节点也指向前一个节点；根节点向前指向null，向后指向下一个节点；尾节点向前指向上一个节点，向后指向null。

                3.循环链表：前一个节点指向后一个节点，后一个节点也指向前一个节点；根节点向前指向尾节点，向后指向下一个节点；尾节点向前指向上一个节点，向后指向根节点。

 

       好吧，废话不多说，直接上代码，代码才是王道：

首先是链表节点类：

/**
 * 双向链表节点类
 * @author ZhuMei
 */
public class doublyLinkedListNode {
	private Object obj;//节点内的数据对象
	private doublyLinkedListNode next;//对下一个节点的引用
	private doublyLinkedListNode previous;//对上一个节点的引用
	private int score;

	/**
	 * 构造方法1
	 */
	public doublyLinkedListNode(){
		
	}
	/**
	 * 构造方法2
	 */
	public doublyLinkedListNode(Object obj){
		this.obj = obj ;
	}
	
	/**
	 * 构造方法3
	 */
	public doublyLinkedListNode(Object obj, int score) {
		super();
		this.obj = obj;
		this.score = score;
	}
	
	/**
	 * 构造方法4
	 */
	public doublyLinkedListNode(Object obj, doublyLinkedListNode next,
			doublyLinkedListNode previous) {
		this.obj = obj;
		this.next = next;
		this.previous = previous;
	}
	
	public Object getObj() {
		return obj;
	}
	public void setObj(Object obj) {
		this.obj = obj;
	}
	public doublyLinkedListNode getNext() {
		return next;
	}
	public void setNext(doublyLinkedListNode next) {
		this.next = next;
	}
	public doublyLinkedListNode getPrevious() {
		return previous;
	}
	public void setPrevious(doublyLinkedListNode previous) {
		this.previous = previous;
	}
	public int getScore() {
		return score;
	}
	public void setScore(int score) {
		this.score = score;
	}
}

 

然后是链表的实现类（重点）：

/**
 * 双向链表实现类
 * @author ZhuMei
 *
 */
public class doublyLinkedList implements NodeLinkedListInterface{
	private int size = 0;// 节点总数

	private doublyLinkedListNode root = null;// 根节点，附初值null

	private doublyLinkedListNode last = null;// 尾节点，附初值null

	/**
	 * 添加节点的方法
	 * @param node新添加的节点对象
	 */
	public void add(doublyLinkedListNode node) {
		//判断root是否null
		if(null == root ){
			//让根节点和尾节点都指向新添加的节点
			root = node;
			last =node;
		}else{
			//向末尾添加节点
			last.setNext(node);
			//将last设为node的上一个节点
			node.setPrevious(last);
			//将新的节点作为尾节点
			last = node;
		}
		size++;
	}
	
	/**
	 * 在指定索引位置添加新节点
	 * @param node要添加的新节点
	 * @param index指定的索引位置
	 */
	public void add(doublyLinkedListNode node, int index) {
		if(index >= size || index<0){
			return;
		}
		//创建一个新节点
		doublyLinkedListNode oldNode = new doublyLinkedListNode();
		//获取指定索引位置的节点，将其赋给node
		 oldNode = this.get(index);
		 //如果将node设为根节点，即index==0
		 if(index == 0){
			 doublyLinkedListNode nextNode = root;
			 root = node;
			 root.setNext(nextNode);
			 nextNode.setPrevious(root);
		 }else{
			 //得到上一个节点
			 doublyLinkedListNode preNode = oldNode.getPrevious();
			 //设置新的节点关系
			 preNode.setNext(node);
			 node.setPrevious(preNode);
			 node.setNext(oldNode);
			 oldNode.setPrevious(node);	
		 }
		 size++;
	}

	/**
	 * 获取指定索引位置的节点对象
	 * 
	 * @param index指定的索引位置
	 * @return 返回节点对象，如果index的范围超出size，则返回null.
	 */
	public doublyLinkedListNode get(int index) {
		//如果超出索引，返回null
		if(index >= size || index<0){
		return null;
		}
		//让node为根节点
		doublyLinkedListNode node = root;
		//遍历至索引位置
		for(int i = 0; i<index;i++){
			//获取node节点的下一个节点
			node = node.getNext();
		}
		return node;
	}
	
	/**
	 * 移除指定的节点
	 * @param node要被移除的节点对象
	 */
	public boolean remove(doublyLinkedListNode node) {
		//用state标记，当state = true时，表示移除成功，返回true，当state = false 时，表示移除失败，返回false
		boolean state = false;
		int x = size; 
		//遍历数组，找出node
		for(int i = 0; i<size;i++){
			//取出索引为i的节点数据，赋给node1
			doublyLinkedListNode node1 = this.get(i);
			//当node = node1 时，执行移除
			if(node == node1){

				//当node1的下一个节点不为null时
				if(node1.getNext()!=null && node1.getPrevious()!=null){
				//得到节点node1的下一个节点，赋给nextNode
				doublyLinkedListNode nextNode = node1.getNext();
				System.out.println(nextNode);
				//得到节点node1的上一个节点，赋给preNode
				doublyLinkedListNode preNode = node1.getPrevious();
				//将nextNode设置为preNode的下一个节点
				preNode.setNext(nextNode);
				//将preNode设置为nextNode的上一个节点
				nextNode.setPrevious(preNode);
								}
				
				else if(node1.getNext()==null && node1.getPrevious()!=null){//当node1的下一个节点为null时
					//获得node1的上一个节点preNode
					doublyLinkedListNode preNode = node1.getPrevious();
					//让preNode的下一个节点指向null
					//preNode.setNext(null);
					last = preNode;
				}
				
				else if(node1.getNext()!=null && node1.getPrevious()==null){
					//获得node1的下一个节点nextNode
					doublyLinkedListNode nextNode = node1.getNext();
					//让nextNode的上一个节点指向null
					//nextNode.setPrevious(null);
					root = nextNode;
				}
				else{
					root = null;
				}
				size--;
				state = true;
			}
		}
				return state；
	}

	/**
	 * 移除指定所以位置的节点
	 * @param index指定要移除的节点索引
	 * @return 返回true和false，true表示移除成功，false表示移除失败
	 */
	public boolean remove(int index) {
		//若超出索引，返回false，表示移除失败
		if(index >=size && index <0){
			return false;
		}
		//让node为根节点
		doublyLinkedListNode node = root;
		
		//遍历至索引位置
		for(int i = 0; i < index-1; i++){
			//获取node的下一个节点
			node = node.getNext();
		}
		//next为index处的节点
		doublyLinkedListNode next = node.getNext();
		//将next指向index+1处的节点
		next =next.getNext();
		//设置node（index-1）的下一个节点是index+1
		node.setNext(next);
		size--;
		return true;
	}
	
	/**
	 * 获取双链表中存储的元素总数
	 * @return 返回size的值，如果为0则表示链表中没有节点
	 */
	public int getSize() {
		return size;
	}
	
	
}

 最后是主函数（应用实现类里面的方法）：

public class doublyManager {

	/**
	 * @param ZhuMei
	 */
	public static void main(String[] args) {
		
		//实例化一个doublyLinkedList对象
		NodeLinkedListInterface nll = new doublyLinkedList();
			//实例化对象，再添加
			doublyLinkedListNode node1 = new doublyLinkedListNode("海绵宝宝",97);
			doublyLinkedListNode node2 = new doublyLinkedListNode("派大星",95);
			doublyLinkedListNode node3 = new doublyLinkedListNode("蟹老板",68);
			doublyLinkedListNode node4 = new doublyLinkedListNode("章鱼哥",61);
			doublyLinkedListNode node5 = new doublyLinkedListNode("珊迪",90);
			doublyLinkedListNode node6 = new doublyLinkedListNode("痞老板",59);
			doublyLinkedListNode node7 = new doublyLinkedListNode("小蜗",92);
			nll.add(node1);
			nll.add(node2);
			nll.add(node3);
			nll.add(node4);
			nll.add(node5);
			nll.add(node6);
			nll.add(node7);
		
		//初始化节点n
		doublyLinkedListNode n = new doublyLinkedListNode("泡芙老师",91);
		//将n添加到索引为6的位置
		nll.add(n, 0);
		
		
		//输出
		System.out.print("********移除之前的人物排列为：\n");
		for(int i=0;i<nll.getSize();i++){
			doublyLinkedListNode node = nll.get(i);
			System.out.println(node.getObj()+"	"+node.getScore());
		}
		
		//移除索引为7的节点
		nll.remove(7);
		//移除节点n
		nll.remove(n);
		
		//输出
		System.out.print("\n********移除之后的人物排列为：\n");
		for(int i=0;i<nll.getSize();i++){
			doublyLinkedListNode node = nll.get(i);
			System.out.println(node.getObj()+"	"+node.getScore());
		}

	}
	
}

       至于链表实现类的接口的代码就不用贴了，然后说一句：《海绵宝宝》真的好看呢，尽管好久都没看了，不过真的很怀念。

       练习中遇到的困难和解决：

              做链表练习的时候老是遇到空指针异常，这让我很是忧桑啊，不过这些异常都是有原因的，总体来说，就是考虑不周，比如在“移除指定的节点”的方法中，开始的时候就没有考虑到如果移除的节点是根节点或尾节点的情况，导致空指针异常。当然，还有很多犯了同样的错误，不过我倒是觉得犯错并没有什么，它甚至还会是你进步的关键，在编程中，调试改错也是一种能力，而且可以大大地提高对编程的认识和编程能力。

       练习的不足：到现在还没有将链表排序实现（捣鼓了好久，没有效果，得去问大神啊）。

       还想说说做完练习的感想：嗯~这篇总结和练习是拖了好久的了，练习之前实现了部分，后来由于种种原因停了，现在把搞定之后有一种如释重负的感觉，虽然今天花了不少时间，但我自己感觉我在自己琢磨的过程中有收获，这就够了，我没有一些人的聪明，编个程序要花我很多时间，但是我既然选择了，就会认真地做，虽然有时会晚一点。

       OK！又搞定了一篇总结，先睡觉咯，明天继续奋斗…………