【Java数据结构】线性表-链表_java接口实现线性表和链表

作者：煮酒与君饮 | 2024-08-11 21:38:11

踩

java接口实现线性表和链表

线性表-链表

链表的概念及结构
实现无头单向非循环链表
LinkedList 模拟实现
ArrayList和LinkedList的区别

链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

链表在物理上不连续在逻辑上连续
在这里插入图片描述
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环

在这么多链表结构中我们主要学习两种

**无头单向非循环链表：**无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
无头双向链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

实现无头单向非循环链表

public class SingleLinkedList {
    //头插法
    public void addFirst(int data){
    }
    //尾插法
    public void addLast(int data){
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key){
    }
    //删除所有值为key的节点
    public void removeAllKey(int key){
    }
    //得到单链表的长度
    public int size(){
        return -1;
    }
    public void clear() {
    }
    public void display() {}
}
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

实现上面的接口即可

public class SingleLinkedList {

	//内部类 实现了一个节点
    static class ListNode {
        public int val;
        //节点的值
        public ListNode next;
        //节点中储存了下一个节点的地址
        public ListNode(int val) {
            this.val = val;
        }
        //初始化节点的构造方法
    }
    //永远指向头节点
    public ListNode head;

	//打印链表中所有节点的值
    public void show() {
        ListNode cur = head;
        //记录头节点的位置 遍历不改变头节点位置
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
            //当cur不为空时 打印每个节点的val值 使cur指向下一个节点
        }
        System.out.println();
    }
	

    //头插法
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        //新建一个节点 将这个节点头插
        node.next = head;
        //将新节点指向头节点 成为新的头节点
        head = node;
        //head永远指向头节点 head也改为node
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        //新建一个节点 将这个节点尾插
        if (head == null) {
            head = node;
            //如果此时链表为空 那么该节点就是新的头节点
            return;
        }
        ListNode cur = head;
        //记录头节点
        while (cur.next != null) {
            cur = cur.next;
        }
        //此时cur指向的就是最后一个节点
        //只需要把最后一个节点指向node
        cur.next = node;
    }

    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index, int data) {
        int len = size();
        //判断下标的合法性
        if (index < 0 || index > len) {
            throw new IndexOutOfBoundsExcption("在任意位置插入数据时，index位置不合法: " + index);
        }
        //如果插入位置时头位置 则是头插
        if (index == 0) {
            addFirst(data);
        }
        //如果插入位置时尾部 则是尾插
        if (index == len) {
            addLast(data);
        }
    }

    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if (head == null) {
            return;
        }
        //如果头节点是要移除的节点
        if (head.val == key) {
            head = head.next;
            return;
        }
        ListNode prev;
    }

    //查找目标节点的上一个节点
    private ListNode searchPrev(int key) {
        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == key) {
                return prev;
            } else {
                prev = prev.next;
            }
        }
        return null;
    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if (head != null) {
            return;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while (cur != null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if (head.val == key) {
            head = head.next;
        }
    }

    //得到单链表的长度
    public int size() {
        int count = 0;
        ListNode cur = head;
        //如果是引用类型用equals比较
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void clear() {
        //this.head = null;
        while (head != null) {
            ListNode headNext = head.next;
            head.next = null;
            head = headNext;
        }
    }

    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

LinkedList 模拟实现

LinkedList的底层是双向链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

public class MyLinkedList {
    static class ListNode {
        public int val;
        public ListNode prev;
        //储存上一个节点的位置
        public ListNode next;
        //储存下一个节点的位置

        public ListNode(int val) {
            this.val = val;
        }
    }

    //获取双向链表的长度 和双向无关
    public ListNode head;
    public ListNode last;

    //获取链表的长度
    public int size() {
        int len = 0;
        ListNode cur = head;
        //遍历链表求长度
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        return len;
    }

    //打印链表内容
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val);
            cur = cur.next;
        }
        System.out.println();
    }

    //查找某个关键字key是否在链表中
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    //头插
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        //如果链表为空 插入的同时初始化头节点和尾节点
        if (head == null) {
            head = node;
            last = node;
            return;
        }
        node.next = head;
        head.prev = node;
        head = node;
    }

    //尾插法
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            last = node;
            return;
        }
        node.prev = last;
        last.next = node;
        last = node;
    }


    public void addIndex(int index, int data) {
        int size = size();
        if (index < 0 || index > size) {
            throw new IndexOutOfBounds("双向链表index下标不合法：" + index);
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size) {
            addLast(data);
            return;
        }
        ListNode cur = head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        ListNode node = new ListNode(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    public void remove(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                //开始删除
                if (cur == head) {
                    //如果是头节点 删除头节点
                    head = head.next;
                    //如果删除后还有节点
                    if (head != null) {
                        head.prev = null;
                    } else {
                        last = null;
                        //此时head = head.next head已经为null
                        //只需要将last也置为null即可
                    }
                } else {
                    cur.prev.next = cur.next;
                    //将cur之前的节点next指向改为cur的下一个节点
                    //判断cur是否为尾节点
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                        //将后面节点的prev指向cur的prev
                    } else {
                        last = cur.prev;
                        //如果为最后一个节点 就把last向前移
                    }
                }
                return;
            } else {
                cur = cur.next;
            }
        }
    }
    public void removeAllKey(int key){
        ListNode cur = head;
        //逻辑和删除一个元素一模一样
        while (cur != null) {
            if (cur.val == key) {
                //开始删除
                if (cur == head) {
                    //如果是头节点 删除头节点
                    head = head.next;
                    //如果删除后还有节点
                    if (head != null) {
                        head.prev = null;
                    } else {
                        last = null;
                        //此时head = head.next head已经为null
                        //只需要将last也置为null即可
                    }
                } else {
                    cur.prev.next = cur.next;
                    //将cur之前的节点next指向改为cur的下一个节点
                    //判断cur是否为尾节点
                    if (cur.next != null) {
                        cur.next.prev = cur.prev;
                        //将后面节点的prev指向cur的prev
                    } else {
                        last = cur.prev;
                        //如果为最后一个节点 就把last向前移
                    }
                }
            }
            cur = cur.next;
        }
    }

    public void clear(){
        ListNode cur = head;
        while (cur != null){
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
        head = null;
        last = null;
    }
}


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

ArrayList和LinkedList的区别

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/煮酒与君饮/article/detail/966214