双向链表

小咪咪 2021-08-12 00:11 459阅读 0赞

【一】双向链表

> 单向链表，查找的只能是一个方向，而双向链表可以向前或向后查找。  
> 单向链表不能自我删除，需要靠辅助节点；而双向链表可以自我删除  
> 双向链表中的节点  
> pre data next  
> pre指向前一个节点的地址  
> data存储当前节点的数据  
> next指向下一个节点的地址

【二】代码实现

>  实现功能：  
> 1.遍历双向链表  
>     双向链表的遍历和单链表一样，只是可以向前查找，向后查找。  
> 2.增加节点、删除节点、修改节点、插入节点  
>     添加和单项链表相似：1.找到最后一个节点temp；2.temp.next=node,node.pre=temp;  
>     修改：和单项链表相同；  
>     删除(添加至双向链表的末端)：1.找到要删除的节点temp；2.temp.pre.next=temp.next;temp.next.pre=temp.pre;  
>     插入节点：1.找到要插入节点的后一个节点temp;2.temp.pre=node;node.next=temp;  
> 3.返回头结点

插入节点的示意图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70][]

代码实现：

public class DoubleLinkedList {
    	public static void main(String[] args) {
    		DoubleStudentNode dsn=new DoubleStudentNode();
    		dsn.add(new StudentNode2(100,"zhangsan","beijing"));
    		dsn.add(new StudentNode2(106,"lisi","shanghai"));
    		dsn.add(new StudentNode2(109,"wangwu","xian"));
    		dsn.add(new StudentNode2(107,"zhaoliu","shanxi"));
    		
    		dsn.list();
    		//dsn.del(106);
    		System.out.println("----------修改节点");
    		dsn.updateNode(new StudentNode2(106,"haha","shijiazhuang"));
    		dsn.list();
    		System.out.println("----------删除节点");
    		dsn.del(109);
    		dsn.list();
    		System.out.println("----------插入节点");
    		dsn.addNodesByOrder(new StudentNode2(103,"wangerxiao","changan"));
    		dsn.list();
    	}
    }
    class DoubleStudentNode{
    	StudentNode2 head=new StudentNode2(0,"","");
    	//返回头结点
    	public StudentNode2 getHead() {
    		return head;
    	}
    	//插入节点
    	public void addNodesByOrder(StudentNode2 node) {
    		StudentNode2 temp=head;
    		boolean flag=false;
    		while(true) {
    			if(temp.next==null) {
    				break;
    			}
    			if(temp.id>node.id) {
    				break;
    			}
    			if(temp.id==node.id) {
    				flag=true;
    				break;
    			}
    			temp=temp.next;
    		}
    		if(flag) {
    			System.out.printf("id为%d的节点已存在链表中", node.id);
    		}else {
    			temp.pre.next=node;
    			node.pre=temp.pre;
    			node.next=temp;
    			temp.pre=node;
    		}
    	}
    	//修改
    	public void updateNode(StudentNode2 node) {
    		StudentNode2 temp=head.next;
    		boolean flag=false;
    		if(temp==null) {
    			System.out.println("链表为空，没有要修改的元素");
    			return;
    		}
    		while(true) {
    			if(temp==null) {
    				break;
    			}
    			if(temp.id==node.id) {
    				flag=true;
    				break;
    			}
    			temp=temp.next;
    		}
    		if(flag) {
    			temp.name=node.name;
    			temp.adress=node.adress;
    		}else {
    			System.out.printf("没有找到id为%d的节点，无法修改", node.id);
    		}
    	}
    	
    	//删除元素
    	public void del(int id) {
    		if(head.next==null) {
    			System.out.println("链表为空，要删除的节点不存在");
    			return;
    		}
    		StudentNode2 temp=head.next;
    		boolean flag=false;
    		while(true) {
    			if(temp==null) {
    				break;
    			}
    			if(temp.id==id) {
    				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("要删除id为%d的节点不存在",id);
    		}
    	}
    	
    	//添加元素
    	public void add(StudentNode2 node) {
    		StudentNode2 temp=head;
    		while(true) {
    			if(temp.next==null) {
    				break;
    			}
    			temp=temp.next;
    		}
    		temp.next=node;
    		node.pre=temp;
    	}
    	//遍历链表
    	public void list() {
    		StudentNode2 temp=head.next;
    		if(temp==null) {
    			return;
    		}
    		while(temp!=null) {
    			System.out.println(temp);
    			temp=temp.next;
    		}
    	}
    }
    
    //定义双向链表的节点
    class StudentNode2{
    	public int id;
    	public String name;
    	public String adress;
    	public StudentNode2 next;
    	public StudentNode2 pre;
    	StudentNode2(int id,String name,String adress){
    		this.id=id;
    		this.name=name;
    		this.adress=adress;
    	}
    	@Override
    	public String toString() {
    		return "StudentNode [id=" + id + ", name=" + name + ", adress=" + adress +  "]";
    	}
    }

【三】输出截图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70]: /images/20210811/1e094db9ae78421ea095cf52bf9f827b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RoZV9CZXN0X0hhY2tlcg_size_16_color_FFFFFF_t_70 1]: /images/20210811/5e915634bb6241ee92ac766003213a96.png