链表总结~发现数据结构的趣味性

链表有一系列的结点组成，其中单向链表每个结点包括两个部分，一个是存储数据元素的数据域，和指向下一个结点的指针域，而双向链表包含了存储直接子结点地址的右链域，和直接存储父节点地址的左链域，以及存储数据的数据域。下面分别用代码实现单链表与双向链表。

 

/*
 * 单向链表结点类
 * @author miaofei
 */
public class singleLink {
private Object obj;//节点内的数据对象
private singleLink next;//对下一个节点的引用
//在创建节点对象的时候就传入节点中的数据对象

public singleLink(Object obj) {
	super();
	this.obj = obj;
}
public Object getObj() {
	return obj;
}
public void setObj(Object obj) {
	this.obj = obj;
}
public singleLink getNext() {
	return next;
}
public void setNext(singleLink next) {
	this.next = next;
}

	
}

 用快捷方式添加的构造方法，不知为什么会有super()；求教大神！！

单向链表类

/**单向链表类
 ** @author miaofei
*/
public class LinkedNode {

	
	public static void main(String[] args) {
		LinkedNode ln = new LinkedNode();
		//创建链表
		singleLink root = ln.createLink();
		//遍历
		ln.printLinklist(ln.root);
       
	}
	//创建链表
	public singleLink createLink(){
		String s = "根节点";
		root = new singleLink(s);
		singleLink n1 = new singleLink("first");
		singleLink n2 = new singleLink("second");
		singleLink n3 = new singleLink("third");
		singleLink n4 = new singleLink("forth");
		root.setNext(n1);
		n1.setNext(n2);
		n2.setNext(n3);
		n3.setNext(n4);
		return root;
		
	}
	//遍历链表
	public void printLinklist(singleLink root){
		if(null!=root){
			Object data = root.getObj();
			System.out.println(data);
			singleLink temp = root.getNext();
			printLinklist(temp);
			
		}
		
	}

}

 下面是双向链表，实现了添加，删除的各两种方法，还有从小到大的排序

package NodeLink;

public class NodeLinkedList implements NodeLinkedListInterface {
	private int size = 0;// 节点总数

	private Node root = null;// 根节点

	private Node last = null;// 尾节点
//根据节点来给链表添加新的节点
	public void add(Node node) {
		// 判断root是否为null
		if (null == root) {
			// 让根节点和尾节点都指向新添加的节点
			root = node;
			last = node;
		} else {
			// 向末尾添加节点
			last.setNext(node);
			// 将设为上一个节点
			node.setPrevious(last);
			// 将新的节点作为尾节点
			last = node;
		}
		size++;
	}

	/* (non-Javadoc)
	 * @see cn.netjava.lesson13.NodeLinkedListInterface#add(cn.netjava.lesson13.Node, int)
	 */
	@Override
	//给定节点与插入位置来添加节点
	public void add(Node node, int index) {  
       if(size<index ||index<0){
    	   throw new RuntimeException("下标越界："+index+"，size"+size);
       }else{
    	  
    	   Node nodenow = get(index);
    	   if(index==0){
    		   root = node;
    		   
    	   }else{
    		   
    		   Node fNode = nodenow.getPrevious();
    		   //设置新的引用关系
    		   fNode.setNext(node);
    		   node.setPrevious(fNode);
//    		   node.setNext(nodenow);
//    		   nodenow.setPrevious(node);
    	   }
    	   //设置新的引用关系
    	   node.setNext(nodenow);
    	   nodenow.setPrevious(node);
       }
       size++;
    }  
	
	
	/* (non-Javadoc)
	 * @see cn.netjava.lesson13.NodeLinkedListInterface#remove(cn.netjava.lesson13.Node)
	 */
	@Override
	//删除指定的节点
	public void remove(Node node){
		int I =0;
		for(int i=0;i<size;i++){
			Node nodenow = get(i);
			if(nodenow==node){
				I = i;
			}
			
		}
		//得到当前索引位置的节点
		Node nodenow = get(I);
		//得到父节点
		Node Fnode = nodenow.getPrevious();
		//得到子节点
		Node Cnode = nodenow.getNext();
		if(Fnode==null){
        root=Cnode;
		
	}else if(Cnode==null){
		Fnode.setNext(null);
	}else{
		Fnode.setNext(Cnode);
		Cnode.setPrevious(Fnode);
		
	}
	
		
		size--;	
		
		
	}
	
	/* (non-Javadoc)
	 * @see cn.netjava.lesson13.NodeLinkedListInterface#remove(int)
	 */
	@Override
	//根据指定索引位删除节点
	public void remove(int index){
		if(size<index ||index<0){
		throw new RuntimeException("下标越界："+index+"，size"+size);
			
		}else{
			//得到当前索引位置的节点
			Node nodenow = get(index);
			//得到父节点
			Node Fnode = nodenow.getPrevious();
			//得到子节点
			Node Cnode = nodenow.getNext();
			if(Fnode==null){
            root=Cnode;
			
		}else if(Cnode==null){
			Fnode.setNext(null);
		}else{
			Fnode.setNext(Cnode);
			Cnode.setPrevious(Fnode);
			
		}
		
			
		}
	
		size--;
	}
	
	
	
	/* (non-Javadoc)
	 * @see cn.netjava.lesson13.NodeLinkedListInterface#get(int)
	 */
	@Override
	//得到节点索引位的方法
	public Node get(int index) {
		// 超出索引，返回null
		if (index >= size || index < 0) {
			return null;
		}
		//让node为根节点
		Node node = root;
		//遍历至索引位置
		for (int i = 0; i < index; i++) {
			//获取node节点的下一个节点
			node = node.getNext();
		}
		return node;
	}

	/* (non-Javadoc)
	 * @see cn.netjava.lesson13.NodeLinkedListInterface#size()
	 */
	@Override
	//得到链表中结点个数的方法
	public int size() {
		return size;
	}

}

 

程序主体如下

package NodeLink;

import java.util.Random;

public class Meneger {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// 用第一种添加方法初始化链表内容
		NodeLinkedListInterface nll = new NodeLinkedList();
		Random rand = new Random();
		for (int i = 0; i < 10; i++) {
			Node node = new Node(rand.nextInt(100));
			nll.add(node);
		}

		for (int i = 0; i < 10; i++) {
			Node node = nll.get(i);
			System.out.print(node.getData()+"    ");
		}
		System.out.println("\n");
		// 用第二种添加方法插入一个数字
		int index = rand.nextInt(10);
		Node node = new Node(rand.nextInt(100));
		nll.add(node, index);
		for (int i = 0; i < 11; i++) {
			if (i == index) {
				Node node1 = nll.get(i);
				System.out.print("new  " + node1.getData()+"   ");
			} else {
				Node node1 = nll.get(i);
				System.out.print(node1.getData()+"    ");
			}
		}
		System.out.println("\n");
		 //移除
		 int index1 = rand.nextInt(10);
		 int indexx = index1+1;
		 System.out.println("移除的是第"+indexx+"个节点");
		 nll.remove(index1);
		 for(int i=0;i<nll.size();i++){
		 Node node2 = nll.get(i);
		 System.out.print(node2.getData()+"    ");
		 }
		 System.out.println("\n");
		// 第二种移除
		int index2 = rand.nextInt(10);
		System.out.println("移除的是第" + (index2 + 1) + "个节点");
		nll.remove(nll.get(index2));
		for (int i = 0; i < nll.size(); i++) {
			Node node3 = nll.get(i);
			System.out.print(node3.getData() + "   ");
		}
		for (int i = 1; i < nll.size(); i++) {
			for (int j = i; j > 0; j--) {
				Node node1 = nll.get(j);
				Node node2 = nll.get(j - 1);

				if (nll.get(j).getData() < nll.get(j - 1).getData()) {
					int temp = nll.get(j).getData();
					nll.get(j).setData(nll.get(j - 1).getData());
					nll.get(j - 1).setData(temp);

				}

			}
		}
		System.out.println("");
		System.out.println("从小到大排序后的结果为：");
		for (int k = 0; k < nll.size(); k++) {
			Node nodex = nll.get(k);
			System.out.print(nodex.getData()+"   ");
		}

	}
}

  结点类与接口比较简单略去不写。

关于链表，有几个感受，我又一次要把它跟C语言对比。。。C的链表跟java的链表大同小异，这种通过绑定地址来实现的节点之间的连接操作，突破了数组中数据必须相同类型，并且必须连续的限制，增加了使用的灵活性，在这次的练习中，加深了对递归的理解~递归超级有用啊，极大的缩短了代码量，感觉数据结构好有意思。。。估计我说这句话会被拍死。。。好啦，这就是这一部分的总结，精华全在代码