1.介绍

使用带head头的双向链表实现

管理单向链表的缺点分析:

(1)单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。

(2)单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到temp,temp是待删除节点的前一个节点

(3)示意图帮助理解删除

2.代码实现

public class DoubleList {

	//初始化头节点，不存放具体的数据
	private Node head=new Node(0,"");
		
	//返回头结点
	public Node getHead() {
		return head;
	}
	
	//遍历
	//遍历链表
	public void list() {
		//判断链表是否为空
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		//head是哑节点，head.next才是真正意义上的first
		for(Node x=head.next;x!=null;x=x.next) {
			System.out.println(x);
		}
	}
	
	//添加节点到双向链表的最后
	public void add(Node newNode) {
		//temp指向哑节点head
		Node temp=head;
		while(true) {
			//找到链表的最后
			if(temp.next==null) {
				break;
			}
			
			temp=temp.next;
		}
		
		//最后链表的next指向newNode
		temp.next=newNode;
		newNode.pre=temp;
	}
	
	public void addByOrder(Node newNode) {
		//头节点不能动
		//单链表 找的temp位于添加的前1个节点
		
		Node temp=head;
		boolean flag=false; //添加的符号是否存在，默认为false
		
		while(true) {
			
			//temp已经到了最后一个节点
			if(temp.next==null) {
				break;
			}
			//找到temp.next刚好大于newNode	
			if(temp.next.no>newNode.no) {
				break;
			}
			//说明要添加的Node的编号已经存在了
			else if(temp.next.no==newNode.no) {
				flag=true; //说明编号已经存在
				break;
			}
			//后移遍历当前链表
			temp=temp.next;
		}
		//判断flag的值
		if(flag) {
			//不能添加
			System.out.printf("准备插入的节点%d已经存在了，不能加入n",newNode.no);
		}else {
			//插入到链表中
			Node tempNext=temp.next;
			if(tempNext!=null) {
				tempNext.pre=newNode;
			}
			newNode.next=tempNext;
			temp.next=newNode;
			newNode.pre=temp;
		}
	}

	
	
	//修改节点
	public void update(Node newNode) {
		//判断是否为空
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		
		//找到要修改的节点，根据no编号
		//定义辅助变量
		Node temp=head.next;
		boolean flag=false;
		while(true) {
			if(temp==null) {
				break;
			}
			if(temp.no==newNode.no) {
				flag=true;
				break;
			}
			temp=temp.next;
		}
		if(flag) {
			temp.no=newNode.no;
			temp.name=newNode.name;
		}else {
			System.out.printf("没有找到编号 %d 的节点,不能修改n",newNode.no);
		}
	}

	//删除双向链表的一个节点
	//1. 对于双向链表，可以直接找到要删除的这个节点
	//2. 找到后自我删除
	public void del(int no) {
		//判断链表是否为空
		if(head.next==null) {
			System.out.println("链表为空，无法删除");
			return;
		}
		
		//指向哑节点，因为有可能删除第1个
		Node temp=head.next;
		boolean flag=false;
		while(true) {
			if(temp==null) {//已经找到链表的最后了
				break;
			}
			if(temp.no==no) {
				flag=true;
				break;
			}
			temp=temp.next;
		}
		
		if(flag) {
			temp.pre.next=temp.next;
			//如果删除的不是最后一个节点
			//如果不是最后一个节点，就不需要执行下面这句话，否则会暴空指针异常
			if(temp.next!=null) {
				temp.next.pre=temp.pre;
			}
			
		}else {
			System.out.printf("没有节点%dn",no);
		}
	}
	
	
	public static void main(String[] args) {
		System.out.println("双向链表的测试");
		DoubleList dl=new DoubleList();
		Node n1=new Node(1,"宋江");
		Node n2=new Node(2,"孙悟空");
		Node n3=new Node(3,"唐僧");
		Node n4=new Node(4,"沙师弟");
		
		dl.add(n1);
		dl.add(n2);
		dl.add(n3);
		dl.add(n4);
		
		dl.list();
		System.out.println("修改测试");
		Node n4_2=new Node(4,"白龙马");
		dl.update(n4_2);
		dl.list();
		
		System.out.println("删除测试");
		dl.del(3);
		dl.list();
		
		System.out.println("-----addByOrder----------");
		Node n5=new Node(5,"孙行者");
		Node n3_2=new Node(3,"行者孙");
		Node n0=new Node(0,"杨戬");
		dl.addByOrder(n5);
		dl.addByOrder(n3_2);
		dl.addByOrder(n0);
		dl.list();
	}
}