链表初识:概念、增删改查操作

链表

链表通常与数组一起比较,因为链表也是一种线性数据结构。

单链表示意图

链表中每个元素是一个单独的对象,在对象中存储着下一个对象的地址信息,形成链条,所有对象连接在一起。

链表有两种类型:单链表和双链表。双链表如下图所示:

双链表示意图

单链表

单链表的典型定义

Java定义:

// Definition for singly-linked list.
public class SinglyListNode {
    int val;
    SinglyListNode next;
    SinglyListNode(int x) { val = x; }
}

Python定义:

Definition for singly-linked list.
class ListNode:
 def __init__(self, x):
     self.val = x
     self.next = None

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

操作

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

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

0%