java实现双向链表的基本功能_java集合中双向链表的作用

单向链表的缺点
1）单向链表，查找的方向只能是一个方向，而双向链表可以向前或向后查找
2）单向链表不能自我删除，需要借助辅助变量，而双向链表可以自我删除

双向链表的增删改、遍历的操作思路
1）添加节点（默认添加到双向链表的最后）
1.先找到双向链表的最后节点
2.temp.next=newHero（temp为辅助节点）
3.newHero.pre=temp

2）删除节点
1.直接找到要删除的这个节点，比如temp
2.temp.pre.next=temp.next
3.temp.next.pre=temp.pre

3)修改节点
1.根据节点的某个属性（比如编号 no）来找到目标节点
2.修改该节点其他数据

4）遍历
思路跟单链表一样，只是可以向前，也可以向后查找

单链表方法

双向链表的代码实现

public class DoubleLinkedList {
    //初始化头节点head，头节点不能动，不存放任何数据
    private User head=new User(0,"","");
    //添加节点到链表最后
    public void add(User user){
        //由于头节点不能动，因此需要一个辅助变量temp
        User temp=head;
        while(true){
            if(temp.next==null){
                //到达链表最后
                break;
            }
            //如果没有到最后，继续将temp后移
            temp=temp.next;
        }
        //当推出while循环时，表明temp指向链表最后一个节点
        temp.next=user;
        user.pre=temp;
    }

    //删除节点
    //传一个用户名过来，根据用户名是否匹配来删除节点
    public void del(String name){
        //先判断是否为空链表
        if(head.next==null){
            System.out.println("该链表为空，没有数据可删");
            return;
        }
        User temp=head.next;
        boolean flag=false;//标志是否找到待删节点
        while(true){
            if(temp==null){
                //表明链表到最后了
                break;
            }
            if(temp.name.equals(name)){
                //找到待删除节点
                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.println("要删除名字为："+name+"节点不存在");
        }
    }

    //修改节点数据
    public void update(User newUser){
        //判断是否为空链表
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //根据name找到需修改的节点
        User temp=head.next;
        boolean flag=false;//标志是否找到待修改节点
        while(true){
            if(temp==null){
                //链表已到最后
                break;
            }
            if(temp.name.equals(newUser.name)){
                //找到待修改节点了
                flag=true;
                break;
            }
            temp=temp.next;//后移，遍历
        }
        if(flag){
            //修改该节点内容
            temp.age=newUser.age;
            temp.password=newUser.password;
        }else{
            System.out.println("没有找到名字为："+newUser.name+"的节点，不能修改");
        }
    }

    //遍历
    public void show(){
        //判断是否为空链表
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        User temp=head.next;
        while(true){
            if(temp==null){
                //链表到最后了
                break;
            }
            //输出节点内容
            System.out.println(temp);
            temp=temp.next;//后移，遍历
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

定义一个User类

//定义一个User类，每个User对象为一个节点
class User{
    public int age;
    public String name;
    public String password;
    public User next;//指向下一个节点
    public User pre;//指向前一个节点

    public User(int age,String name,String password){
        this.age=age;
        this.name=name;
        this.password=password;
    }

    //重写toString方法
    public String toString(){
        return "User[age="+age+"name="+name+"password="+password+"]";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19