一只小码农

每天进步一点点

链表

发表于 分类于 Valine：
本文字数： 7.7k 阅读时长 ≈ 7 分钟
链表知识的学习

链表

单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。习惯于用头节点来代表整个单链表。

下面是一个单链表的例子：

screen-shot-2018-04-12-at-152754

蓝色箭头显示单个链接列表中的结点是如何组合在一起的。

1
2
3
4
5
public class SinglyListNode{
    int val;
    SinglyListNode next;    //定义对象，下一个节点
    SinglyListNode(int x){val=x;} 
}

单列表的操作

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

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

你可能想知道为什么链表很有用，尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。 在 插入和删除中，链表具有良好的性能。

操作一：添加元素cur在prev之后

image-20210113091359911

与数组对比，插入新元素不需要将插入节点后的所有元素都后移，因此，时间复杂度为O(1),

特殊情况

在开头添加结点：在列表开头添加新节点时更新头节点head至关重要。

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

在结尾添加节点

操作二：从单链表中删除现有结点cur

删除操作 - 单链表
如果我们想从单链表中删除现有结点 cur，可以分两步完成：

找到 cur 的上一个结点 prev 及其下一个结点 next ；

接下来链接 prev 到 cur 的下一个节点 next 。

在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。

空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

示例

让我们尝试把结点 6从上面的单链表中删除。

  1. 从头遍历链表，直到我们找到前一个结点 prev，即结点 23

    image-20210113092734343

  2. 将 prev（结点 23）与 next（结点 15）链接

    image-20210113092712828

结点 6 现在不在我们的单链表中。

特殊情况

删除第一个结点
如果我们想删除第一个结点，策略会有所不同。

正如之前所提到的，我们使用头结点 head 来表示链表。我们的头是下面示例中的黑色结点 23。

image-20210113092928077

如果想要删除第一个结点，我们可以简单地将下一个结点分配给 head。也就是说，删除之后我们的头将会是结点 6。

image-20210113092949088

链表从头结点开始，因此结点 23 不再在我们的链表中。

双链表

与单链表的区别在于：双链表除了有数据域和指向其后继的指针外，还有指向其前驱的指针。

所以，根据链接数的不同，可以将链表分为单链表、双链表、多重链表

LC设计链表

链表时一个包含零个或多个元素的数据结构。每个元素都包含一个值和到另一个元素的链接。根据链接数的不同，可以分为单链表，双链表和多重链表。

单链表是最简单的一种，它提供了在常数时间内的 addAtHead 操作和在线性时间内的 addAtTail 的操作。双链表是最常用的一种，因为它提供了在常数时间内的 addAtHead 和 addAtTail 操作，并且优化的插入和删除。

双链表在 Java 中的实现为 LinkedList，在 Python 中为 list。这些结构都比较常用，有两个要点：

1、哨兵节点：
哨兵节点在树和链表中被广泛用作伪头、伪尾等，通常不保存任何数据。

我们将使用伪头来简化我们简化插入和删除。在接下来的两种方法中应用此方法。

2、双链表的双向搜索：我们可以从头部或尾部进行搜索。

####在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

方式一：单链表实现

image-20210113095508745 

1
2
3
4
5
6
7
public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}      //声明结点

 
1
2
3
4
5
6
7
    int size;
    ListNode head;  //sentinel node as pseudo-head
    public MyLinkedList(){
        size = 0;
        head = new ListNode(0);
    }
}   //声明链表，用哨兵做伪头，这样确保链表中节点永远不为空
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
public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

class MyLinkedList {
  int size;
  ListNode head;  // sentinel node as pseudo-head
  public MyLinkedList() {
    size = 0;
    head = new ListNode(0);
  }

  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  public int get(int index) {
    // if index is invalid
    if (index < 0 || index >= size) return -1;

    ListNode curr = head;
    // index steps needed 
    // to move from sentinel node to wanted index
    for(int i = 0; i < index + 1; ++i) curr = curr.next;   //与删除不同，如果要获取指定索引处的节点，必须前进index+1步
    return curr.val;
  }

  /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  public void addAtHead(int val) {
    addAtIndex(0, val);
  }

  /** Append a node of value val to the last element of the linked list. */
  public void addAtTail(int val) {
    addAtIndex(size, val);
  }

  /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  public void addAtIndex(int index, int val) {
    // If index is greater than the length, 
    // the node will not be inserted.
    if (index > size) return;

    // [so weird] If index is negative, 
    // the node will be inserted at the head of the list.
    if (index < 0)  index = 0;
		++size;
    // find predecessor of the node to be added
    ListNode pred = head;    
    for(int i = 0; i < index; ++i) pred = pred.next;   //从头开始找给定索引处的前一个元素pred，

    // node to be added
    ListNode toAdd = new ListNode(val);    //新建一个节点
    // insertion itself
    toAdd.next = pred.next;  
    pred.next = toAdd;
  }

  /** Delete the index-th node in the linked list, if the index is valid. */
  public void deleteAtIndex(int index) {
    // if the index is invalid, do nothing
    if (index < 0 || index >= size) return;

    size--;
    // find predecessor of the node to be deleted
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;  //找到的是要删除节点的前一个节点

    // delete pred.next 
    pred.next = pred.next.next;
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/design-linked-list/solution/she-ji-lian-biao-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#####复杂度分析

时间复杂度：
addAtHead： \mathcal{O}(1)O(1)
addAtInder，get，deleteAtIndex: \mathcal{O}(k)O(k)，其中 kk 指的是元素的索引。
addAtTail：\mathcal{O}(N)O(N)，其中 NN 指的是链表的元素个数。
空间复杂度：所有的操作都是 O(1)O(1)。

####方式二：双链表实现

双链表比单链表快得多，测试用例花费的时间比单链表快了两倍。但是它更加复杂，它包含了 size，记录链表元素个数，和伪头伪尾。

image-20210113105525613

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
public class ListNode {
  int val;
  ListNode next;   //后继结点
  ListNode prev;   //前驱节点
  ListNode(int x) { val = x; }
}

class MyLinkedList {
  int size=0;
  // sentinel nodes as pseudo-head and pseudo-tail  --伪元素充当头结点和尾节点
  ListNode head, tail;
  public MyLinkedList() {
    size = 0;
    head = new ListNode(0);
    tail = new ListNode(0);
    head.next = tail;
    tail.prev = head;
  }

  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  public int get(int index) {
    // if index is invalid
    if (index < 0 || index >= size) return -1;

    // choose the fastest way: to move from the head
    // or to move from the tail    ----从后或者从前遍历，选择一个比较快速的遍历方向
    ListNode curr = head;
    if (index + 1 < size - index)
      for(int i = 0; i < index + 1; ++i) curr = curr.next;
    else {
      curr = tail;
      for(int i = 0; i < size - index; ++i) curr = curr.prev;
    }

    return curr.val;
  }

  /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  public void addAtHead(int val) {
    ListNode pred = head, succ = head.next;

    ++size;      //记得把链表长度更新一下
    ListNode toAdd = new ListNode(val);
    toAdd.prev = pred;
    toAdd.next = succ;
    pred.next = toAdd;
    succ.prev = toAdd;
  }

  /** Append a node of value val to the last element of the linked list. */
  public void addAtTail(int val) {
    ListNode succ = tail, pred = tail.prev;

    ++size;
    ListNode toAdd = new ListNode(val);
    toAdd.prev = pred;
    toAdd.next = succ;
    pred.next = toAdd;
    succ.prev = toAdd;
  }

  /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  public void addAtIndex(int index, int val) {
    // If index is greater than the length, 
    // the node will not be inserted.
    if (index > size) return;

    // [so weird] If index is negative, 
    // the node will be inserted at the head of the list.
    if (index < 0) index = 0;

    // find predecessor and successor of the node to be added   找到节点的前驱和后继
    ListNode pred, succ;
    if (index < size - index) {
      pred = head;
      for(int i = 0; i < index; ++i) 
          pred = pred.next;
      succ = pred.next;
    }
    else {
      succ = tail;
      for (int i = 0; i < size - index; ++i) succ = succ.prev;
      pred = succ.prev;
    }
	
    //先找到待插入元素的前驱与后继，然后在进行节点指向的变更
    // insertion itself
    ++size;        //注意长度的更新
    ListNode toAdd = new ListNode(val);
    toAdd.prev = pred;
    toAdd.next = succ;
    pred.next = toAdd;
    succ.prev = toAdd;
  }

  /** Delete the index-th node in the linked list, if the index is valid. */
  public void deleteAtIndex(int index) {
    // if the index is invalid, do nothing
    if (index < 0 || index >= size) return;

    // find predecessor and successor of the node to be deleted
    ListNode pred, succ;
    if (index < size - index) {
      pred = head;
      for(int i = 0; i < index; ++i) pred = pred.next;
      succ = pred.next.next;
    }
    else {
      succ = tail;
      for (int i = 0; i < size - index - 1; ++i) succ = succ.prev;
      pred = succ.prev.prev;
    }

    // delete pred.next 
    --size;
    pred.next = succ;
    succ.prev = pred;
  }
}

伪头和伪尾总是存在，MyLinkedList 中所有节点都包含：值 + 指向前一个节点的指针 + 指向后一个节点的指针。

#####复杂度分析

时间复杂度：
addAtHead，addAtTail： \mathcal{O}(1)O(1)
get，addAtIndex，delete：\mathcal{O}(\min(k, N - k))O(min(k,N−k))，其中 kk 指的是元素的索引。
空间复杂度：所有的操作都是 \mathcal{O}(1)O(1)。

说明:不论是单链表还是双链表，在进行遍历时，如果想要通过index来get某一结点元素，for循环中的终止条件是i<index+1

如果是删除或者添加，for循环中的终止条件是**i<index

相关文章推荐
谢谢你的支持哦，继续加油.