- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章java数据结构基础:单,双向链表由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
单向链表比顺序结构的线性表最大的好处就是不用保证存放的位置,它只需要用指针去指向下一个元素就能搞定.
图画的比较粗糙,简单的讲解一下:
上面四个长方形,每个长方形都是一个节点。在长方形中,一种包含两个东西,一个是当前节点的元素,一个是指向下一节点的地址。这个下一个节点的地址指向了下一个节点中的元素。以此类推.
在最左边的叫做头节点,同样,最后面的叫尾节点.
所以,我们所有的操作都是根据节点来进行操作.
这些代码都有很详细的注释,我就不做过多的解释了,你直接复制代码到本地idea运行一遍就全部知道了.
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
|
package
com.zxy.lianbiao;
/**
* @Author Zxy
* @Date 2021/2/3 21:25
* @Version 1.0
*/
/**
* 基于单向链表实现元素的存取
*
* @param <E>
*/
public
class
MySinglyLinkedList<E>
implements
MyList<E> {
/**
* 定义单向链表中的节点对象
*/
class
Node<E> {
private
E item;
// 存储元素
private
Node next;
// 存储下一个节点对象
public
Node(E item, Node next) {
this
.item = item;
this
.next = next;
}
}
private
Node head;
// 存放链表中的头节点
private
int
size;
// 记录元素的个数
/**
* 向链表中添加元素
*
* @param element
*/
@Override
public
void
add(E element) {
// 创建节点
Node<E> node =
new
Node<>(element,
null
);
// 找到尾节点
Node tail = getTail();
// 节点的挂接
if
(tail ==
null
) {
// 如果没有尾节点,那意思就是头节点都不存在
// 没有头节点,那么就把创建的节点给头节点
this
.head = node;
}
else
{
tail.next = node;
}
// 记录元素的个数
this
.size++;
}
/**
* 找尾节点
*/
private
Node getTail() {
// 判断头节点是否存在
if
(
this
.head ==
null
) {
return
null
;
}
// 查找尾节点
Node node =
this
.head;
while
(
true
) {
if
(node.next ==
null
) {
break
;
}
node = node.next;
// 移动指针指向下一个
}
return
node;
}
/**
* 根据元素的位置获取元素
*
* @param index
* @return
*/
@Override
public
E get(
int
index) {
// 校验index的合法性
this
.checkIndex(index);
// 根据位置获取指定节点
Node<E> node =
this
.getNode(index);
// 将该节点中的元素返回
return
node.item;
}
/**
* 对index进行校验
*/
private
void
checkIndex(
int
index) {
// 0<=index<size
if
(!(index >=
0
&& index <
this
.size)) {
throw
new
IndexOutOfBoundsException(
"Index: "
+ index +
" this.size: "
+
this
.size);
}
}
/**
* 根据位置获取节点
*/
private
Node<E> getNode(
int
index) {
Node<E> node =
this
.head;
for
(
int
i =
0
; i < index; i++) {
node = node.next;
}
return
node;
}
/**
* 获取元素的个数
*
* @return
*/
@Override
public
int
size() {
return
this
.size;
}
/**
* 根据元素位置删除元素
*
* @param index
* @return
*/
@Override
public
E remove(
int
index) {
// 校验index合法性
this
.checkIndex(index);
// 根据位置找到节点对象
Node<E> node = getNode(index);
// 获取该节点对象中的元素
E item = node.item;
// 将该节点对象从单向链表中移除
// 判断当前删除的节点是否为头节点
if
(
this
.head == node) {
this
.head = node.next;
}
else
{
Node<E> temp =
this
.head;
for
(
int
i =
0
; i < index -
1
; i++) {
temp = temp.next;
// 此时的temp就是要删除的那个节点的前一个节点
}
temp.next = node.next;
// 将当前节点的前一个节点指向当前节点的后一个节点
}
// 然后将当前节点的下一个节点指向null
node.next =
null
;
// 记录元素个数
this
.size--;
// 将该元素返回
return
item;
}
/**
* 插入节点思路:如果当前共有三个节点分别是1,2,3,在1和2的中间插入4,原本的指向是1->2 现改变成1->4 4->2 先获取到指定位置的node,再获取到前一个位置的node和下一个位置的node
*/
public
void
insert(
int
index, E element) {
// 先根据要插入的位置拿到这个位置的节点对象
Node<E> item = getNode(index);
// 根据插入的元素新建一个节点
Node<E> eNode =
new
Node<>(element,
null
);
// 如果是头节点,那么就找不到前一个,直接把这个赋值给head
if
(index ==
0
){
// index==0代表是替换掉头节点
this
.head = eNode;
eNode.next = item;
this
.size++;
}
else
{
// 根据当前的节点对象去找到前一个节点对象和后一个节点对象
Node<E> before =
this
.head;
// 根据头节点去找
for
(
int
i =
0
; i < index -
1
; i++) {
before = before.next;
// 此时的before就是当前节点的前一个节点
}
before.next = eNode;
eNode.next = item;
this
.size++;
}
}
public
static
void
main(String[] args) {
MySinglyLinkedList<String> list =
new
MySinglyLinkedList<>();
System.out.println(
"添加节点开始------------------------"
);
list.add((String)
"a"
);
list.add((String)
"b"
);
list.add((String)
"c"
);
list.add((String)
"d"
);
System.out.println(
"添加节点完成-------------------------\n"
);
System.out.println(
"插入指定的元素"
);
list.insert(
0
,
"f"
);
for
(
int
i =
0
; i < list.size; i++) {
System.out.println(list.get(i));
}
}
}
|
昨天写完单向链表和栈结构之后,看了看程杰大大的书中有介绍双向链表的部分。虽然是c语言写的,但是我还是用Java给翻译出来了.
思路如下:
首先,双向链表和单向链表的最大区别就是,双向链表比单链表多了个指向前一节点的指针。代码量其实并不比单链表多很多,只是思路的转变需要克服一下.
其次就是在插入元素的时候,我们可以在链表的头部插入,也可以在链表的尾部插入(因为有两个指针嘛) 。
代码其实和单链表差不多,如果感兴趣的话可以去看看我之前写的单链表的文章。虽然文笔很烂,但是代码货真价实.
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
|
package
com.zxy.lianbiao;
/**
* @Author Zxy
* @Date 2021/2/4 20:11
* @Version 1.0
*/
/**
* 基于双向链表实现元素存取的容器
*
* @param <E>
*/
public
class
MyDoublyLinkedList<E>
implements
MyList<E> {
/**
* 定义双向链表节点对象
*/
class
Node<E> {
E item;
// 记录元素
Node<E> prev;
// 记录前一个节点对象
Node<E> next;
// 记录下一个节点对象
public
Node(Node<E> prev, E item, Node<E> next) {
this
.item = item;
this
.prev = prev;
this
.next = next;
}
}
private
Node head;
// 记录头节点
private
Node tail;
// 记录尾节点
private
int
size;
// 记录元素个数
/**
* 向双向链表中添加元素的方法
*
* @param element
*/
@Override
public
void
add(E element) {
linkLast(element);
}
/**
* 将节点对象添加到双向链表的尾部
*/
private
void
linkLast(E element) {
Node t =
this
.tail;
// 获取尾节点
Node<E> node =
new
Node<>(t, element,
null
);
// 创建节点对象
this
.tail = node;
// 将新节点定义为尾节点 因为原来的尾节点被这个新节点替代了
if
(t ==
null
) {
// 说明一个节点都没有,这个还得是头节点
this
.head = node;
}
else
{
t.next = node;
}
this
.size++;
}
/**
* 根据指定位置获取元素
*
* @param index
* @return
*/
@Override
public
E get(
int
index) {
this
.checkIndex(index);
// 根据位置查找节点对象
Node<E> node =
this
.getNode(index);
return
node.item;
}
/**
* 对index的合法性校验
*/
private
void
checkIndex(
int
index) {
if
(!(index >=
0
&& index <
this
.size)) {
throw
new
IndexOutOfBoundsException();
}
}
/**
* 根据位置获取指定节点对象
*/
private
Node getNode(
int
index) {
// 判断当前位置距离头或者尾哪个节点更近 使用二分法
if
(index < (
this
.size >>
1
)) {
Node node =
this
.head;
for
(
int
i =
0
; i < index; i++) {
node = node.next;
}
return
node;
}
else
{
Node node =
this
.tail;
for
(
int
i =
this
.size -
1
; i > index; i--) {
node = node.prev;
}
return
node;
}
}
/**
* 返回元素的个数
*
* @return
*/
@Override
public
int
size() {
return
this
.size;
}
/**
* 删除元素
*
* @param index
* @return
*/
@Override
public
E remove(
int
index) {
// 对index进行合法性校验
this
.checkIndex(index);
Node node =
this
.getNode(index);
// 根据位置获取到节点对象
// 获取节点对象的元素
E item = (E) node.item;
// 判断当前节点是否为头节点
if
(node.prev ==
null
) {
this
.head = node.next;
}
else
{
node.prev.next = node.next;
}
// 判断当前节点是否为尾节点
if
(node.next ==
null
) {
// node.prev.next = null;
this
.tail = node.prev;
}
else
{
node.next.prev = node.prev;
}
// 当前节点断掉与他后继节点的连接
node.next =
null
;
// 当前节点断掉与直接前驱节点的连接
node.prev =
null
;
node.item =
null
;
this
.size--;
return
item;
}
/**
* 在双向链表的头添加元素
*/
public
void
addFirst(E element) {
this
.linkFirst(element);
}
/**
* 在链表的头添加元素
*
* @param element
*/
public
void
linkFirst(E element) {
// 获取头节点对象
Node head =
this
.head;
Node<E> eNode =
new
Node<>(
null
, element, head);
// 将新节点定义为头节点
this
.head = eNode;
if
(head ==
null
) {
// 如果为空,说明该链表中一个节点都没有 也就是该头节点也是尾节点
this
.tail = eNode;
}
else
{
head.prev = eNode;
}
this
.size++;
}
/**
* 在链表的尾部添加元素
*
* @param element
*/
public
void
addLast(E element) {
this
.linkLast(element);
}
public
static
void
main(String[] args) {
MyDoublyLinkedList<String> list =
new
MyDoublyLinkedList<>();
list.add(
"a"
);
list.add(
"b"
);
list.add(
"c"
);
list.add(
"d"
);
list.add(
"e"
);
System.out.println(list.remove(
2
));
System.out.println(list.size);
for
(
int
i =
0
; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
}
|
本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注我的更多内容! 。
原文链接:https://blog.csdn.net/weixin_43581288/article/details/113660067 。
最后此篇关于java数据结构基础:单,双向链表的文章就讲到这里了,如果你想了解更多关于java数据结构基础:单,双向链表的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
前言:笔记是参考B站up主尚硅谷,图片、代码都是哦。在blog写笔记~(图片、代码来源尚硅谷,侵权必删!) 尚硅谷数据结构学习路线B站网站:https://www.bilibili.com/video
这个问题不太可能对任何 future 的访客有帮助;它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关,通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用,visit the
我想创建一个没有全局变量的单个链表。我用 NULL 初始化了第一个元素,然后想将第一个元素 node 复制到 list_。它被复制到函数中,但副作用不起作用。在我的主函数中,该值仍然是NULL。如果我
我正在尝试使链表与此处的链表相似: linked list in C 那就是在另一个结构中有“头”,我首先称它为“头”。但是我发现做那个改变。很难向 list_item 结构添加值。我已经尝试了一些东
我正在尝试理解链表的代码。我明白他们是如何工作的。我正在查看一些与动态内存和链表有关的代码,我在此处对其进行了简化: #include #include typedef struct nod
有人可以解释下面的代码吗?我是 C 的新手,正在努力弄清楚。为什么我们最后有 queueNodeT? typedef char queueElementT; typedef struct queueN
场景如下:- 我想反转单链表的方向,换句话说,反转后所有指针现在应该指向后.. 这个算法应该需要线性时间。 我想到的解决方案是使用另一个数据结构 A Stack.. 借助它可以轻松反转单向链表,所有指
在 python 中使用链表最简单的方法是什么?在 scheme 中,链表由 '(1 2 3 4 5) 定义。 Python 的列表 [1, 2, 3, 4, 5] 和元组 (1, 2, 3, 4,
本文首发公众号:小码A梦 一般数据主要存储的形式主要有两种,一种是数组,一种是链表。数组是用来存储固定大小的同类型元素,存储在内存中是 一片连续 的空间。而链表就不同于数组。链表
虽然之前有人问过关于链表与数组的问题,但答案大多归结为我们大多数人在某个时候可能已经学到的东西: 列表擅长插入和删除 数组擅长随机访问 现在像 Bjarne Stroustrup 这样受人尊敬的人有
位置 在堆中,碎片化(每个节点的 malloc) - 在几种不同的方式(缓慢分配,缓慢访问,内存碎片)方面效率低下 在堆中,在一个大块中 - 当需要重新分配 时,数据结构获得的所有灵活性都将丢失 在堆
我完成了泛型的学习,但并不容易。不过,我确实明白了。这是我的理解。我希望您纠正我的错误并回答几个问题:)。 public class LinkedList { //class definition }
我将如何创建一个链接列表来在 OCaml 中保存我的数据?我正在尝试制作一个单链表,但是我遇到了语法问题。我只想制作一个模块来简单地从链表中获取'a,插入'a或删除'a。 有人知道吗? 最佳答案 正如
我在使用这段代码时遇到了问题,我不确定我做错了什么 #include #include #include #include typedef struct flight_struct{
我正在创建一个函数来删除给定列表的最后一个节点(作为参数输入)。该函数本身非常简单,如下所示。 function popBack(list) { var current = list.head
我正在尝试开发一种方法,该方法将在链接列表中的当前节点之前插入传递给它的节点。它有3个条件。对于此实现,不能有任何头节点(仅对列表中第一个节点的引用),并且我无法添加更多变量。 如果列表为空,则将传递
使用 scala,我已将大约 100000 个节点添加到链表中。当我使用函数 length 时,例如 mylist.length。我收到“java.lang.StackOverflowError”错误
所以我正在学习处理链表。我将如何递归地添加节点内的项目。我可以通过执行 sum = h.item +h.next.item+h.next.next.item 添加它们,但这只有在我有小的链接列表时才有
所以我一直在努力理解链表的概念(一直在看一些示例代码,我在互联网上找到了这个。现在如果我能请别人确认我是否正确掌握了一些概念。我将绘制图表,说明我认为每个代码链接的作用。 #include #inc
已关闭。这个问题是 not reproducible or was caused by typos 。目前不接受答案。 这个问题是由拼写错误或无法再重现的问题引起的。虽然类似的问题可能是 on-top
我是一名优秀的程序员,十分优秀!