Xu-Blog

养一猫一狗，猫叫啵啵，狗叫没想好~~

0%

链表-01

发表于 分类于 阅读次数： Valine：
本文字数： 7.1k 阅读时长 ≈ 6 分钟

链表与数组相似，链表也是一种线性数据结构。这里有一个图例：

如图中所示，链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。

链表有两种类型：单链表和双链表。上面给出的图例是一个单链表，以下是双链表的图例：

对于链表，需要掌握的内容如下：

  • 了解单链表和双链表的结构；
  • 在单链表或双链表中实现遍历、插入和删除；
  • 分析在单链表或双链表中的各种操作的复杂度；
  • 在链表中使用双指针技巧（快指针慢指针技巧）；
  • 解决一些经典问题，例如反转链表；
  • 分析你设计的算法的复杂度；
  • 积累设计和调试的经验。

单链表

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

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

以下是单链表中结点的典型定义：

1
2
3
4
5
6
// 单链表定义
struct SinglyListNode {
  int val;
  SinglyListNode *next;   // 定义一个指针指向结构体
  SinglyListNode(int x) : val(x), next(NULL){}  // 初始化 val 为 x，next指向 NULL；
}

大多数情况下，我们将使用头结点（第一个结点）来表示整个链表。

操作

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

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

那为什么，链表在索引访问数据时具有如此糟糕的性能（与数组相比），但是链表还必须要掌握那么多。之后来介绍链表的插入和删除操作，来了解链表的好。

添加操作-单链表

如果我们想在给定的结点 prev 之后添加新值，我们应该：

1.使用给定值初始化新结点 cur；

2.将 cur 的“next”字段链接到 prev 的下一个结点 next；

3.将 prev 中的“next”字段链接到 cur

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

在开头添加结点

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

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

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

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

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

在结尾添加结点

如何在列表的末尾添加新的结点呢？我们还能使用类似的策略么？

我们新初始化一个结点，将 15 的指针指向新结点即可。

删除操作-单链表

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

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

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

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

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

删除第一个结点

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

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

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

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

删除末尾结点

删除最后一个结点呢？我们还能使用类似的策略吗？

我们找到末尾结点的上一个结点，将他的 next 指向空（即将其置为末尾）

题目：设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

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

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

提示：

  • 所有 val 值都在 [1, 1000] 之内。
  • 操作次数将在 [1, 1000] 之内。
  • 请不要使用内置的 LinkedList 库。

个人理解：
这个没啥好说的，细心点，一点点写，一步步看，就成了。

单链表实现

代码如下(C++):

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
class MyLinkedList {
private:
  struct Node
  {
    int val;
    Node *next;  // 定义一个next指针指向这个结构体
    /* 初始化节点方式，将x赋值给val，node指针赋值给next指针 */
    Node(int x): val(x), next(nullptr){}
  };
  Node *head; // 定义头指针
  int size;   // 定义链表大小
public:
  /** 初始化数据结构 */
  MyLinkedList() {        // 初始化链表
    head = nullptr;        // 头部为空
    size = 0;           // 大小为0
  }

  /** 获取链表中第index个节点的值。 如果索引无效，则返回-1。 */
  int get(int index) {
    if(index < 0 || index >= size)  // 索引无效
      return -1;
    Node *p = head;     // 定义指针 p 指向链表头部
    int i = 0;          // 从i到 index 就是 p 向后移动的步数
    while(p && i < index){
      p = p -> next;  // 这个 next 表示，将 p 指向下一个节点，不是指针 next
      i++;            // 向后移动一步
    }
    if(p) return p -> val;    // 返回 p 指向结构体中的值
    else return -1;
  }

  /** 在链接列表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。 */
  void addAtHead(int val) {
    Node *p = new Node(val);  // 定义指针 p，新建了节点，值为 val, 指针为 head
    p -> next = head;
    head = p;       // 把 head 置为 p 指向的内存
    ++size;         // 链表大小加一
  }

  /** 将val的节点追加到链接列表的最后一个元素。 */
  void addAtTail(int val) {
    Node *p = new Node(val);    // 定义一个 p 获取 head 位置
    if(head == nullptr){        // 如果链表为空，直接将新节点作为头节点
      head = p;
      return;
    }
    Node *q = head;             // q 复制 head 位置
    while(q -> next)            // 从头开始把 q 一直向后遍历完毕
      q = q -> next;
    q -> next = p;              // 在最后添加一个新的节点，值为val
    ++size;
  }

  /** 在链接列表的第index个节点之前添加一个值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于长度，则不会插入该节点。 */
  void addAtIndex(int index, int val) {
    if(index > size)  return;       // 大于长度，不插入节点

    if(index <= 0){                 // 小于等于0，直接在头部插入即可
      addAtHead(val);
      return;
    }
    Node *p = head;
    int i = 0;
    while(p && i < index - 1){      // 从头开始移动
      p = p -> next;
      i++;
    }
    Node *q = new Node(val);        // p 是索引节点的前节点，所以 p -> next 插入 q
    if(p){
      q -> next = p -> next;      // 将 p -> next 指向 q -> next
      p -> next = q;              // 将节点 q 指向 p -> next
    }
    ++size;
  }

  /** 如果索引有效，请删除链接列表中的第index个节点。 */
  void deleteAtIndex(int index) {
    if(index < 0 || index >= size)  return;     // 索引无效
    if(index == 0 && head != nullptr){          // index 为 0，直接删除 head 节点
      Node *del = head;
      head = head -> next;
      delete del;
      --size;
      return;
    }
    Node *p = head;
    int i = 0;
    /* 要删除index，我们需要找到他的前驱节点，然后指向他的后驱即可。 */
    while(p && i < index - 1){
      p = p -> next;
      i++;
    }
    if(!p) return;          // index 超过链表范围，删除失败
    if(p -> next){
      Node *del = p->next;    // 删除节点指向 p -> next
      p -> next = del -> next;    // 将 p -> next 指向 del -> next
      delete del;
      --size;
    }
  }
};

双链表实现

代码如下(C++):

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
class MyLinkedList {
private:
  struct Node
  {
    int val;
    Node *next, *prev;  // 定义一个next和prev
    /* 初始化节点方式，将x赋值给val，node指针赋值给next指针 */
    Node(int x): val(x), next(nullptr), prev(nullptr){}
  };
  Node *head, *tail;  // 定义头指针
  int size;           // 定义链表大小
public:
  /** 初始化数据结构 */
  MyLinkedList() {        // 初始化链表
    head = nullptr;       // 头部为空
    tail = nullptr;       // 尾部为空
    size = 0;             // 大小为0
  }

  /** 获取链表中第index个节点的值。 如果索引无效，则返回-1。 */
  int get(int index) {
    if(index < 0 || index >= size)  // 索引无效
      return -1;
    Node *p = head;     // 定义指针 p 指向链表头部
    int i = 0;          // 从i到 index 就是 p 向后移动的步数
    while(p && i < index){
      p = p -> next;    // 这个 next 表示，将 p 指向下一个节点，不是指针 next
      i++;              // 向后移动一步
    }
    if(p) return p -> val;          // 返回 p 指向结构体中的值
    else return -1;
  }

  /** 在链接列表的第一个元素之前添加一个值为val的节点。插入后，新节点将成为链表的第一个节点。 */
  void addAtHead(int val) {
    if(head != nullptr){
      Node *node = new Node(val);
      node -> next = head;
      head -> prev = node;
      head = node;
    }else{          // 头为空，那尾肯定也是空
      head = new Node(val);
      tail = head;
    }
    ++size;         // 链表大小加一
  }

  /** 将val的节点追加到链接列表的最后一个元素。 */
  void addAtTail(int val) {
    if(tail != nullptr){
      Node *node = new Node(val);
      node -> prev = tail;
      tail -> next = node;
      tail = node;
    }else{           // 尾为空，那头肯定也是空
      tail = new Node(val);
      head = tail;
    }
    ++size;
  }

  /** 在链接列表的第index个节点之前添加一个值为val的节点。如果index等于链表的长度，则该节点将附加到链表的末尾。如果index大于长度，则不会插入该节点。 */
  void addAtIndex(int index, int val) {
    if(index <= 0){                 // 小于等于0，直接在头部插入即可
      addAtHead(val);
      return;
    }
    if(index == size){              // index 等于 size，直接在尾部插入即可
      addAtTail(val);
      return;
    }
    if(index > size)  return;       // 大于长度，不插入节点

    Node *p = nullptr, *cur = head;
    int i = 0;
    while(cur && i < index){        // 从头开始移动
      p = cur;
      cur = cur -> next;
      i++;
    }
    Node *node = new Node(val);     // 创建要插入的节点
    /* 特殊情况已经排除了，现在 p 和 cur 都在链表内。 */
    p -> next = node;
    node -> prev = p;
    node -> next = cur;
    cur -> prev = node;
    ++size;
  }

  /** 如果索引有效，请删除链接列表中的第index个节点。 */
  void deleteAtIndex(int index) {
    if(index < 0 || index >= size)  return;     // 索引无效
    if(!head) return;
    if(index == 0){           // index为头节点，删除头节点
      Node *del = head;
      head = head -> next;
      if(head){
        head -> prev = nullptr;
      }else{
        tail = nullptr;
      }
      delete del;
      --size;
      return;
    }
    if(index == size - 1){    // index为尾节点，删除尾节点
      Node *del = tail;
      tail = tail -> prev;
      if(tail){
        tail -> next = nullptr;
      }
      delete del;
      --size;
      return;
    }
    Node *p = nullptr, *cur = head;
    int i = 0;
    /* 要删除index， */
    while(cur){
      if(i == index){
        Node *del = cur;
        p -> next = cur -> next;
        if(cur -> next){
          cur -> next ->prev = p;
        }
        delete del;
        --size;
        return;
      }
      p = cur;
      cur = cur -> next;
      ++i;
    }
  }
  int length(){
    return size;
  }
};

声明：本文为学习记录，参考之处较多，如果有侵权内容，请联系我立即删除。

End~~请支持原创撒花=￣ω￣=花撒
如果您读文章后有收获，可以打赏我喝咖啡哦～