双端链表和双向链表

一:双端链表

1.什么是双端链表?
链表中保存着对最后一个链节点引用的链表就是双端链表.

2.从头部插入
要对链表进行判断,如果为空则设置尾节点为新增节点

3.从尾部插入
如果链表为空,则直接设置头节点为新增节点,否则设置尾节点的后一个节点为新增节点

4.从头部删除节点
判断头节点是否指向下一个节点,如果没有则设置节点为null

1.创建双端链表节点Node

//头节点
public class Node {
    //包含下一个节点的引用
    Node next;
    //节点数据
    long data;

    //构造方法
    public Node(long value){
        this.data = value;
    }

    //显示节点
    public void display(){
        System.out.println(data);
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.创建双端链表和操作链表

//双端链表
public class FirstLastLinkList {
    //保存头节点引用
    Node first;
    //保存尾节点的引用
    Node last;

    //构造方法
    public FirstLastLinkList(){
        first = null;
        last = null;
    }

    //从头部节点进行插入
    public void insertFirst(long value){
        //新建节点并且初始化数据
        Node node = new Node(value);
        //插入节点
        if (first == null){
            //如果没有头节点,则设置新节点为尾节点
            last = node;
        }else{
            //如果存在头节点,则新节点改为头节点且旧的头节点改为新节点的下一个节点
            node.next = first;
            first = node;
        }
        //每次插入都会更新头节点
        first = node;
    }

    //从尾节点进行插入
    public void insertLast(long value){
        //新建节点
        Node node = new Node(value);
        if (first == null){
            //如果头节点为空,则新节点就是头节点
            first = node;
        }else{
            //如果头节点不为空,则新节点就作为尾节点的后面节点
            last.next = node;
        }
        //每次插入都会更新尾节点
        last = node;
    }

    //从头部开始查找
    public Node find(long value){
        //头节点
        Node node = first;
        if (node == null){
            return null;
        }
        //如果头节点数据不匹配则进行循环查找
        while (node.data != value){
            //如果没有下一个节点就说明查找结束,返回null
            if (node.next == null){
                return null;
            }
            //如果存在下一个节点,就继续从下一个节点开始查找
            node = node.next;
        }
        //返回找到的节点
        return node;
    }

    //删除头节点
    public Node removeFirst(){
        //头节点
        Node node = first;
        if (node == null){
            last = null;
        }else{
            first = node.next;
        }
        return node;
    }

    //删除其他指定节点
    public Node removeNode(long value){
        //头节点
        Node node = first;
        //临时节点,记录每次查找节点的前一个节点
        Node tmp = first;
        if (node == null){
            return null;
        }
        while (node.data != value){
            if (node.next == null){
                return null;
            }
            tmp = node;
            node = node.next;
        }
        //删除节点
        if (node == first){
            first = first.next;
        }else{
            tmp.next = node.next;
        }
        return node;
    }

    //从头节点开始遍历
    public void show(){
        //先获取头节点
        Node node = first;
        if (node == null) {
            System.out.println("链表为空");
        }
      //如果头节点不为空再打印
        while (node != null){
            node.display();
            node = node.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
105
106
107
108
109
110
111
112
113
114
115
116
117
118

3.测试链表

public class Test {
    public static void main(String[] args) {

        FirstLastLinkList list = new FirstLastLinkList();

        //从头节点插入
        list.insertFirst(1);
        list.insertFirst(2);
        list.insertFirst(3); //这个是头节点
        list.show();  //3 2 1

        //从尾节点插入
        list.insertLast(6);
        list.insertLast(7);
        list.insertLast(8); //这个是尾节点
        list.show();    //3 2 1 6 7 8

        //查找节点
        Node node = list.find(3);
        if (node == null){
            System.out.println("没有找到节点");
        }else{
            System.out.println("找到节点: "+node.data); //找到节点: 3
        }

        //删除头节点
        Node first = list.removeFirst();
        System.out.println("删除的头节点为: "+first.data); //删除的头节点为: 3
        list.show(); //2 1 6 7 8

        //删除指定节点
        Node removeNode = list.removeNode(2);
        if (removeNode == null){
            System.out.println("找不到节点");
        }else{
            System.out.println("被删除节点为: "+removeNode.data); //被删除节点为: 2
        }
        list.show(); //1 6 7 8

    }
}

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

二:双向链表

1.什么是双向链表
每个节点除了保存对下一个节点的引用,同时还保存着对前一个节点的引用

2.从头部进行插入
先对链表进行判断,如果链表为空,则新节点就是尾节点;如果不为空,则需要设置新节点为头节点,同时旧的头节点作为新节点的下一个节点

3.从尾部进行插入
判断链表,如果链表为空,则新节点就是头节点;如果不为空,则设置新节点是尾节点的下一个节点,同时尾节点变成新节点

4.从头部进行删除
判断头节点是否有下一个节点,如果没有设置节点为空;如果有则设置下一个节点的前节点为空

5.从尾部进行删除
如果头节点后面没有其他节点,则设置尾节点为null;否则设置头节点前一个节点为null,同时设置新的尾节点为旧的尾节点的前一个节点

1.创建双向链表节点Node

//双向链表的节点
public class Node {
    //下一个节点引用
    Node next;
    //前一个节点引用
    Node pre;
    //节点数据
    long data;
    //初始化节点数据
    public Node(long value){
        this.data = value;
    }
    ///显示节点
    public void display(){
        System.out.println(data);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.创建双向链表和操作链表

//双向链表
public class DoubleLinkList {
    //保存头节点引用
    Node first;
    //保存尾节点的引用
    Node last;

    //构造方法
    public DoubleLinkList(){
        first = null;
        last = null;
    }

    //从头部节点进行插入
    public void insertFirst(long value){
        //新建节点并且初始化数据
        Node node = new Node(value);
        //插入节点
        if (first == null){
            //如果没有头节点,则设置新节点为尾节点
            last = node;
        }else{
            //如果存在头节点
            //新节点就是旧头节点的前一个节点
            first.pre = node;
            //旧的头节点变成新节点的下一个节点
            node.next = first;
            //新节点变成头节点
            first = node;
        }
        //每次插入都会更新头节点
        first = node;
    }

    //从尾节点进行插入
    public void insertLast(long value){
        //新建节点
        Node node = new Node(value);
        if (first == null){
            //如果头节点为空,则新节点就是头节点
            first = node;
        }else{
            //如果头节点不为空
            //则新节点就作为尾节点的后面节点
            last.next = node;
            //同时新节点的上一个节点就是旧的尾节点
            node.pre = last;
        }
        //每次插入都会更新尾节点
        last = node;
    }

    //从头部开始查找
    public Node find(long value){
        //头节点
        Node node = first;
        if (node == null){
            return null;
        }
        //如果头节点数据不匹配则进行循环查找
        while (node.data != value){
            //如果没有下一个节点就说明查找结束,返回null
            if (node.next == null){
                return null;
            }
            //如果存在下一个节点,就继续从下一个节点开始查找
            node = node.next;
        }
        //返回找到的节点
        return node;
    }

    //删除头节点
    public Node removeFirst(){
        //头节点
        Node node = first;
        if (node == null){
            last = null;
        }else{
            //新的头节点前一个节点就为null了
            node.next.pre = null;
            //修改头节点
            first = node.next;
        }
        return node;
    }

    //删除其他指定节点
    public Node removeNode(long value){
        //头节点
        Node node = first;
        //临时节点,记录每次查找节点的前一个节点
        //Node tmp = first;
        if (node == null){
            return null;
        }
        while (node.data != value){
            if (node.next == null){
                return null;
            }
            //tmp = node;
            node = node.next;
        }
        //删除节点
        if (node == first){
            first = first.next;
            first.pre = null;
        }else{
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node;
    }

    //从尾部进行删除
    public Node removeLast(){
        //尾节点
        Node node = last;

        if (first.next == null){
            first = null;
        }else{
            //尾节点的前一个节点的next为null
            node.pre.next = null;
            //尾节点的前一个节点成为新的尾节点
            last = node.pre;
        }
        return node;
    }

    //从头节点开始遍历
    public void show(){
        //先获取头节点
        Node node = first;
        if (node == null) {
            System.out.println("链表为空");
        }
        //如果头节点不为空再打印
        while (node != null){
            node.display();
            node = node.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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

3.测试链表

public class Test {
    public static void main(String[] args) {
        DoubleLinkList list = new DoubleLinkList();

        //从头部插入数据
        list.insertFirst(2);
        list.insertFirst(4);
        list.insertFirst(6);
        list.show(); //6 4 2

        //从尾部插入数据
        list.insertLast(1);
        list.insertLast(3);
        list.insertLast(5);
        list.show(); //6 4 2 1 3 5

        //查找节点
        Node node = list.find(1);
        if (node == null){
            System.out.println("找不到节点");
        }else{
            System.out.println("找到节点: "+node.data); //找到节点: 1
        }

        //从删除头节点
        Node first = list.removeFirst();
        if (first == null){
            System.out.println("找不到头节点");
        }else{
            System.out.println("删除的头节点: "+first.data); //删除的头节点: 6
        }
        list.show();  //4 2 1 3 5

        //删除其他指定节点
        Node removeNode = list.removeNode(1);
        if (removeNode == null){
            System.out.println("找不到节点");
        }else{
            System.out.println("删除的节点: "+removeNode.data); //删除的节点: 1
        }
        list.show();  //4 2 3 5

        //从尾部进行删除
        Node last = list.removeLast();
        if (last == null){
            System.out.println("找不到尾节点");
        }else{
            System.out.println("删除的尾节点: "+last.data); //删除的尾节点: 5
        }
        list.show();  //4 2 3

    }
}

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