线性链表

发表于 |

线性表

线性表可以用数学方式来定义 (a1, ... ai-1, ai, ai+1, ... an)，其中 ai+1 是 ai 的前驱，ai-1 是 ai 的后缀。当 n=0 的时候，称为空表。

线性结构：顺序存储，比如数组。
链表结构：乱序存储，里面有一个指针指向下一项元素地址，分为数据域（如data1）和指针域（next 指针）如下图：

链表存储结构

线性表的优缺点：

优点：

  • 快速存取表中任意位置的元素。
  • 无需为表示表中元素之间的关系而增加额外的存储空间。

缺点：

  • 插入和删除操作需要移动大量的元素。
  • 当线性表变化比较大的时候，难以确定存储空间的容量。
  • 容易造成存储空间碎片。

链表

数据域存储数据，指针域指向下一个储存节点的地址：

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
typedef struct Node {
  ElemeType data;      // 数据域
  struct Node * next;  // 指针域
} Node, *LinkList;

// 初始化链表
void InitList(LinkList *L)
{
  // 初始化头结点，也就是上图中的 head
  *L = (LinkList)malloc(sizeof(struct Node));
  // 构造空的线性表
  if(!*L)
    exit(OVERFLOW);
  (*L)->next = NULL; // 置空指针域
}

// 销毁链表
void DestroyList(LinkList *L)
{
  LinkList q;
  while(*L)
  {
    q = (*L)->next;
    free(*L);
    *L = q;
  }
}

// 初始条件：线性表L已存在。操作结果：将L重置为空表
void ClearList(LinkList L)
{
  LinkList p,q;
  p = L->next; // p指向第一个结点，然后循环删除
  while(p)
  {
    q = p->next;
    free(p);
    p = q;
  }
  L->next = NULL; // 头结点指针域为空
}

// 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
Status IsListEmpty(LinkList L)
{
  return L->next == NULL;
}

// 初始条件：线性表L已存在。操作结果：返回L中数据元素个数
int ListLength(LinkList L)
{
  int i=0;
  LinkList p = L->next; // p指向第一个结点
  while(p)
  {
    i++;
    p = p->next;
  }
  return i;
}

// 顺序线性表 L 已存在，1 <= i <= ListLength(L)
// 操作结果，用 e 返回 L 中第 i 个元素的值
Status GetElem(LinkList L, int i, ElemType *e)
{
  int j = 1;
  LinkList p = L->next;
  while(p&&j < i) // 顺指针向后查找，直到p指向第i个元素或p为空
  {
    p = p->next;
    j++;
  }
  if(!p || j>i) // 第i个元素不存在
    return ERROR;
  *e = p->data; // 取第i个元素
  return OK;
}

// 初始条件: 线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)
// 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。
//          若这样的数据元素不存在，则返回值为0
int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType,ElemType))
{
  int i = 0;
  LinkList p = L->next;
  while(p)
  {
    i++;
    if(compare(p->data,e)) // 找到这样的数据元素
      return i;
    p=p->next;
  }
  return 0;
}

// 初始条件: 线性表L已存在
// 操作结果: 若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
//           返回OK；否则操作失败，pre_e无定义，返回INFEASIBLE
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{
  LinkList q, p = L->next;
  while(p->next) // p所指结点有后继
  {
    q = p->next; // q为p的后继
    if(q->data == cur_e)
    {
      *pre_e = p->data;
      return OK;
    }
    p=q; // p向后移
  }
  return INFEASIBLE;
}

// 初始条件：线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
//         返回OK;否则操作失败，next_e无定义，返回INFEASIBLE
Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e)
{
  LinkList p = L->next;
  while(p -> next) // p 所指结点有后继
  {
    if(p->data == cur_e)
    {
      *next_e = p->next->data;
      return OK;
    }
    p = p->next;
  }
  return INFEASIBLE;
}

// 在带头结点的单链线性表 L 中第 i 个位置之前插入元素 e
Status ListInsert(LinkList L, int i, ElemType e)
{
  int j = 0;
  LinkList p = L, s;
  while(p&&j < i-1) // 寻找第 i-1 个结点
  {
    p = p->next;
    j++;
  }
  if(!p || j > i-1) // i 小于1或者大于表长
    return ERROR;

  s = (LinkList)malloc(sizeof(struct Node)); // 生成新结点
  s->data = e; // 插入 L 中
  s->next = p->next;
  p->next = s;
  return OK;
}

// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
Status ListDelete(LinkList L, int i, ElemType *e)
{
  int j = 0;
  LinkList p = L, q;
  while(p->next && j < i-1) // 寻找第i个结点，并令p指向其前驱
  {
    p = p->next;
    j++;
  }
  if(!p->next || j > i-1) // 删除位置错误
    return ERROR;
  q = p->next; // 删除并释放结点
  p->next = q->next;
  *e = q->data;
  free(q);
  return OK;
}

// 初始条件：线性表 L 已存在。操作结果：依次对 L 的每个数据元素调用函数 vi()
void ListTraverse(LinkList L, void(*vi)(ElemType))
{
  LinkList p = L->next;
  while(p)
  {
    vi(p->data);
    p = p->next;
  }
  printf("\n");
}

时间复杂度

在操作单链表的过程中，由于算法的时间复杂度取决于 i 的值，因此最坏情况下的时间复杂度为 O(n)，最好的情况下为 O(1)。对于插入或者删除数据越频繁的操作，单链表的效率优势就越明显，因为其操作的是指针。

单链表结构与顺序存储结构时间性能对比：

单链表 顺序结构
查找 O(n) O(1)
删除 O(1) O(n)
插入 O(1) O(n)

空间性能

  • 顺序结构需要分配连续的存储空间，空间分大了造成浪费，分小了会造成溢出。
  • 单链表不需要分配存储空间，元素个数也不受限制。

选取单链表还是顺序结构？

  • 若线性表需要频繁查找，很少进行插入和删除操作，采用顺序存储结构。
  • 若需要频繁的插入和删除时，采用单链表结构。

单链表应用

快速找到未知长度单链表的中间节点。

可以通过遍历单链表的方式来获取其中间节点。其时间复杂度为 O(3L/2)思路如下：

  • 先遍历一遍链表，获取其长度 L。
  • 再次循环到 L/2 处，获取其中间节点。

还有一种更巧妙的方式来解决这个问题，其时间复杂度为O()，利用快慢指针的原理，思路如下：

  • 设置两个指针 *search、*mid，都指向单链表的头结点。
  • 其 *search 的移动速度是 *mid 的两倍。这样当 *search 移动到末尾结点的时候，*mid 指针刚好就在中间了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status GetMidNode(LinkList L, ElemType *e)
{
  LinkList mid, search;
  mid = search = L;
  while (search -> next != NULL)
  {
    if (search -> next -> next != NULL)
    {
      search = search -> next -> next;
      mid = mid -> next;
    }
    else
    {
      search = search -> next;
    }
  }

  *e = mid -> data;

  return OK;
}