线性表之链表中篇

一、双向链表

双向链表也叫双向表，是链表的一种，它由多个节点组成，每个节点都由一个数据域和两个指针域组成，数据域用来存储数据，其中一个指针域用来指向其后继节点，另一个指针用来指向前驱节点。链表的头节点的数据域不存储数据，指向前驱节点的指针域值为 null ，指向后继节点的指针域指向第一个真正存储数据的节点，如下图：

image-20221206213524158.png

1.1、节点 API 设计

类名 Node<T>
构造方法 Node(T t,Node next) ：创建 Node 对象
成员变量 T item ：存储数据
Node next ：指向下一个节点
Node pre ：指向上一个节点

1.2、双向链表 API 设计

类名 TwoWayLinkList<T>
构造方法 TwoWayLinkList() ：创建 TwoWayLinkList 对象
成员方法 1、public void clean() ：清空线性表
2、public boolean isEmpty() ：线性表是否为空
3、public int length() ：获取线性表元素的个数
4、public T get(int i) ：获取线性表中第 i 个位置元素的值
5、public void insert(int i,T t) ：在第 i 个元素之前插入一个值为 t 的数据元素
6、public void insert(T t) ：向线性表中添加一个元素 t
7、public T remove(int i) ：删除并返回线性表中第 i 个位置的数据元素
8、public int indexOf(T t) ：返回线性表中首次出现的指定的数据元素的位序号，若不存在，则返回 -1
9、public T getFirst() ：获取第一个元素
10、public T getLast() ：获取最后一个元素
成员内部类 private class Node<T> ：节点类
成员变量 1、private Node first ：记录头节点
2、private Node last ：记录尾节点
3、private int N ：记录链表的长度

1.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
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
public class TwoWayLinkList<T>{

    //记录头节点
    private Node first;
    //记录尾节点
    private Node last;
    //记录链表的长度
    private int N;

		//节点类
    private class Node{
        private T item;
        private Node pre;
        private Node next;

        public Node(T item,Node pre,Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    public TwoWayLinkList() {
        first = new Node(null, null, null);
        last = null;
        N = 0;
    }

    public void clear(){
        first.next = null;
        last = null;
        N = 0;
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public int length(){
        return N;
    }

    public T getFirst(){
        if(isEmpty()) return null;
        return first.next.item;
    }

    public T getLast(){
        if(isEmpty())return null;
        return last.item;
    }

    public T get(int i){
        Node temp = first.next;
        for (int j = 0; j < i; j++) {
            temp = temp.next;
        }
        return temp.item;
    }

    public void insert(T t){
        if(isEmpty()){
            //创建一个新节点
            Node newNode = new Node(t, first, null);
            //将其赋值给 last
            last = newNode;
            //头节点的next指向尾节点即可
            first.next = last;
        }else {
            Node oldLast = last;
            Node newNode = new Node(t, oldLast, null);
            oldLast.next = newNode;
            last = newNode;
        }
        N++;
    }

    public void insert(int index,T t){
        if(index >= N)return;
        Node pre = first;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node current = pre.next;
        Node newNode = new Node(t, pre, current);
        pre.next = newNode;
        current.pre = newNode;
        N++;
    }

    public int indexOf(T t){
        Node temp = first;
        for (int i = 0;temp.next != null;i++){
            temp = temp.next;
            if(temp.next.item.equals(t)){
                return i;
            }
        }
        return -1;
    }

    public T remove(int index){
        if(index >= N) return null;
        Node pre = first;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node current = pre.next;
        Node nextNode = current.next;
        pre.next = nextNode;
        nextNode.pre = pre;
        N--;
        return current.item;
    }
}

1.4、双向链表遍历

我们也让 TwoWayLinkList 支持增强 for 循环：

1、让 TwoWayLinkList 实现 Iterable 接口，重写 iterator 接口

2、在 TwoWayLinkList 内部提供一个内部类 TIterator，实现 Iterator 接口，重写 hasNext() 方法和 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
public class TwoWayLinkList<T> implements Iterable<T>{

    //记录头节点
    private Node first;
    //记录尾节点
    private Node last;
    //记录链表的长度
    private int N;


    private class Node{
        private T item;
        private Node pre;
        private Node next;

        public Node(T item,Node pre,Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    public TwoWayLinkList() {
        first = new Node(null, null, null);
        last = null;
        N = 0;
    }

    public void clear(){
        first.next = null;
        last = null;
        N = 0;
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public int length(){
        return N;
    }

    public T getFirst(){
        if(isEmpty()) return null;
        return first.next.item;
    }

    public T getLast(){
        if(isEmpty())return null;
        return last.item;
    }

    public T get(int i){
        Node temp = first.next;
        for (int j = 0; j < i; j++) {
            temp = temp.next;
        }
        return temp.item;
    }

    public void insert(T t){
        if(isEmpty()){
            //创建一个新节点
            Node newNode = new Node(t, first, null);
            //将其赋值给 last
            last = newNode;
            //头节点的next指向尾节点即可
            first.next = last;
        }else {
            Node oldLast = last;
            Node newNode = new Node(t, oldLast, null);
            oldLast.next = newNode;
            last = newNode;
        }
        N++;
    }

    public void insert(int index,T t){
        if(index >= N)return;
        Node pre = first;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node current = pre.next;
        Node newNode = new Node(t, pre, current);
        pre.next = newNode;
        current.pre = newNode;
        N++;
    }

    public int indexOf(T t){
        Node temp = first;
        for (int i = 0;temp.next != null;i++){
            temp = temp.next;
            if(temp.next.item.equals(t)){
                return i;
            }
        }
        return -1;
    }

    public T remove(int index){
        if(index >= N) return null;
        Node pre = first;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }
        Node current = pre.next;
        Node nextNode = current.next;
        pre.next = nextNode;
        nextNode.pre = pre;
        N--;
        return current.item;
    }

    //================================== 新增部分代码 start =================================
    @NonNull
    @Override
    public Iterator<T> iterator() {
        return new TIterator();
    }

    private class TIterator implements Iterator<T>{

        private Node temp;

        public TIterator() {
            temp = first;
        }

        @Override
        public boolean hasNext() {
            return temp.next != null;
        }

        @Override
        public T next() {
            temp = temp.next;
            return temp.item;
        }
    }
    //================================== 新增部分代码 end =================================
}

1.5、双向链表测试

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
public class Test {
    public static void main(String[] args) {
        TwoWayLinkList<String> strList = new TwoWayLinkList<>();
        //1、插入元素
        strList.insert("姚明");
        strList.insert("科比");
        strList.insert("麦迪");
        strList.insert(1,"詹姆斯");
        for (String s : strList) {
            System.out.println(s);
            //姚明
            //詹姆斯
            //科比
            //麦迪
        }
        //2、获取头节点元素
        System.out.println("获取头节点元素：" + strList.getFirst());//获取头节点元素：姚明
        //3、获取尾节点元素
        System.out.println("获取尾节点元素：" + strList.getLast());//获取尾节点元素：麦迪
        //4、获取元素
        String result = strList.get(1);
        System.out.println(result);//詹姆斯
        //5、删除元素
        String removeElement = strList.remove(0);
        System.out.println(removeElement);//姚明
        //6、测试清空
        strList.clear();
        System.out.println(strList.length());//0
    }
}

二、双向链表复杂度分析

2.1、get(i) 方法时间复杂度

get(i) 每一次查询，都要从链表的头开始，依次向后查询，随着数据元素 N 的增加，比较的元素也越多，时间复杂度为 O(n)

2.2、insert(int i,T t) 方法时间复杂度

insert(int i,T t) 每一次插入，需要先找到 i 位置的前一个元素，然后完成插入操作，随着数据元素 N 的增多，查找的元素越多，时间复杂度为 O(n)

2.3、remove(int i) 方法时间复杂度

remove(int i) 每一次删除，需要先找到 i 位置的前一个元素，然后完成移除操作，随着数据元素 N 的增多，查找的元素越多，时间复杂度为 O(n)

结合我们对单向链表的时间复杂度分析，可以发现双向链表和单向链表的时间复杂度是一样的

三、总结

本篇文章我们介绍了：

1、单向链表 API 设计，节点 API 设计，具体实现，以及添加了支持增强 for 循环，最后进行了测试用例测试

2、双向链表时间复杂度分析，结合前面讲的单向链表的时间复杂度，可发现，它们两时间复杂度是一样的

好了，本篇文章到这里就结束了，感谢你的阅读🤝

数据结构和算法 > 数据结构
#原创 #数据结构和算法
线性表之链表中篇
https://sweetying520.github.io/2022/08/05/D2.2-线性表之链表中篇/
作者
sweetying
发布于
2022年8月5日
许可协议