数据结构：线性表

一个好的算法是建立在一个好的数据结构基础之上的。可以说，数据结构是算法设计的基础。根据数据元素之间逻辑关系和操作运算的不同，可以划分出多种数据结构，常用的数据结构如下图所示：

在这些数据结构中，线性表是最基本和最常用的一种数据结构，同时也是其它数据结构的基础，尤其是链表，它会贯穿整个数据结构课程的始终。本篇文章将重点讨论线性表这个最基础的数据结构。

一、线性表

1.1、定义和特点

线性表，是由n个具有相同特性的数据元素构成的有限序列。其中，数据元素的个数n是线性表的长度，当n为零时称为空表。

对于一个非空的线性表（或线性结构）来说，其特点如下：

仅有一个被称作“第一个”的数据元素；
仅有一个被称作”最后一个“的数据元素；
除第一个元素之外，表中的每个数据元素均只有一个直接前驱；
除最后一个元素之外，表中的每个数据元素均只有一个直接后继。

在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表就是一个线性表，表中的数据元素是单个字母。在稍复杂的线性表中，一个数据元素可以包含若干个数据项。例如，在一张学生基本信息表中，每个学生的基本信息为一个数据元素，包括学号、姓名、性别、籍贯、专业等数据项。

1.2、存储结构

存储结构，也称物理结构，指的是数据对象在计算机中的存储表示。把数据对象存储到计算机时，不仅要存储各数据元素的数据，还要存储数据元素之间的逻辑关系。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。

1.2.1、顺序存储

顺序存储，是指用一组地址连续的存储单元存放数据元素。其特点是，逻辑上相邻的数据元素，其物理位置也是相邻的。采用这种存储方法的线性表被称为顺序表（Sequential List）。

顺序存储借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。在顺序表中，每个数据元素的存储地址是该数据元素在表中位置的线性函数。假设，在一个线性表中，第一个数据元素的存储地址是LOC( $a_1$ )，每个数据元素的大小是s，那么第i个数据元素的存储地址LOC( $a_i$ )就为：

LOC(a_i) = LOC(a_1) + (i-1)*s

这也就是说，只要知道了第一个数据元素的存储地址（也称基地址）和每个数据元素的大小，就能求出任一数据元素的存储地址，所以顺序表是一种支持随机存取的数据结构。

1.2.2、链式存储

链式存储，是指用一组地址任意的存储单元存放数据元素。其特点是，逻辑上相邻的两个元素，其物理位置可以是连续的，也可以是不连续的。采用这种存储方法的线性表被称为链表。

在链式存储结构中，为了表示数据元素之间的逻辑关系，在存储数据时，不仅要存储数据元素本身，还要存储其直接前驱（或后继）的位置等信息。所以，链表中的每个数据元素（通常称为结点）由数据域和指针域这两部分信息共同构成。其中，数据域用于存储数据元素本身的信息；指针域用于存储直接前驱（或后继）的位置等信息。

链表中各个元素的存储位置都是随意的。也就是说，链表是非随机存取的存储结构，要取得第i个数据元素必须顺链进行寻找，因此，链表也被称为顺序存取的存储结构。

二、顺序表

在高级程序设计语言中，数组具有随机访问的特性。因此，通常用数组来描述顺序表。在C语言中，可用动态分配的一维数组表示顺序表，相应的描述如下：

// 顺序表的最大长度（应该根据实际需要来定，这里假设为100）
#define MAXSIZE 100

// 表中数据元素的类型（应根据实际情况而定，这里假设为int）
typedef int ElemType;

// 定义顺序表类型
typedef struct {
  // 存储空间的基地址
  ElemType* elem;
  // 表的当前长度（即实际存储的数据元素个数）
  int length;
}SeqList;

有了该定义，顺序表的一些操作就可轻松实现。因为表的长度是顺序表的一个”属性“，所以可通过返回length的值实现求表长的操作，也可通过length的值是否为0判断表是否为空，实现这些操作的算法的时间复杂度都是O(1)。下面重点讨论顺序表其他几个主要操作的实现。

3.1、初始化

初始化，就是构造一个空的顺序表。该算法步骤为：

为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址。
将表的当前长度设为0。

相应的算法描述为：

// 构造一个空的顺序表
Status InitList(SeqList &L) {
    // 为顺序表分配一个大小为MAXSIZE的数组空间
    L.elem=(ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
    // 空间分配失败，退出
    if(!L.elem) exit(OVERFLOW);
    // 空表的长度为0
    L.length=0;
    
    return OK;
}

3.2、取值

取值，是指根据指定的位置序号i，获取顺序表中第i个数据元素的值。由于顺序存储结构具有随机存取的特点，因此可以直接通过数组下标定位第i个数据元素，即第i个数据元素可通过elem[i-1]获取。该算法步骤为：

判断位置序号i值是否合理（i值的合法范围是1<=i<=L.length），若不合理，则返回ERROR。
若i值合理，则将第i个数据元素L.elem[i-1]赋给参数e，通过e返回第i个数据元素的值。

相应的算法描述为：

// 获取顺序表L的第i个数据元素的值
Status GetElem(SeqList L, ini i, ElemType &e) {
    // 判断i值是否合理，若不合理，返回ERROR
    if(i<1||i>L.length)return ERROR;
    // 获取第i个数据元素
    e=E.elem[i-1];
    
    return OK;
}

显然，顺序表取值算法的时间复杂度为O(1)。

3.3、查找

查找，是指根据指定的元素值e，查找顺序表中第1个值与e相等的元素。若查找成功，则返回该元素在表中的位置序号；若查找失败，则返回0。该算法步骤为：

从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1。
若查遍整个顺序表都没有找到，则查找失败，返回0。

相应的算法描述为：

// 在顺序表L中查找值为e的数据元素，返回其序号
int LocateElem(SeqList L, ElemType e) {
    for(i=0;i<L.length;i++) {
        // 查找成功，返回该元素的序号i+1
        if(L.elem[i]==e) return i+1;
    }
    
    // 查找失败，返回0
    return 0;
}

在顺序表中查找一个数据元素时，其时间主要耗费在数据的比较上，而比较的次数取决于被查元素在线性表中的位置。显然，该算法要分析其平均时间复杂度，在等概率情况下，其平均复杂度为O(n)。

3.4、插入

插入，是指在表的第i个位置上插入一个新的数据元素e，使线性表的长度由n变为n+1。

由于在顺序表中逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i=n+1，否则必须移动数据元素。一般情况下，在第i（1≤i≤n）个位置插入一个元素时，需从最后一个元素即第n个元素开始，将每个元素向后移动一个位置，直至第i个元素。该算法步骤为：

判断插入位置i是否合法（i值的合法范围是1≤i≤n+1），若不合法则返回ERROR。
判断顺序表的存储空间是否已满，若满则返回ERROR。
将最后一个元素至第i个位置的元素依次向后移动一个位置，空出第i个位置（i=n+1时无需移动）。
将要插入的新元素e放入第i个位置。
表长加1。

相应的算法描述为：

// 将新元素e插入到顺序表L的第i个位置
Status ListInsert(SeqList &L, int i, ElemType e) {
    // i值不合法
    if((i<1)||(i>L.length+1)) return ERROR;
    
    // 当前存储空间已满
    if(L.length==MAXSiZE) return ERROR;
    
    // 从最后一个元素开始，依次将每个元素向后移动一个位置，直到第i元素为止
    for(j=L.length-1; j>=i-1; j--) {
        L.elem[j+1]=L.elem[j];
    }
    
    // 将新元素e插入到第i个位置
    L.elem[i-1]=e;
    
    // 表长加1
    ++L.length;
    
    return OK;
}

在顺序表中某个位置上插入一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入元素的位置。显然，该算法要分析其平均时间复杂度，在等概率情况下，其平均复杂度为O(n)。

3.5、删除

删除，是指将表的第i个元素删去，使线性表的长度由n变为n-1。

与插入操作类似，除非i=n，否则必须移动数据元素。一般情况下，删除第i（1≤i≤n）个元素时，需将第i+1个至第n个元素依次向前移动一个位置（i=n时无需移动）。该算法步骤为：

判断删除位置i是否合法（合法值为1≤i≤n），若不合法则返回ERROR。
将第i+1个至最后一个元素依次向前移动一个位置（i=n时无需移动）。
表长减1。

相应的算法描述为：

// 在顺序表L中删除第i个元素
Status ListDelete(SeqList &L, int i) {
    // i值不合法
    if((i<1)||(i>L.length)) return ERROR;
    
    // 从第i+1个元素开始，依次将每个元素向前移动一个位置，直到最后一个元素为止
    for(j=i;j<=L.length-1;j++) {
        L.elem[j-1]=L.elem[j];
    }
    
    // 表长减1
    --L.length;
    
    return OK;
}

当在顺序表中某个位置上删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于删除元素的位置。显然，该算法也要分析其平均时间复杂度，在等概率情况下，其平均复杂度为O(n)。

3.6、小结

顺序表可以随机存取表中任一元素，其存储位置可用一个线性函数来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的缺点：在进行插入或删除操作时，需移动大量元素。另外，由于数组长度是固定的，当表中数据元素个数较多且变化较大时，不仅会使操作变复杂，还会导致存储空间的浪费。而所有这些问题，都可以通过链表来解决。

三、链表

根据结点指针域的不同，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中，单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。接下来，我们重点讨论前者。

3.1、单链表

单链表，是指链表中每个节点的指针域只包含一个指向其直接后继结点的指针。

在单链表中，由于第一个结点无直接前趋，所以通常会设立头指针指向链表中第一个结点。又由于最后一个结点无直接后继，所以最后一个结点的指针域为空，即NULL。如果单链表中一个数据元素也没有，则为空表，即L==NULL。

在C语言中，可用”结构体指针“来描述单链表，相应的描述如下：

// 表中元素的类型应根据实际情况而定，这里假设为int
typedef int ElemType;

// 定义单链表的节点类型
typedef struct node {
    // 结点的数据域
    ElemType data;
    // 结点的指针域
    struct node *next;
}LNoe,*LinkList;

说明：

在单链表中，每个结点的存结构由两部分组成：存储数据的数据域data，其类型用通用类型标识符ElemType表示；存储后继结点位置的指针域next，其类型为指向结点的指针类型LNode*。
LinkList和LNode *，两者在本质上是等价的。它们是不同名字的同一结构体指针类型，取名不同是为了在概念上更明确。通常，习惯上用LinkList定义单链表，强调定义的是某个单链表的头指针；用LNode *定义指向单链表中任意结点的指针变量。比如，若定义LinkList L，则L为单链表的头指针，若定义LNode *p，则p为指向单链表中某个结点的指针。
单链表是由头指针唯一确定的，因此单链表可以用头指针的名字来命名。若头指针名是L，则简称该链表为表L。

一般情况下，为了处理方便，会在单链表的第一个结点之前附设一个结点（称之为头结点），并使头指针指向该结点。增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。

在带头结点的单链表中，有3个容易混淆的概念，它们分别是：

首元结点，指链表中存储第一个数据元素的结点。
头指针，指向链表中的第一个结点。若链表设有头结点，则头指针所指结点为线性表的头结点；若链表不设头结点，则头指针所指结点为线性表的首元结点。
头结点，是在首元结点之前附设的一个结点，其指针域指向首元结点。头结点的数据域可以不存储任何信息，也可存储与数据元素类型相同的其他附加信息。例如，当数据元素为整数型时，头结点的数据域中可存放该线性表的长度。

3.1.1、初始化

初始化，就是构造一个空的单链表。该算法步骤为：

生成新结点作为头结点，用头指针L指向头结点。
头结点的指针域置空。

相应的算法描述为：

// 构造一个空的单链表
Status InitList(LinkList &L) {
    // 生成新结点作为头结点，并用头指针L指向头结点
    L=(LinkList)malloc(sizeof(LNode));
    // 头结点的指针域置空
    L->next=NULL;
    
    return OK;
}

3.1.2、取值

和顺序表不同，链表中逻辑相邻的结点，在物理存储上并不相邻。这样，根据给定的结点位置序号i，在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结点出发，顺着链域next逐个结点向后访问。该算法步骤为：

用指针p指向首元结点，用j做计数器初值赋为1。
从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空（NULL），并且没有到达序号为i的结点，则循环执行以下操作：
- p指向下一个结点；
- 计数器j加1。
退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或i小于等于0），取值失败返回ERROR；否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。

相应的算法描述为：

// 在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
Status GetElem(LinkList L, int i, ElemType &e) {
    // p指向首元结点，计数器j初值赋为1
    p=L->next;j=1;
    
    // 顺链域向后扫描，直到p为空或p指向第i个元素
    while(p && j<i) {
        // p指向下一个结点
        p=p->next;
        // p指向下一个结点
        ++j;
    }
    
    // i值不合法i>n或i≤0
    if(!p || j>i) return ERROR;
    
    // 取第i个结点的数据域
    e=p->data;
    
    return OK;
}

该算法的基本操作是比较j和i并后移指针p，while循环体中的语句频度与位置i有关。显然，该算法要分析其平均时间复杂度，在等概率情况下，其平均复杂度为O(n)。

3.1.3、查找

链表的按值查找过程和顺序表类似，从链表的首元结点出发，依次将结点值和给定值e进行比较，返回查找结果。该算法步骤为：

用指针p指向首元结点。
从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行以下操作：
- p指向下一个结点。
返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。

相应的算法描述为：

// 在带头结点的单链表L中查找值为e的元素
LNode *LocateElem(LinkList L, ElemType e) {
    // p指向首元结点
    p=L->next;
    
    // 顺链域向后扫描，直到p为空或p所指结点的数据域等于e
    while(p && p->data!=e) {
        // p指向下一个结点
        p=p->next;
    }
    
    // 查找成功返回值为e的结点地址p，查找失败p为NULL
    return p;
}

该算法的执行时间与待查找的值e的位置有关，需要分析其平均时间复杂度，在等概率情况下，其平均复杂度为O(n)。

3.1.4、插入

插入，是指将值为e的新结点插入到表的第i个结点的位置上，即插入到结点 $a_{i-1}$ 与结点 $a_i$ 之间。

其算法步骤为：

查找结点 $a_{i−1}$ 并由指针p指向该结点。
生成一个新结点*s。
将新结点*s的数据域置为e。
将新结点*s的指针域指向结点 $a_i$ 。
将结点*p的指针域指向新结点*s。

相应的算法描述为：

// 在带头结点的单链表L中第i个位置插入值为e的新结点
Status ListInsert(LinkList &L, int i, ElemType e) {
    p=L;j=0;
    
    // 查找第i−1个结点，p指向该结点
    while(p && j<i-1) {
        p=p->next;
        ++j;
    }
    
    // i值不合法（i>n+1或者i<1）
    if(!p || j>i-1) return ERROR;
    
    // 生成新结点*s
    s=new LNode;
    // 将结点*s的数据域置为e
    s->data=e;
    // 将结点*s的指针域指向结点ai
    s->next=p->next;
    // 将结点*p的指针域指向结点*s
    p->next=s;
    
    return OK;
}

单链表的插入操作虽然不需要像顺序表的插入操作那样需要移动元素，但其平均时间复杂度仍为O(n)。这是因为，为了在第i个结点之前插入一个新结点，必须首先找到第i−1个结点，在等概率情况下，该操作的平均复杂度为O(n)。

3.1.5、删除

删除，是指将第i个结点从链表中删去，即将链表第i-1个结点的指针指向第i+1个结点。

其步骤为：

查找结点 $a_{i−1}$ 并由指针p指向该结点。
临时保存待删除结点 $a_i$ 的地址在q中，以备释放。
将结点*p的指针域指向 $a_i$ 的直接后继结点。
释放结点 $a_i$ 的空间。

相应的算法描述为：

// 在带头结点的单链表L中，删除第i个元素
Status ListDelete(LinkList &L, int i) {
    p=L;j=0;
    
    while(p>next && j<i-1) {
        p=p->next;
        ++j;
    }
    
    // i值不合法（i>n或者i<1）
    if(!(p->next) || (j>i-1)) return ERROR;
    // 临时保存被删结点的地址以备释放
    q=p->next;
    // 改变删除结点前驱结点的指针域
    p->next=q->next;
    // 释放删除结点的空间
    free(q);
    
    return OK;
}

类似于插入算法，删除算法的平均时间复杂度亦为O(n)。

3.1.6、创建单链表

初始化操作是创建一个只有头结点的空链表，而前面的一些算法都是假定链表已经存在多个结点。那么，该如何建立一个包括若干个结点的链表呢？

链表和顺序表不同，它是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统按需即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。即从初始的空表状态起，依次生成各元素结点，并逐个插入链表。

根据结点插入位置的不同，链表的创建方法可分为前插法和后插法。

3.1.6.1、前插法

前插法，是指通过将新结点逐个插入到链表的头部（头结点之后）来创建链表。每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。如下图，是采用前插法创建线性表(a,b,c,d,e)的过程。因为每次是在链表的头部插入，所以应该逆位序输入数据，即应该依次输入e、d、c、b、a。

该算法步骤为：

创建一个只有头结点的空链表。
根据待创建链表中的元素个数n，循环n次执行以下操作：
- 生成一个新结点*p；
- 输入元素值赋给新结点*p的数据域；
- 将新结点*p插入到头结点之后。

相应的算法描述为：

//逆位序输入n个元素的值，建立带表头结点的单链表L
void CreateList_H(LinkList &L, int n) {
    // 先建立一个带头结点的空链表
    L=(LNode *)malloc(sizeof(LNode));
    L->next=NULL;

    for(i=0;i<n;++i) {
        // 生成新结点*p
        p=(LNode *)malloc(sizeof(LNode));
        // 输入元素值赋给新结点*p的数据域
        cin>>p->data;
        // 将新结点*p插入到头结点之后
        p->next=L->next;
        L->next=p;
    }
}

显然，该算法的时间复杂度与数据规模n有关，其时间复杂度为O(n)。

3.1.6.2、后插法

后插法，是指通过将新结点逐个插入到链表的尾部来创建链表。同前插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。如下图，是采用后插法创建线性表(a,b,c,d,e)的过程。

该算法步骤为：

创建一个只有头结点的空链表。
尾指针r初始化指向头结点。
根据待创建链表中的元素个数n，循环n次执行以下操作：
- 生成一个新结点*p；
- 输入元素值赋给新结点*p的数据域；
- 将新结点*p插入到尾结点*r之后；
- 尾指针r指向新的尾结点*p。

相应的算法描述为：

// 正位序输入n个元素的值，建立带表头结点的单链表L
void CreateList_R(LinkList &L, int n) {
    // 先建立一个带头结点的空链表
    L=(LNode *)malloc(sizeof(LNode));
    L->next=NULL;
    // 尾指针r指向头结点
    r=L;

    for(i=0;i<n;++i) {
        // 生成新结点
        p=(LNode *)malloc(sizeof(LNode));
        // 输入元素值赋给新结点*p的数据域
        cin>>p->data;
        // 将新结点*p插入尾结点*r之后
        p->next=NULL;
        r->next=p;
        // r指向新的尾结点*p
        r=p;
    }
}

显然，该算法的时间复杂度与数据规模n有关，其时间复杂度为O(n)。

3.1.7、头节点的作用

看到这里，我们可能会有一个疑问，在链表中，为什么要设置头节点？在回答这个问题之前，我们先来看看，在不设头节点的情况下，如何通过尾插法建立单链表。话不多说，我们直接上代码：

// 正位序输入n个元素的值，建立带表头结点的单链表L
void CreateList_R(LinkList &L, int n) {
    // 先将链表置空，即头尾指针都为NULL
    L=NULL;
    r=NULL;

    for(i=0;i<n;++i) {
        // 生成新结点
        p=(LNode *)malloc(sizeof(LNode));
        // 输入元素值赋给新结点*p的数据域
        cin>>p->data;
		p->next=NULL;
		
		// 链表为空时，将头指针指向新结点
		if(head==NULL) L=p;
		// 链表非空时，将新节点插入到尾节点之后
		else r->next=p;
  
        // r指向新的尾结点*p
        r=p;
    }
}

对比前面带头节点的尾插法，我们不难看出，对于首元节点，该算法要进行特殊处理，代码逻辑会变得复杂，且不易理解。概括来讲，在链表中增加头节点，有两个重要的作用：

便于首元结点的处理。在带头结点的链表中，首元结点的地址保存在头结点的指针域中，这样对链表的第一个数据元素的操作与其他数据元素相同，无需进行特殊处理。
便于空表和非空表的统一处理。假设L为单链表的头指针，当链表不设头结点时，头指针应该指向首元结点，如果链表为空，则头指针为空，判定空表的条件为：L==NULL。增加头结点后，若链表为空，则头结点的指针域为空，判定空表的条件为：L->next ==NULL，而这和非空表的处理是一致的。

3.2、循环链表

循环链表（Circular Linked List），是指链表中最后一个结点的指针域不为空，而是指向链表的头结点，使整个链表形成一个环。因此，从表中任一结点出发，都能访问到表中的其他结点。

在单循环链表中，为了使空表和非空表的处理一致，通常也会设置头结点。单循环链表的结点类型与单链表完全相同，在操作上也与单链表基本一致。差别仅在于，算法中循环的结束判断条件不再是p==NULL或p->next==NULL，而是它们是否等于头指针。

在某些情况下，若在循环链表中设立尾指针而不设头指针，可使一些操作简化。

例如，在将两个线性表合并成一个表时，仅需将第一个表（假设为A）的尾指针指向第二个表（假设为B）的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。这个操作仅需改变两个指针值即可，主要语句如下：

// 保存第二个表的第一个结点
p=B->next->next;
// 将第二个表的尾指针指向第一个表的头结点
B->next=A->next;
// 将第一个表的尾指针指向第二个表的第一个结点
A->next=p;

3.3、双向链表

双向链表，是在单链表的基础上增加一个指向其直接前趋的指针域prior，其结构如下：

在单链表中，只有一个指示直接后继的指针域，由此，从某个结点出发只能顺指针向后寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。换句话说，在单链表中，查找直接后继结点的执行时间为O(1)，而查找直接前驱的执行时间为O(n)。为克服单链表这种单向性的缺点，可使用双向链表（Double Linked List）。

和单链表的循环表类似，双向链表也由头指针唯一确定。为了使某些操作方便，双向链表也会增设一个头结点。双向链表也可以有循环表。其结构如下：

在C语言中，双向链表的描述如下：

// 双向链表的存储结构
typedef struct DuLNode {
    // 数据域
    ElemType data;
    // 前驱指针
    struct DuLNode *prior;
    // 后继指针
    struct DuLNode *next;
}DuLNode, *DuLinkList;

在双向链表中，有些操作（如ListLength、GetElem和LocateElem等）仅需涉及一个方向的指针，它们的算法描述和单链表的操作相同，但在插入、删除时有很大的不同。接下来，我们重点讨论这两种操作。

3.3.1、插入

在插入结点时需要修改四个指针，操作过程如下：

相应的算法描述为：

// 在带头结点的双向链表L中第i个位置之前插入元素e
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {
    // 指针p指向链表中第i个位置的元素
    if(!(p=GetEem_DuL(L,i))) return ERROR;
    
    // 生成新结点*s
    s=(DuLNode *)malloc(sizeof(DuLNode));
    // 将e赋给新结点的数据域
    s->data=e;
    // 插入新结点
    s->prior=p->prior;
    p->prior->next=s;
    s->next=p;
    p->prior=s;
    
    return OK;
}

该算法主要有两个操作：设置指针和获取第i个数据元素。前者的时间复杂度为O(1)，而后者需要分析其平均时间复杂度，在等概率情况下，该操作的平均复杂度为O(n)。

3.3.2、删除

在删除结点时需要修改两个指针，操作过程如下：

相应的算法描述为：

// 删除带头结点的双向链表L中的第i个元素
Status ListDelete_DuL(DuLinkList &L, int i) {
    // 指针p指向链表中第i个位置的元素
    if(!(p=GetElem_DuL(L,i))) return ERROR;
    
    p->prior->next=p->next;
    p->next->prior=p->prior;
    
    delete p;
    
    return OK;
}