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

今天刷题的时候再次遇到了链表，网上搜了很多关于链表的概念，有些感觉写的不错，有些云里雾里，这里对链表这个结构做个详细的说明。

单链表

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

img

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的下一个节点了。

img

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

• 开头添加节点

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

思路：

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

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

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

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

img

• 删除中间节点

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

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

• 删除第一个节点

直接head = head.next即可。

• 删除最后节点

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