JAVA双向链表的构建

      直接进入主题，要想自己构建一个双向链表就得知道双向链表的构成，既然是链表，很容易让人联想到链条，其实就是和链条差不多的结构，很形象，那就让我们来看看节点的结构，图画得有些难看不要打我。  

 

     双向链表的结构：由若干个节点组成，每个节点有三个属性，一个是指向前一个节点的，一个是存储该节点数据的，一个是指向后一个节点的。从图可知，链表是由节点组成，那么就要先声明节点：

     节点的声明：这里以数据类型为String类型来举例

    

/**
	 * 定义节点类
	 * @author Administrator
	 *
	 */
	class Node{
		String data;
		Node next;
		Node front;
		/**
		 * 构造函数
		 * @param data 节点的数据 
		 */
		public Node(String data)
		{
			this.data=data;
		}	
	}

       声明好节点后就可以来声明链表类了：

       双向链表的属性：

             Node   head;------------>头节点

             Node   tail;--------------->尾节点

             int        count;----------->计算节点个数

     既然是链表就得有一些方便我们用的方法：增、删、改、查

     上代码：         

package jhf.linklist;


/**
 * 我的链表类
 * 双向链表
 * @author Administrator
 *
 */
public class MyLinkList {
	
	Node head;//头节点
	Node tail;//尾节点
	int count;//节点的个数
	/**
	 * 添加指定元素到链表的尾部
	 * @param s  要添加的元素
	 */
	public void add(String s)
	{
		//根据元素创建一个新节点
		Node n=new Node(s);
		if(head==null)
		{
			head=n;
		}else{
			
			tail.next=n;
			n.front=tail;
		}
		tail=n;
		count++;
	}
	/**
	 * 取出指定位置的节点
	 * @param index  要取出节点的位置
	 * @return  返回的是该位置的节点
	 */
	public Node getNode(int index)
	{
		//下标越界处理
		if (index < 0 || index >= size()) {
			throw new RuntimeException("下标越界");
		}
		int num = 0;// 寻找的下标
		Node n=head;//从头结点开始寻找
		while (n != null) {
			if (num == index) {
				break;
			}
			num++;
			n = n.next;
		}
		
		return n;
	}
	
	/**
	 * 根据下标得到元素值的方法
	 * @param index  要得到元素的下标
	 * @return  返回的是这个元素的值
	 */
	public String  get(int index)
	{
		//下标越界处理
		if (index < 0 || index >= size()) {
			throw new RuntimeException("下标越界");
		}
		int num = 0;// 寻找的下标
		Node n=head;//从头结点开始寻找
		while (n != null) {
			if (num == index) {
				break;
			}
			num++;
			n = n.next;
		}
		// 获得该节点的元素
		String s = n.data;
		
		return s;
	}
	/**
	 * 根据元素值得到这个节点的方法
	 * @param s   元素
	 * @return  与该值相对应的节点
	 */
	public Node getNode(String s)
	{
		int unm=0;//计数器
		String ss=head.data;
		if(s==ss){//如果要找的就是头节点
			//System.out.println("已经得到下标"+unm);测试得到的下标是否正确时用的语句
			Node n=getNode(unm);//根据下标得到节点  该方法已经在上面实现并测试挣钱  可以直接调用 
			//System.out.println("找到元素："+n.data+"的节点啦！");测试找到的元素是否正确的时候用的语句
			return head;
		}
		else//如果找到的不是头节点
		{
			unm=1;
			ss=get(unm);
			while(ss!=s)
			{
				if(ss==s) break;
				unm++;
				ss=get(unm);
			}
		}
		//System.out.println("已经得到下标"+unm);测试得到的下标是否正确时用的语句
		Node n=getNode(unm);//根据下标得到节点  该方法已经在上面实现并测试挣钱  可以直接调用 
		//System.out.println("找到元素："+n.data+"的节点啦！");测试找到的元素是否正确的时候用的语句
		return n;
		
	}
	/**
	 * 将指定的元素添加到指定的位置
	 * @param s  要添加的元素
	 * @param index  要添加到的位置
	 */
	public void add(String s,int index)
	{
		//判断下标是否越界
		if (index < 0 || index >= size()) {
			throw new RuntimeException("下标越界");
		}
		int num= 0;//用来寻找的下标
		Node n=head;//从头节点开始寻找
		while(n!=null){
			if(num==index){
				break;
			}
			num++;
			n=n.next;
		}
		Node nn=new Node(s);
		if(n==tail)
		{
			n.next=nn;
			nn.front=n;
			tail=nn;
		}else{
		nn.next=n.next;
		n.next.front=nn;		
		n.next=nn;
		nn.front=n;
		}
		count++;
		
	}

	/**
	 * 删除指定位置的元素
	 * @param s  要删除的元素的下标
	 */
	public void delete(int index)
	{
		Node n=getNode(index);
		if(n==tail)//如果找到的该节点是尾节点
		{
			n.front.next=null;	
		}else{
		n.front.next=n.next;
		n.next.front=n.front;
		}
		count--;
	}
	/**
	 * 删除指定元素
	 * @param s  要删除的元素
	 */
	public void delete(String s){
		Node n=getNode(s);
		if(n==tail)//如果找到的该节点是尾节点
		{
			n.front.next=null;	
		}else{
		n.front.next=n.next;
		n.next.front=n.front;
		}
	count--;
	
	}
	
	
	
	 public int size(){
		return count;
	}
	
	// 传入头节点取出链表中的所有元素
		public void printList(Node n) {
			if (n != null) {
				String s = n.data;
				System.out.println(s);
				printList(n.next);
			}
		}
	
	
	
	/**
	 * 定义节点类
	 * @author Administrator
	 *
	 */
	class Node{
		String data;
		Node next;
		Node front;
		/**
		 * 构造函数
		 * @param data 节点的数据 
		 */
		public Node(String data)
		{
			this.data=data;
		}	
	}

}