各位读者朋友们,
从今天开始,我将通过博文的形式,概述数据结构中应知必会的基本算法,
由于我更加熟悉 Java 语言,所以全程使用 Java 语言进行叙述,
如果您发现了文章中的错误,请您不吝赐教。
什么是链表?
“链表”(Linked List)是一种常见的数据结构,用于存储和组织数据。它是由一系列节点(Node)组成的,每个节点包含两部分:数据和指向下一个节点的引用(或指针)。每个节点中的数据可以是任意类型的数据,例如整数、字符、对象等。
链表中的节点通过指针相互连接,形成一个线性序列。与数组不同,链表的节点在内存中可以不连续存储,因为每个节点都包含指向下一个节点的指针,这使得链表具有动态分配内存的特性。
链表的主要特点是插入和删除操作的高效性。在链表中插入或删除节点时,只需要调整节点的指针,而不需要移动其他节点,这使得链表在频繁插入和删除操作时比数组更加高效。
链表的类型?
常见的链表类型有单向链表和双向链表:
- 单向链表(Singly Linked List):每个节点只包含一个指向下一个节点的指针。它的优点是节点占用的内存空间较小,但缺点是无法直接反向遍历链表。
- 双向链表(Doubly Linked List):每个节点包含两个指针,一个指向下一个节点,另一个指向前一个节点。这样可以实现双向遍历链表,但相应地,每个节点需要更多的内存空间来存储额外的指针。
单向链表的构建?
首先进行逐步分解,最后会给出完整代码。节点的构造如下:
static class Node { // 静态内部类
public int val;
public Node next;
Node(int x) { // 有参构造器
val = x;
next = null;
}
}
在堆内存中新建节点时,使用的是如下代码:
for (int i = 0; i < array.length; i++) {
Node newNode = new Node(array[i]);
}
由上述代码我们可以看出,每一次 for 循环都会产生一个新的 Node 类对象,此前存在栈中的 newNode 对象,一旦没有被引用,就会被 JVM 回收,所以在这里我们需要定义两个 Node 类 “指针” 对象,这里分别命名为 head 和 cur,head 对象作为头结点“指针”,持续指向头结点,而 cur 对象是为了保证新建的节点一直有被引用,不被 JVM 回收,代码及演示如下:
(演示是为了更容易理解,当值被赋予 null 时,在内存中其实没有指向关系)
Node head = null, cur = null;
接下来创建第一个 Node 节点,并改变“指针”的指向关系:
Node newNode = new Node(array[i]);
head = newNode;
cur = newNode;
此时,newNode 临时对象的任务就完成了,可以创建第二个节点了。由于 head 对象已经指向了头结点,所以后续该对象指向对象就不会再变化。而 cur 对象需要操作第一个节点的后继节点指向第二个节点的地址,代码实现及演示如下:
Node newNode = new Node(array[i]);
cur.next = newNode;
第一个节点已经配置完成,cur 可以指向第二个节点了,之后临时变量 newNode 继续弹栈、建立第三个节点、以此往复,直到循环结束:
cur = newNode;
Node newNode = new Node(array[i]);
随着此步骤的不断循环,最终就会建立一个链表,我们在 IDEA 中调试,可以发现这种链式结构:
文章来源:https://www.toymoban.com/news/detail-602988.html
最后,给出完整代码:文章来源地址https://www.toymoban.com/news/detail-602988.html
public static void main(String[] args) {
int[] a = {1, 2, 3, 4, 5, 6};
Node head = initLinkedList(a);
System.out.println(head);
}
private static Node initLinkedList(int[] array) {
Node head = null, cur = null;
for (int i = 0; i < array.length; i++) {
Node newNode = new Node(array[i]);
// newNode.next = null;
if (i == 0) {
head = newNode;
cur = newNode;
} else {
cur.next = newNode;
cur = newNode;
}
}
return head;
}
static class Node { // 静态内部类
public int val;
public Node next;
Node(int x) {
val = x;
next = null;
}
}
到了这里,关于[算法通关村] 1.1 单向链表的创建的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!