双向链表代码实现和详解—java实现_java 双向链表遍历

目录
　　一 .双向链表的优点
　　二 .插入
　　三 .遍历
　　四 .删除
　　五 .代码清单
　　六 .总结

双向链表的优点

　　传统的链表沿着链表的反向遍历是困难的，以及操作某个节点的前一个元素，也是十分的困难。
　　双向链表提供了这些能力，即可以向前遍历，也可以向后遍历。其中实现在于每个链节点有两个指向其它节点的引用。一个指向前驱节点，一个像传统链表一样指向后继节点。如图：
　　
　　双向链表的节点类是这样声明的：
　　

class Link <T>{
    public T val;
    public Link<T> next;
    public Link<T> pre;

    public Link(T val) {
        this.val = val;
    }
 ｝
1
2
3
4
5
6
7
8
9

插入

　　双向链表的缺点就是：每次插入和删除操作时，要处理四个节点的引用，而不是两个。
　　
　　两个连接前一个链节点，两个连接后一个链接点。当然 ，由于多了两个链节点的引用，链节点占用的空间也会变大。

　　双向链表由于前驱指针的存在，可以多种方式插入。addFrist()头插，addLast()尾插，在特定元素之前插入addBefore()，在特定元素之后插入addAfter()。
　　对于头插，如图：
　　
　　插入的新节点的next是未插入之前的frist节点。
　　如果链表是空的，last需要改变。如果链表非空，frist.pre字段改变。
　　

        Link<T> newLink= new Link(value);
        if(isEmpty()){ // 如果链表为空
            last = newLink; //last -> newLink
        }else {
            frist.pre = newLink; // frist.pre -> newLink
        }
        newLink.next = frist; // newLink -> frist
        frist = newLink; // frist -> newLink
1
2
3
4
5
6
7
8

addLast()，也是同样的过程，不过是对last指针的应用。

addAfter()在某个特定节点之后插入一个节点。需要建立4个引用的连接。首先找到该特定的节点。然后假设插入的位置不在表尾，首先建立新节点和下一个节点之间的两个连接，接着是建立当前结点所指节点与新节点之间的两个连接。如图：

   Link<T> cur = frist;
        while(cur.val!=key){ //经过循环，cur指针指向指定节点
            cur = cur.next;
            if(cur == null){ // 找不到该节点
                throw new RuntimeException("Node is not exists");
            }
        }
        Link<T> newLink = new Link<>(value);
        if (cur == last){ // 如果当前结点是尾节点
            newLink.next = null; // 新节点指向null
            last =newLink; // last指针指向新节点
        }else {
            newLink.next = cur.next; //新节点next指针，指向当前结点的next
            cur.next.pre = newLink; //当前结点的前驱指向新节点
        }
        newLink.pre = cur;//当前结点的前驱指向当前结点
        cur.next = newLink; //当前结点的后继指向新节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在特定节点之前插入也是类似，只是要找到cur.next == 特定的节点，然后和之后插入类似。就是得判断first元素是不是特点元素。

遍历

遍历可以按first开始遍历，使用next引用。也可以按last反向遍历，使用pre引用。

    public void displayForward(){
        Link<T> cur = frist;
        while(cur!=null){
            cur.displayCurrentNode();
            cur = cur.next;
        }
        System.out.println();

    }
    public void displayBackward(){
        Link<T> cur = last;
        while(cur!=null){
            cur.displayCurrentNode();
            cur = cur.pre;
        }
        System.out.println();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

删除

删除可以有三种方式，deleteFrist() ，deleteLast()，deleteKey()。前两种删除较为简单，后一种如图：

删除任意节点

   Link<T> cur = frist;
        while(cur.val!= key){
            cur = cur.next;
            if(cur == null){ //不存在该节点
                throw new RuntimeException("Node is not exists");
            }
        }
        if(cur == frist){ // 如果frist指向的节点
            frist = cur.next; //frist指针后移
        }else {
            cur.pre.next = cur.next;//前面节点的后继指向当前节点的后一个节点
        }
        if(cur == last){ // 如果当前节点是尾节点
            last = cur.pre; // 尾节点的前驱前移
        }else {
            cur.next.pre = cur.pre; //后面节点的前驱指向当前节点的前一个节点
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

完整代码清单，包括讨论的代码

import org.junit.Test;

import java.io.IOException;

/**
 * @author 
 * @date 2018/4/2  22:15
 */

public class DoublyLinkList<T>{
    private Link<T> frist;
    private Link<T> last;
    public DoublyLinkList(){//初始化首尾指针
        frist = null;
        last = null;
    }

    public boolean isEmpty(){
        return frist == null;
    }

    public void addFrist(T value){
        Link<T> newLink= new Link(value);
        if(isEmpty()){ // 如果链表为空
            last = newLink; //last -> newLink
        }else {
            frist.pre = newLink; // frist.pre -> newLink
        }
        newLink.next = frist; // newLink -> frist
        frist = newLink; // frist -> newLink
    }

    public void addLast(T value){
        Link<T> newLink= new Link(value);
        if(isEmpty()){ // 如果链表为空
            frist = newLink; // 表头指针直接指向新节点
        }else {
            last.next = newLink; //last指向的节点指向新节点
            newLink.pre = last; //新节点的前驱指向last指针
        }
        last = newLink; // last指向新节点
    }

    public boolean addBefore(T key,T value){

        Link<T> cur = frist;
        if(frist.next.val == key){
            addFrist(value);
            return true;
        }else {
            while (cur.next.val != key) {
                cur = cur.next;
                if(cur == null){
                    return false;
                }
            }
            Link<T> newLink= new Link(value);
            newLink.next = cur.next;
            cur.next.pre = newLink;
            newLink.pre = cur;
            cur.next = newLink;
            return true;
        }
    }

    public void addAfter(T key,T value)throws RuntimeException{
        Link<T> cur = frist;
        while(cur.val!=key){ //经过循环，cur指针指向指定节点
            cur = cur.next;
            if(cur == null){ // 找不到该节点
                throw new RuntimeException("Node is not exists");
            }
        }
        Link<T> newLink = new Link<>(value);
        if (cur == last){ // 如果当前结点是尾节点
            newLink.next = null; // 新节点指向null
            last =newLink; // last指针指向新节点
        }else {
            newLink.next = cur.next; //新节点next指针，指向当前结点的next
            cur.next.pre = newLink; //当前结点的前驱指向新节点
        }
        newLink.pre = cur;//当前结点的前驱指向当前结点
        cur.next = newLink; //当前结点的后继指向新节点
    }

    public void deleteFrist(){
        if(frist.next == null){
            last = null;
        }else {
            frist.next.pre = null;
        }
        frist = frist.next;
    }

    public void deleteLast(T key){
        if(frist.next == null){
            frist = null;
        }else {
            last.pre.next = null;
        }
            last = last.pre;
    }

    public void deleteKey(T key)throws RuntimeException{
        Link<T> cur = frist;
        while(cur.val!= key){
            cur = cur.next;
            if(cur == null){ //不存在该节点
                throw new RuntimeException("Node is not exists");
            }
        }
        if(cur == frist){ // 如果frist指向的节点
            frist = cur.next; //frist指针后移
        }else {
            cur.pre.next = cur.next;//前面节点的后继指向当前节点的后一个节点
        }
        if(cur == last){ // 如果当前节点是尾节点
            last = cur.pre; // 尾节点的前驱前移
        }else {
            cur.next.pre = cur.pre; //后面节点的前驱指向当前节点的前一个节点
        }
    }

    public T queryPre(T value)throws IOException,RuntimeException{
        Link<T> cur = frist;
        if(frist.val == value){
            throw new RuntimeException("Not find "+value+"pre");
        }
        while(cur.next.val!=value){
            cur = cur.next;
            if(cur.next == null){
                throw new RuntimeException(value +"pre is not exeist!");
            }
        }

        return cur.val;
    }

    public void displayForward(){
        Link<T> cur = frist;
        while(cur!=null){
            cur.displayCurrentNode();
            cur = cur.next;
        }
        System.out.println();

    }
    public void displayBackward(){
        Link<T> cur = last;
        while(cur!=null){
            cur.displayCurrentNode();
            cur = cur.pre;
        }
        System.out.println();
    }

    @Test
    public void test()throws Exception{ // 自己测试代码
        DoublyLinkList<Integer> d = new DoublyLinkList<Integer>();
        d.addFrist(1);
//        d.addFirst(1);
        d.addFrist(2);
        d.addFrist(3);
        d.addLast(6);
        d.addFrist(4);
        d.addFrist(5);
        d.addLast(7);
        d.displayForward();
        System.out.println(d.queryPre(4));
        System.out.println(d.queryPre(0));
    }
}

class Link <T>{
    public T val;
    public Link<T> next;
    public Link<T> pre;

    public Link(T val) {
        this.val = val;
    }

    public void displayCurrentNode() {
        System.out.print(val + "  ");
    }
}
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

总结

　　链表是一种很简单的数据结构，我们学习的时候，需要冷静，我们不应该像到代码如何实现。应该是在我们写代码的时候，脑海中有一张清晰的操作流程，如果操作流程不是很熟悉，建议可以使用笔模拟一下。按照流程一步步的写出代码，问题 也随之解决了。
　　链表无非就抓住指针的移动，就能完成该有的操作。
　　
　　本文描述和实现的都是具有双端性质的双向链表。如果有朋友对不具有双端性质的传统双向链表有需求，戳这里。
　　
　　谢谢观看！