data structure

由于顺序表的插入、删除操作需要移动大量的元素,影响了运行效率,由此引入了线性表的链式存储。链式存储线性表时,不需要使用地址连续的存储单元,即它不要求逻辑上相邻的两个元素在物理位置上也相邻,它通过 “链” 建立起数据元素之间的逻辑关系,因此对线性表的插入、删除不需要移动元素,而只需要修改指针。

1. 单链表的定义

线性表的链式存储又称为单链表,它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系,对每个链表接待你,除存放元素自身的信息外,还需要存放一个指向其后继的指针。

link list

其中 data 为数据域,存放数据元素,next 为指针域,存放其后继结点的地址。单链表中结点类型描述如下:

struct Node {           // 单链表结点类型
	int data;           // 数据域,为了简单描述直接定义为 int
	Node* next;         // 指针域
	Node(int x = 0) : data(x), next(NULL){}
};

利用单链表可以解决顺序表需要大量连续存储空间的缺点,但单链表附加指针域,存在浪费存储空间的缺点。由于单链表的元素是离散地分布在存储空间中的,所以单链表是非随机存取的存储结构,既不能直接找到表中某个特定的结点。查找某个特定的结点时,需要从头开始遍历,依次查找。

通常用头指针来标识一个单链表,头指针为 NULL 时表示一个空表。此外,为了操作上的方便,在单链表第一个结点之前附加一个结点,称为头结点。头节点的数据域可以不设任何信息,也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素结点。

头结点和头指针的区分:不管带不带头结点,头指针始终指向链表的第一个结点,而头结点是带头结点的链表中的第一个结点,结点内通常不存储信息。

引入头结点后,可以带来两个优点:

  1. 由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作和在表的其他位置上的操作一致,无须进行特殊处理。
  2. 无论链表是否为空,其头指针都指向头结点的非空指针(空表中头结点的指针域为空),因此空表和和非空表的处理也就得到了统一。

2. 单链表上的基本操作的实现

  1. 采用头插法建立单链表-

    该方法从一个空表开始,生成新结点,并将读取到的数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头,即头结点之后。

    头插法

    头插法建立单链表的算法如下(每次调用只插入一个结点)

    void headInsert(Node* head, int data) {
    	// 从表尾到表头逆向建立单链表 L,每次均在头结点之后插入元素
    	Node* newNode = new Node(data);
    	newNode->next = head->next;
    	head->next = newNode; 	 
    }
    

    采用头插法建立单链表时,读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结点插入的时间为 O(1) ,设单链表长为 n,则总时间复杂度为 O(n) 。

  2. 采用尾插法建立单链表

    头插法建立单链表的算法虽然简单,但生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致,则可采用尾插法。该方法将新结点插入到当前链表的表尾,为此必须增加一个尾结点 tail ,使其始终指向当前链表的尾结点。

    尾插法

    尾插法建立单链表的算法如下(一开始尾指针指向 head,该算法每次只能插入一个数据):

    void tailInsert(Node* &tail, int data) {
    	Node* newNode = new Node(data);
    	tail->next = newNode;    // 尾指针的下一个结点就是新结点
    	tail = newNode;          // 更新尾指针,注意入参使用引用
    }
    

    因为附设了一个指向表尾结点的指针,故时间复杂度和头插法的相同。

  3. 按序号查找结点值

    在单链表中从第一个结点出发,顺指针 next 域 逐个往下搜索,直到找到第 i 个结点为止,否则返回最后一个结点指针域 NULL。

    按序号查找结点值的算法如下:

    Node* getElem(Node* head, int i) {
    	// 本算法取出单链表 L (带头结点)中第 i 个为止的结点指针
    	if(i == 0) return head;
    	if(i < 1) return NULL;
    	int j = 1;
    	for(Node* it = head->next; it; it = it->next){
    		if (j == i)	return it;
    		j++;
    	}
    	return NULL;
    }
    

    按序号查找操作的时间复杂度为 O(n) 。

  4. 按值查找表结点

    从单链表的第一个结点开始,由前往后依次比较表中各结点数据域的值,若某结点数据域的值等于给定值 e,则返回该结点的指针;若整个单链表中没有这样的结点,则返回 NULL 。

    按值查找表结点的算法如下:

    Node* locateElem(Node* head, int e) {
    	// 本算法查找单链表 L (带头结点) 中数据域值等于 e 的结点,否则返回 NULL
    	for(Node* it = head->next; it; it = it->next) {
    		if(it->data == e) return it;
    	}	 
    	return NULL;
    }
    

    按值查找操作的时间复杂度为 O(n) 。

  5. 插入结点操作

    插入结点操作将值为 x 的新结点插入到单链表的第 i 个位置上。先检查插入位置的合法性,然后找到待插入位置的前驱结点,即第 i-1 个结点,再在其后插入新结点。

    算法首先调用按序号查找算法 getElem(L, i-1) ,查找第 i-1 个结点。假设返回的第 i-1 个结点为 *p ,然后令新结点 *s 的指针域指向 *p 的后继结点,再令结点 *p 的指针域指向新插入的结点 *s 。如下图所示。

    insert node

    实现插入结点的代码片段如下:

    1. p=getElem(head,i-1);  // 查找插入位置的前驱结点
    2. s->next = p->next;    // 图的步骤 1
    3. p->next = s;          // 图的步骤 2
    

    算法中,语句 2 和 3 的顺序不能颠倒,否则,当先执行 p->next=s 后,指向原后继的指针就不存在,再执行 s->next=p->next 时,相当于执行了 s->next = s,显然是错误的。本算法主要的时间开销在于查找第 i-1 个元素,时间复杂度为 O(n) 。若在给定的结点后面插入新结点,则时间复杂度仅为 O(1) 。

    拓展 :对某一结点进行前插操作。

    前插操作是指在某结点的前面插入一个新结点,后插操作的定义刚好与之相反。在单链表插入算法中,通常都采用后插操作。

    以上面的算法为例,首先调用函数 getElem() 找到第 i-1 个结点,即插入结点的前驱结点后,再对其执行操作。由此可知,对结点的前插操作均可转化为后插操作,前提是从单链表的头结点开始顺序查找到其前驱结点,时间复杂度为 O(n) 。

    此外,可采用另一种方式将其转化为后插操作来实现,设待插入结点为 *s ,将 *s 插入到 *p 的前面。外面仍然将 *s 插入到 *P 的后面,然后将 p->datas->data 交换,这样既满足了逻辑关系,又能使得时间复杂度为 O(1) 。算法的代码片段如下

    // 将 *s 结点插入到 *p 之前的主要代码片段
    s->next = p->next;   // 修改指针域,不能颠倒
    p->next = s;
    etmp = p->data;      // 交换数据域部分
    p->data = s->data;
    s->data = temp;
    
  6. 删除结点操作

    删除解答四年操作是将单链表的第 i 个结点删除。先检查删除位置的合法性,然后查找表中第 i-1 个结点,即被删结点的前驱结点,再将其删除。其操作过程如下

    delete node

    假设结点 *p 为找到的被删结点的前驱结点,为实现这一操作后的逻辑关系的变化,仅需修改 *p 的指针域,即将 *p 的指针域 next 指向 *q 的下一个结点。

    实现删除结点的代码片段如下:

    p = getElem(head,i-1);   // 查找删除位置的前驱结点
    q = p->next;             // 令 q 指向被删除结点
    p->next = q->next;       // 将 *q 结点从链中 “断开”
    delete q;                // 释放结点的存储空间
    

    和插入算法一样,该算法的主要时间也耗费在查找操作上,时间复杂度为 O(n) 。

    拓展:删除结点 *P

    要删除某个给定结点 *p ,通常的做法是先从链表的头结点开始顺序找到其前驱结点,然后再执行删除操作,算法的时间复杂度为 O(n) 。

    其实,删除结点 *p 的操作可用删除 *P 的后继结点操作来实现,实质就是将其后继结点的值赋予其自身,然后删除后继结点,也能使得时间复杂度为 O(1) 。当然如果没有后继结点直接删除即可。

    实现上述操作的代码片段如下:

    q = p->next;               // 令 q 指向 *p 的后继结点
    p->data = p->next->data;   // 和后继结点交换数据域
    p->next = q->next;         // 将 *q 结点从链中 “断开”
    delete(q);                 // 释放后继结点的存储空间
    
  7. 求表长操作

    从头结点开始遍历即可。

单链表是整个链表的基础,一定要熟练掌握单链表的基本操作算法。在设计算法时,建议先通过图示的方法理清算法的思路,然后再进行算法的编写。

3. 双链表

单链表结点中只有一个指向其后继的指针,使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时),只能从头开始遍历,访问后继结点的时间复杂度为 O(1) ,访问前驱结点的时间复杂度为 O(n) 。

为了克服单链表的上述缺点,引入了双链表,双链表结点中有两个指针 prior 和 next ,分别指向其前驱结点和后继结点,如下

double link list

双链表中结点类型的描述如下

struct DNode {
	int data;     // 数据 
	DNode* prior;  // 后继指针 
	DNode* next;   // 前驱指针 
	DNode(int x = 0) : data(x), prior(NULL), next(NULL){}
};

双链表仅在单链表的结点中增加了一个指向前驱的 prior 指针,因此在双链表中执行按值查找和按位查找的操作与在单链表中的相同。但双链表在插入和删除操作的实现上,与单链表有着较大的不同。这是因为 “链” 变化时也需要对 prior 指针做出修改,其关键是保证在修改的过程中不断链。此外,双链表可以很方便地找到其前驱结点,因此,插入、删除结点算法的时间复杂度仅为 O(1) 。

  1. 双链表的插入操作

    在双链表中 p 所指的结点之后插入结点 *s ,其指针的变化过程如下

    insert node

    插入操作的代码片段如下:

    1. s->next = p->next;  // 将结点 *s 插入到结点 *p 之后
    2. p->next->prior = s;
    3. s->prior = p;
    4. p->next = s;
    

    上述代码的语句顺序不是唯一的,但也不是任意的,1 和 2 两步必须在 4 之前,否则 *p 的后句结点的指针就会丢掉,导致插入失败。可以自己思考如何将 s 插入到 p 之前。

  2. 双链表的删除操作

    删除双链表中结点 *p 的后继结点 *q ,其指针的变化过程如下

    delete Node

    删除操作的代码片段如下

    1. p->next = q->next;
    2. q->next->prior = p;
    3. delete q;
    

    读者自行考虑删除结点 *q 前驱结点 *p

    在建立双链表的操作中,也可采用如同单链表的头插法和尾插法,但在操作上需要注意指针的变化和单链表有所不同。

4. 循环链表

  1. 循环单链表

    循环单链表和单链表的区别在于,表中最后一个结点的指针不是 NULL,而改为指向头结点,从而整个链表形成一个环,如下

    circular singly linked list

    在循环单链表中,表尾结点 *r 的 next 域指向 L,故表中没有指针域为 NULL 的结点,因此,循环单链表的判空条件不是头结点的指针是否为空,而是它是否等于头指针。

    循环单链表的插入、删除算法与单链表的几乎一样,所不同的是若操作是在表尾进行,则执行的操作不同,以让单链表继续保持循环的性质。当然,正是因为循环单链表是一个 “环”,因此在任何一个位置上的插入和删除操作都是等价的,无须判断是否在表尾。

    在单链表中只能从表头结点开始往后顺序遍历整个链表,而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的,此时对循环单链表不设头指针而仅设尾指针,从而使得操作效率更高。其原因是,若设的是头指针,对表尾进行操作需要 O(n) 的时间复杂度,而若设的是尾指针 r,r->next 即为头指针,对于表头与表尾进行操作都只需要 O(1) 的时间复杂度。

  2. 循环双链表

    由循环单链表的定义不难推出循环双链表,不同的是在循环双链表中,头结点的 prior 指针还要指向表尾结点。如下图所示

    circular double linked list

    在循环双链表中,某结点 *p 为尾结点时,p->next = head ;当循环双链表为空表时,其头结点的 prior 和 next 都指向自己。

5. 静态链表

静态链表借助数组来描述线性表的链式存储结构,结点也有数据域 data 和指针域 next,与前面所讲的链表中的指针不同的是,这里的指针是结点的相对地址(数组下标),又称游标。和顺序表一样,静态链表也要预先分配一块连续的内存空间。

static list

静态链表结构类型的描述如下

#define MaxSize 50    // 静态链表的最大长度
typedef struct {      // 静态链表结构类型的定义
	ElemType data;    // 存储数据元素
	int next;         // 下一个元素的数组下标
} SLinkList[MaxSize];

静态链表以 next == -1 作为其结束的标志。静态链表的插入、删除操作与动态链表的相同,只需要修改指针,而不需要移动元素。总体来说,静态链表没有单链表使用起来方便,但在一些不支持指针的高级语言(如 Basic)中,这是一种非常巧妙的设计方法。

6. 顺序表和链表的比较

  1. 存取方式

    顺序表可以顺序存取,也可以随机存取,链表只能从表头顺序存取元素。

  2. 逻辑结构与物理结构

    采用顺序存储时,逻辑上相邻的元素,其对应的物理存储位置也相邻。而采用链式存储时,逻辑上相邻的元素,其物理存储位置则不一定相邻,其对应的逻辑关系是通过指针链接来表示的。注意区分存取方式和存储方式。

  3. 查找、插入和删除操作

    对于按值查找,顺序表无序时,两者的时间复杂度均为 O(n);顺序表有序时,可采用折半查找,此时的时间复杂度为 $O(\log_2n)$ 。

    对于按序号查找,顺序表支持随机访问,时间复杂度仅为 O(1) ,而链表的平均时间复杂度为 O(n) 。顺序表的插入、删除操作,平均需要移动半个表长的元素。链表的插入、删除操作,只需修改相关结点的指针域即可。由于链表的每个结点都带有指针域,因而在存储空间上要比顺序存储付出的代价大,而存储密度不够大。

  4. 空间分配

    顺序存储在静态存储分配情形下,一旦存储空间装满就不能扩充,若再加入新元素,则会出现内存溢出,因此需要预先分配足够大的存储空间。预先分配过大,可能会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。动态存储分配虽然存储空间可以扩充,但需要移动大量元素,导致操作效率降低,而且若内存中没有更大块的连续存储空间,则会导致分配失败。链式存储的结点空间只在需要时申请分配,只要内存有空间就可以分配,操作灵活、高效。

在实际中应该怎样选取存储结构呢?

  1. 基于存储的考虑

    难以估计线性表的长度或存储规模时,不宜采用顺序表;链表不用实现估计存储规模,但链表的存储密度较低,显然链式存储结构的存储密度是小于 1 的。

  2. 基于运算的考虑

    在顺序表中按序号访问元素的时间复杂度为 O(1) ,而链表中按序号访问的时间复杂度为 O(n) ,因此若经常做的运算是按序号访问数据元素,则显然顺序表优于链表。

    在顺序表中进行插入、删除操作时,平均移动表中一半的元素,当数据元素的信息量较大且表较长时,这一点是不应忽视的;在链表中进行插入、删除操作时,虽然也要找插入位置,但操作主要是比较操作,从这个角度考虑显然链表优于顺序表。

  3. 基于环境的考虑

    顺序表容易实现,任何高级语言中都有数组类型;链表的操作是基于指针的,相对来讲,前者实现较为简单,这也是用户考虑的一个因素。

    总之,两种存储结构各有长短,选择哪一种由实际问题的主要因素来决定。通常较稳定的线性表选择顺序存储,而频繁进行插入、删除操作的线性表(即动态性较强)宜选择链式存储。

注意:只有熟练掌握顺序存储和链式存储,才能深刻理解它们各自的优缺点。

7. 习题

  1. 线性表中有 2n 个元素,下面操作中,哪个操作链表快
    1. 删除所有值为 x 的元素
    2. 在最后一个元素的后面插入一个新元素
    3. 顺序输出前 k 个元素
    4. 交换第 i 个元素和第 2n-i-1 个元素的值 i=0,1,…,n-1
  2. 带头结点和尾结点的单链表中,以下哪些操作与链表的表长有关?
    1. 删除单链表的第一个元素
    2. 删除单链表中的最后一个元素
    3. 在单链表第一个元素前插入一个新元素
    4. 在单链表最后一个元素后插入一个新元素
  3. 给定有 n 个元素的一维数组(假设无序),建立一个有序单链表的最低时间复杂度是多少
  4. 与单链表相比,双链表的优点有什么?

8. 习题答案

  1. 选 1 ,链表删除不需移动元素
  2. 选 2,需要遍历找到倒数第二个元素并置其 next 为 NULL 。
  3. 看排序的最低复杂度。
  4. 访问前后相邻结点更灵活。