Java链表

链表

链表是一种物理存储单元上非连续非顺序的存储结构。链表有一系列结点组成，每个结点包括两个部分：存储数据元素的数据域，和存储下一个结点地址的指针域（引用）。
链表便于插入和删除操作。

链表的分类：
1、单向链表
单向链表的每个结点右存储数据元素的数据域和指向下一个结点的指针域组成。

/**
 * 单向链表结点类
 */
public class LinkNode{
 	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 child;
	}	
	//设置子节点
	public void setNext(LinkNode next){
		this.child = child;
	}	
}

2、双向链表
双向链表有一个数据域和两个链域，一个存储直接子结点地址（右链域），一个存储直接父结点地址（左链域）。

public class LinkNode {
	private Object obj;//结点内的数据对象
	private LinkNode child;//对下一个结点的引用
	private LinkNode parent;//对上一个结点的引用	
	//构造方法
	public LinkNode(Object obj){
		this.obj = obj;
	}	
	//得到节点中的数据对象
	public Object getObj(){
		return obj;
	}	
	//设置节点中的数据对象
	public void setObj(Object obj){
		this.obj = obj;
	}	
	//得到子节点
	public LinkNode getChild(){
		return child;
	}	
	//设置子节点
	public void setChild(LinkNode child){
		this.child = child;
	}	
	//得到父节点
	public LinkNode getParent(){
		return parent;
	}	
	//设置父节点
	public void setParent(LinkNode parent){
		this.parent = parent;
	}	
}

使用链表实现数据的查找、插入、删除等操作。

public class LinkTest {	
	//设置链表的头结点为空
	private static LinkNode front = null;
	//设置链表的尾结点为空
	private static LinkNode last = null;	
	/**
	 * 主方法
	 * @param args
	 */
	public static void main(String[] args){
		LinkTest linktest = new LinkTest();		
		//实例化员工对象
		Worker wk1 = new Worker("张三","0001",3500);
		Worker wk2 = new Worker("李四","0009",3000);
		Worker wk3 = new Worker("王五","0006",5000);
		Worker wk4 = new Worker("熊哥","0003",3500);
		Worker wk5 = new Worker("王麻子","0007",4000);
		//将员工对象加入到链表中
		linktest.add(wk1);
		linktest.add(wk2);
		linktest.add(wk3);
		linktest.add(wk4);
		linktest.print(front);
		//在下标为2的位置插入新结点
		linktest.insert(2, wk5);
		linktest.print(front);
//		//删除下标为3的位置的结点
//                linktest.delete(3);	
//		linktest.print(front);
		//按指定顺序输出
		linktest.inOrder();	
	}	
	/**
	 * 向链表中加入结点，从链表末尾添加
	 * @param obj
	 */
	public void add(Object obj){
		LinkNode node = new LinkNode(obj);
		if(front==null){//如果链表为空
			front = node;
			last = front;
		}else{//如果链表不为空
			last.setChild(node);
			node.setParent(last);
			last = node;
		}
	}	
	/**
	 * 在指定索引位置插入结点，索引是从0开始的
	 * @param index 要插入的索引位置
	 * @param obj
	 */
	public void insert(int index,Object obj){
		//实例化一个新的结点
		LinkNode newNode = new LinkNode(obj);
		LinkNode temp = front;
		for(int i=0;i<index-1;i++){
			temp = temp.getChild();
		}
		//循环结束后的temp是索引位置的前一个结点
		//设置新节点的子结点是索引位置结点，索引位置结点的父结点是新结点	
		(temp.getChild()).setParent(newNode);
		newNode.setChild(temp.getChild());
		//设置索引位置前一个结点的子结点是新结点，新结点的父结点是该结点
		temp.setChild(newNode);
		newNode.setParent(temp);	
	}	
	/**
	 * 删除索引位置的结点
	 * @param index
	 */
	public void delete(int index){
		if(index>=0&&index<this.getLength()){
			LinkNode node = this.getLinkNode(index);
			if(node.getChild()==null){
				node.getParent().setChild(null);
			}
			if(node.getParent()==null){
				node.getChild().setParent(null);
				front = node.getChild();
			}
			if(node.getParent()!=null&&node.getChild()!=null){
				(node.getParent()).setChild(node.getChild());
				(node.getChild()).setParent(node.getParent());
			}		
		}
	}		
	/**
	 * 得到索引位置的结点
	 * @param index 索引位置
	 * @return 返回的是一个结点
	 */
	public LinkNode getLinkNode(int index){
		if(index>=0&&index<this.getLength()){
			int number = 0;
			LinkNode node = front;
			while(number!=index){
				node = node.getChild();
				number++;
			}
//			System.out.println("\t"+node.getObj());
			return node;
		}else{
			System.out.println("下标越界");
			return null;		
		}		
	}		
	/**
	 * 得到链表的长度
	 * @return
	 */
	public int getLength(){
		int count = 0;
		LinkNode node = front;
		while(node!=null){
			count++;
			node = node.getChild();
		}
		return count;
	}	
	/**
	 * 根据员工工资非降序排列员工对象并输出
	 */
	public void inOrder(){
		//整型数组用来存储员工工资
		int[] a = new int[this.getLength()];
		//Object数组用来存储员工对象
		Object[] moneyOrder = new Object[this.getLength()];
		//循环遍历两个数组，将员工工资和员工对象分别存储到两个数组中的相应下标位置
		for(int i=0;i<this.getLength();i++){
			a[i] = ((Worker) this.getLinkNode(i).getObj()).getMoney();
			moneyOrder[i] = this.getLinkNode(i).getObj();
		}
		//使用冒泡排序法，对员工工资大小进行非降序排列，然后将员工对象数组也对应调整，
		//总终员工对象数组的排列是按照其工资的非降序排列的
		for(int i=0;i<a.length-1;i++){
			for(int j=0;j<a.length-i-1;j++){
				if(a[j]>a[j+1]){
					//调整工资数组
					int temp = a[j];
					a[j] = a[j+1];
					a[j+1] = temp;
					//调整员工对象数组
					Object txt = moneyOrder[j];
					moneyOrder[j] = moneyOrder[j+1];
					moneyOrder[j+1] = txt;				}
			}
		}
		//输出工资数组
		for(int i=0;i<a.length;i++){
			System.out.println(a[i]);		
		}
		//输出员工对象数组-----它是按照工资的非降序排列的员工对象
		for(int i=0;i<a.length;i++){
			System.out.println(moneyOrder[i].toString());
		}	
	}	
	/**
	 * 打印链表中的数据内容
	 * @param root
	 */
	public void print(LinkNode root){
		if(root!=null){
			Object data = root.getObj();
			System.out.println(data);
			LinkNode temp = root.getChild();
			print(temp);
		}
	}	
}

/**
 * 员工类
 * @author 客
 *
 */
public class Worker {
	private String name;
	private String number;
	private int money;	
	/**
	 * 构造方法
	 * @param name 员工姓名
	 * @param number 员工工号
	 * @param money 员工工资
	 */
	public Worker(String name,String number,int money){
		this.name = name;
		this.number = number;
		this.money = money;
	}
	
	public void setName(String name){
		this.name = name;
	}	
	public String getName(){
		return name;
	}
	
	public void setNumber(String number){
		this.number = number;
	}	
	public String getNumber(){
		return number;
	}
	
	public void setMoney(int money){
		this.money = money;
	}	
	public int getMoney(){
		return money;
	}
	
	public String toString(){
		return name+"的工号是："+number+"\t工资是："+money;
	}	
}

3、循环链表
     将末尾结点指向根结点。



如有不足欢迎指正！