java数据结构第一篇双链表的增删改查

java数据结构双链表实现增删改查

链表是接触数据结构最先了解的，他是一个线性表，我们是先学习了java的编译原理，知道了Person a=new Person();和Person.son=a;这两个等号的区别，所以编写起链表来相对好理解一下。双链表和单链表的原理相同，所以可以先尝试着编写单链表，然后再编写双链表。

话不多说直接上代码

首先定义了一个类，这个类就相当于结点

public class Person {
	public int id;
    public String name;
    public Person next;
    public Person pre;
 
    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }
 
    @Override
    public String toString() {
        return "Person{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }


	
}

然后就是开始编写双链表

public class List {
	public Person head = new Person(0,"");
    public Person getHead(){
        return head;
    }
    // 添加
    public void add(Person headNode,Person node){

        boolean flag = true;
        Person temp = headNode.next;
        while(true){
            if(temp == null){// 头部插入
                headNode.next = node;
                node.pre = headNode;
                flag = false;
                break;
            }
            if(node.id < temp.id){// 中间插入
                temp.pre.next = node;
                node.pre = temp.pre;
                node.next = temp;
                temp.pre =node;
                flag = false;
                break;
            }
            if(node.id == temp.id){ // 已经存在
                System.out.println("节点已存在。。");
                flag = false;
                break;
            }
            if(temp.next == null){// 如果已经没有节点了，就退出
                break;
            }
            temp = temp.next;
        }
        if(flag){// 尾部插入
            temp.next = node;
            node.pre = temp;
        }
    }
    // 修改
    public void update(Person updateNode){
        boolean flag = true;
        Person temp = head.next;
        while(true){
            if(temp.id == updateNode.id){
                temp.name = updateNode.name;
                flag = false;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            System.out.println("该节点不存在。。");
        }
    }
    // 删除
    public void delete(int id){
        boolean flag = true;
        Person temp = head.next;
        while(temp != null){
            if(temp.id == id){
               if(temp.next == null){// 如果删除的是最后一个的话
                   temp.pre.next = null;
                   temp.pre = null;
                   flag = false;
                   break;
               }else{
                   temp.pre.next = temp.next;
                   temp.pre = temp.next.pre;
                   flag = false;
                   break;
               }
            }
            temp = temp.next;
        }
        if(flag){
            throw new RuntimeException("链表的该节点不存在。。。");
        }
    }
    //查找
    public void find(int id)
    {
    	Person temp=head.next;
   boolean flag=true;
   while(flag=true)
   {
	 if(temp.id==id)
	 {
		 temp.next=null;
		 flag=false;
		 System.out.print(temp);
		 break;
	 }
	 else
	  temp=temp.next;
   }
    	}    
    // 显示
    public void show(Person headNode){
        
        Person temp = headNode.next;
        while( temp != null){
            System.out.println(temp);
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        Person person1 = new Person(1,"zs");
        Person person2 = new Person(6,"ww");
        Person person3 = new Person(3,"ls");
 
 
       List linkedList = new List();
       linkedList.add(linkedList.getHead(),person1);
       linkedList.add(linkedList.getHead(),person2);
       linkedList.add(linkedList.getHead(),person3);
       System.out.println("添加以后");
       linkedList.show(linkedList.getHead());
 
        System.out.println("修改以后");
       Person person4 = new Person(3,"zss");
       linkedList.update(person4);
       linkedList.show(linkedList.getHead());
       System.out.println("删除以后");
       linkedList.delete(3);
       linkedList.show(linkedList.getHead());
       System.out.println("查找之后");
       linkedList.find(6);
}
}

这里说明一下，我在编写插入的时候用的是顺序插入，然后遇到了困难，如果最后判定是尾部插入怎么办，就采用了while循环的方法，来实现循环插入，包括删除和查找都是用的这个方法。这个可以优化成一个学生信息管理系统，来实现学生信息的操作。下个博客分享二叉树的创建以及前中后三种遍历方法。