谈谈数据结构中的链表、节点

2021年5月25日20:43:25
评论
42 989字

今天刷题的时候再次遇到了链表,由于本人是自学,网上搜了很多关于链表的概念,有些感觉写的不错,有些云里雾里自己说错了都不知道,这里对链表这个结构做个详细的说明。

单链表

单链表中的每个结点包含值val,还包含链接到下一个结点的引用字段next。通过这种方式,单链表将所有结点按顺序组织起来。

Java中对一个链表的典型定义如下:

public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

在大多数情况下,我们将使用头结点(第一个结点)来表示整个列表。

操作单链表

与数组不同,我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素,我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间,其中 N 是链表的长度。

例如,在上面的示例中,头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点(结点 6); 然后使用结点 6 的“next”字段,我们能够访问第 3 个结点。

  • 往后添加节点

如果给了节点pre,怎么给它的下一个节点赋值x呢?

思路是新建一个节点cur,值为x,然后向后链接pre.next,再向前链接pre,这样自己就变成了pre的下一个节点了。

与数组不同的是,链表不需要将所有元素移动到插入元素之后。因此可以在 O(1) 时间复杂度中将新结点插入到链表中,这非常高效。

  • 开头添加节点

我们使用头结点来代表整个列表。因此,在列表开头添加新节点时更新头结点 head 至关重要

思路:

  1. 初始化一个新结点 cur ;
  2. 将新结点链接到我们的原始头结点 head
  3. 将 cur 指定为 head 。

例如,让我们在列表的开头添加一个新结点 9 。

1、我们初始化一个新结点 9 并将其链接到当前头结点 23 。

2、指定结点 9 为新的头结点。

  • 删除中间节点

思路:找到cur的上一个节点pre和自身的下一个节点cur.next,然后将pre.next = cur.next即可。跳过cur

需要从头结点遍历链表,时间复杂度为O(n),n是链表长度。空间为O(1),只需要常量空间来存指针。

  • 删除第一个节点

直接head = head.next即可。

  • 删除最后节点

遍历找到倒数第二个节点(cur.next.next=null),将倒数第二个节点指向null,再将最后一个节点指向原来的倒数第二个节点

您可能感兴趣的文章

匿名

发表评论

匿名网友