【数据结构】不带表头节点的双向链表的基本操作 - 实践

一、数据结构定义

typedef struct DuLNode {ElemType data;           // 数据域（存储元素值）struct DuLNode *prior;   // 前驱指针（首元节点的prior为NULL）struct DuLNode *next;    // 后继指针（表尾节点的next为NULL）
} DuLNode, *DuLinkList;

• 每个节点包含 3 部分：数据域（data）、前驱指针（prior）、后继指针（next）。
• 无表头节点：首元节点（第一个有效节点）的prior固定为NULL，表尾节点的next固定为NULL；空表时L=NULL（无任何节点）。

二、核心算法详解

1. 初始化算法（InitDuLinkList）

功能：将链表初始化为空表（不带头节点，空表标识为L=NULL）。步骤：

1. 直接将链表头指针L置为NULL（表示无任何节点）。
2. 返回成功状态OK（无需分配内存，初始化一定成功）。

代码：

Status InitDuLinkList(DuLinkList &L) {L = NULL;  // 空表无任何节点，L直接为NULLreturn OK;
}

时间复杂度：O(1)（仅固定赋值操作）。与带表头节点的区别：无需创建表头节点，节省内存；空表判断直接用L==NULL。

2. 查找算法（GetElem_DuL）

功能：根据位置i（1-based，首元节点为第 1 个）查找节点，返回节点指针（未找到返回NULL）。步骤：

1. 边界条件判断：若链表为空（L==NULL）或i<1（位置非法），直接返回NULL。
2. 遍历初始化：从首元节点开始（p=L），计数器j=1（首元为第 1 个节点）。
3. 遍历查找：当p不为NULL且j < i时，移动p到下一个节点（p=p->next），j++。
4. 结果判断：
   • 若j==i且p!=NULL（找到第i个节点），返回p；
   • 否则（i超出表长或j>i），返回NULL。

代码：

DuLNode* GetElem_DuL(DuLinkList L, int i) {if (L == NULL || i < 1) return NULL;  // 空表或位置非法int j = 1;DuLNode *p = L;  // 从首元节点开始遍历while (p != NULL && j < i) {p = p->next;j++;}return (j == i && p != NULL) ? p : NULL;  // 检查是否找到
}

时间复杂度：O(n)（n为链表长度，最坏情况需遍历整个链表）。关键逻辑：不带头节点时，首元节点直接由L指向，遍历起点为L，而非带表头版本的L->next。

3. 插入算法（ListInsert_DuL）

功能：在第i个节点之前插入新元素e，返回操作状态（成功OK/ 失败ERROR）。核心思路：双向链表插入需修改 4 个指针（新节点的前驱 / 后继、前驱节点的后继、后继节点的前驱），但因不带头节点，插入首元（i=1）需特殊处理。

步骤：

1. 合法性初步判断：若i<1（位置非法），返回ERROR。

2. 创建新节点：分配内存创建节点s，设置s->data=e，初始化prior和next为NULL。若内存分配失败（s==NULL），返回OVERFLOW。

3. 场景 1：插入到第 1 个位置（成为新首元）：

   • 新节点s的后继指向原首元（s->next = L，空表时L=NULL，无问题）。
   • 若原链表非空（L!=NULL），原首元的前驱需指向s（L->prior = s）。
   • 更新链表头指针L为s（L = s），新节点成为首元。

4. 场景 2：插入到第i（i>1）个节点前：

   • 调用GetElem_DuL查找第i个节点p。若p==NULL（i超出表长），释放s并返回ERROR。
   •  4 个指针完成插入（顺序不可颠倒，避免断链）：

     s->prior = p->prior;        // 新节点前驱 = p的前驱（p的前驱一定存在，因i>1）
     s->prior->next = s;         // p的前驱的后继 = 新节点
     s->next = p;                // 新节点后继 = p
     p->prior = s;               // p的前驱 = 新节点

5. 返回OK。

代码：

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {// 1. 合法性初步判断：i<1直接非法if (i < 1) {return ERROR;}// 2. 创建新节点DuLNode *s = new DuLNode;if (!s) {  // 内存分配失败return OVERFLOW;}s->data = e;s->prior = NULL;s->next = NULL;// 3. 场景1：插入到第1个位置（成为新首元）if (i == 1) {s->next = L;          // 新节点的后继指向原首元（空表时L=NULL，无问题）if (L != NULL) {      // 若原链表非空，原首元的前驱指向新节点L->prior = s;}L = s;                // 链表头指针指向新首元return OK;}// 4. 场景2：插入到第i（i>1）个节点前DuLNode *p = GetElem_DuL(L, i);  // 找到第i个节点pif (p == NULL) {                 // 未找到第i个节点（i超出表长）delete s;                    // 释放未使用的新节点，避免内存泄漏return ERROR;}// 5. 修改4个指针完成插入（顺序不可颠倒，避免断链）s->prior = p->prior;        // 新节点的前驱 = p的前驱（p的前驱一定存在，因i>1）s->prior->next = s;         // p的前驱的后继 = 新节点s->next = p;                // 新节点的后继 = pp->prior = s;               // p的前驱 = 新节点return OK;
}

时间复杂度：O(n)（主要耗时在查找第i个节点，i=1时为O(1)）。边界处理：

• 空表插入（L=NULL且i=1）：直接将s作为首元，L=s。
• 非空表插入首元：需同步修改原首元的prior指针。

4. 删除算法（ListDelete_DuL）

功能：删除第i个节点，返回操作状态（成功OK/ 失败ERROR）。核心思路：通过修改前驱节点的后继和后继节点的前驱，断开待删除节点的链接，再释放内存。因不带头节点，删除首元（i=1）需特殊处理。

步骤：

1. 边界条件判断：若链表为空（L==NULL）或i<1（位置非法），返回ERROR。

2. 查找待删除节点：调用GetElem_DuL获取第i个节点p。若p==NULL（i超出表长），返回ERROR。

3. 场景 1：删除首元节点（p->prior==NULL，因i=1）：

   • 更新链表头指针L为p的后继（L = p->next）。
   • 若新首元存在（L!=NULL），其前驱需置为NULL（首元无前置节点）：L->prior = NULL。

4. 场景 2：删除非首元节点（p->prior!=NULL）：

   • 修改前驱节点的后继：p->prior->next = p->next（跳过p）。
   • 若p不是表尾（p->next!=NULL），修改后继节点的前驱：p->next->prior = p->prior（跳过p）。

5. 释放p的内存（delete p），返回OK。

代码：

Status ListDelete_DuL(DuLinkList &L, int i) {// 1. 边界条件：空表或i<1直接非法if (L == NULL || i < 1) {return ERROR;}// 2. 找到第i个节点pDuLNode *p = GetElem_DuL(L, i);if (p == NULL) {  // 未找到第i个节点（i超出表长）return ERROR;}// 3. 场景1：删除首元节点（p的prior为NULL，因i=1）if (p->prior == NULL) {L = p->next;          // 链表头指针指向新首元（p的后继）if (L != NULL) {      // 若新首元存在，其前驱置为NULL（首元无前置）L->prior = NULL;}}// 4. 场景2：删除非首元节点（p的prior不为NULL）else {p->prior->next = p->next;  // p的前驱的后继 = p的后继if (p->next != NULL) {     // 若p不是表尾，p的后继的前驱 = p的前驱p->next->prior = p->prior;}}// 5. 释放被删除节点的内存delete p;return OK;
}

时间复杂度：O(n)（主要耗时在查找第i个节点，i=1时为O(1)）。边界处理：

• 删除唯一节点（L->next==NULL且i=1）：删除后L=NULL（空表）。
• 删除表尾节点（p->next==NULL）：无需修改后继节点的前驱（避免空指针访问）。

5. 打印算法（PrintDuLinkList）

功能：从首元节点开始，依次输出链表中所有元素（空表时输出 “空表”）。步骤：

1. 若链表为空（L==NULL），输出 “当前双向链表元素：空表”。
2. 否则，从首元节点（p=L）开始遍历，依次打印p->data，直到p==NULL（表尾）。

代码：

void PrintDuLinkList(DuLinkList L) {if (L == NULL) {cout << "当前双向链表元素：空表" << endl;return;}DuLNode *p = L;cout << "当前双向链表元素：";while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}

时间复杂度：O(n)（需遍历所有节点）。

三、主函数流程（算法验证）

1. 初始化：调用InitDuLinkList将L置为NULL（空表）。
2. 插入测试：
   • 输入n个元素，均插入到第 1 个位置前（存储顺序与输入顺序相反，如输入1 2 3，链表为3 2 1）。
   • 每次插入后输出结果，最后打印整个链表。
3. 删除测试：
   • 输入删除位置delPos，调用ListDelete_DuL删除对应节点。
   • 输出删除结果并打印修改后的链表。
4. 内存释放：遍历所有节点并释放（delete），最后置L=NULL避免野指针。

四、完整代码

C++代码如下：

#include
using namespace std;
typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
// 双向链表节点结构（无表头节点，首元节点直接由L指向）
typedef struct DuLNode {ElemType data;           // 数据域struct DuLNode *prior;   // 前驱指针（首元节点的prior为NULL）struct DuLNode *next;    // 后继指针（表尾节点的next为NULL）
} DuLNode, *DuLinkList;
// 函数声明（均适配不带头节点特性）
Status InitDuLinkList(DuLinkList &L);  // 初始化（空表时L=NULL）
DuLNode* GetElem_DuL(DuLinkList L, int i);  // 查找第i个节点（首元为第1个）
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e);  // 插入元素
Status ListDelete_DuL(DuLinkList &L, int i);  // 删除元素
void PrintDuLinkList(DuLinkList L);  // 打印链表（从首元开始）
int main() {DuLinkList L;int n, e, delPos;// 1. 初始化双向链表（不带头节点，空表时L=NULL）if (InitDuLinkList(L) != OK) {cout << "双向链表初始化失败！" << endl;return 1;}cout << "双向链表初始化成功！（空表时L=NULL）" << endl;// 2. 测试插入操作（所有元素插入到第1个位置前，即逆序存储）cout << "\n============ 测试插入操作 ============" << endl;cout << "请输入要插入的元素个数：";cin >> n;if (n <= 0) {cout << "元素个数必须为正整数！" << endl;return 1;}cout << "请依次输入" << n << "个元素（将插入到链表第1个位置前）：" << endl;for (int k = 1; k <= n; k++) {cin >> e;if (ListInsert_DuL(L, 1, e) == OK) {cout << "插入元素 " << e << " 到位置1前成功！" << endl;} else {cout << "插入元素 " << e << " 到位置1前失败！" << endl;}}PrintDuLinkList(L);// 3. 测试删除操作cout << "\n============ 测试删除操作 ============" << endl;cout << "请输入要删除的位置（1~" << n << "）：";cin >> delPos;if (ListDelete_DuL(L, delPos) == OK) {cout << "删除位置" << delPos << "的元素成功！" << endl;PrintDuLinkList(L);} else {cout << "删除位置" << delPos << "不合法或元素不存在！" << endl;}// 4. 释放内存（遍历删除所有节点，不带头节点无需删表头）DuLNode *p = L, *q;while (p != NULL) {q = p;p = p->next;delete q;  // 释放当前节点}L = NULL;  // 避免野指针return 0;
}
// -------------------------- 核心函数实现（不带头节点） --------------------------
// 1. 初始化双向链表（不带头节点），空表标识：L=NULL（无任何节点，区别于带表头的空表）
Status InitDuLinkList(DuLinkList &L) {L = NULL;  // 不带头节点，空表时直接置为NULLreturn OK;  // 无需分配内存，初始化一定成功
}
// 2. 查找第i个节点（不带头节点，1-based），返回值：找到返回节点指针，未找到（空表/i非法/i超出表长）返回NULL
DuLNode* GetElem_DuL(DuLinkList L, int i) {// 边界条件：空表或i<1直接返回NULLif (L == NULL || i < 1) {return NULL;}int j = 1;          // 计数器：首元节点为第1个DuLNode *p = L;     // 从首元节点开始遍历（不带头节点，L即首元）// 遍历到第i个节点，或p为NULL（i超出表长）while (p != NULL && j < i) {p = p->next;j++;}// 若j>i（i非法）或p==NULL（i超出表长），返回NULL；否则返回preturn (j == i && p != NULL) ? p : NULL;
}
// 3. 插入元素e到第i个节点前（不带头节点），核心处理：分“插入首元（i=1）”和“插入非首元（i>1）”两种场景
Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) {// 1. 合法性初步判断：i<1直接非法if (i < 1) {return ERROR;}// 2. 创建新节点DuLNode *s = new DuLNode;if (!s) {  // 内存分配失败return OVERFLOW;}s->data = e;s->prior = NULL;s->next = NULL;// 3. 场景1：插入到第1个位置（成为新首元）if (i == 1) {s->next = L;          // 新节点的后继指向原首元（空表时L=NULL，无问题）if (L != NULL) {      // 若原链表非空，原首元的前驱指向新节点L->prior = s;}L = s;                // 链表头指针指向新首元return OK;}// 4. 场景2：插入到第i（i>1）个节点前DuLNode *p = GetElem_DuL(L, i);  // 找到第i个节点pif (p == NULL) {                 // 未找到第i个节点（i超出表长）delete s;                    // 释放未使用的新节点，避免内存泄漏return ERROR;}// 5. 修改4个指针完成插入（顺序不可颠倒，避免断链）s->prior = p->prior;        // 新节点的前驱 = p的前驱（p的前驱一定存在，因i>1）s->prior->next = s;         // p的前驱的后继 = 新节点s->next = p;                // 新节点的后继 = pp->prior = s;               // p的前驱 = 新节点return OK;
}
// 4. 删除第i个节点（不带头节点），核心处理：分“删除首元（i=1）”和“删除非首元（i>1）”两种场景
Status ListDelete_DuL(DuLinkList &L, int i) {// 1. 边界条件：空表或i<1直接非法if (L == NULL || i < 1) {return ERROR;}// 2. 找到第i个节点pDuLNode *p = GetElem_DuL(L, i);if (p == NULL) {  // 未找到第i个节点（i超出表长）return ERROR;}// 3. 场景1：删除首元节点（p的prior为NULL，因i=1）if (p->prior == NULL) {L = p->next;          // 链表头指针指向新首元（p的后继）if (L != NULL) {      // 若新首元存在，其前驱置为NULL（首元无前置）L->prior = NULL;}}// 4. 场景2：删除非首元节点（p的prior不为NULL）else {p->prior->next = p->next;  // p的前驱的后继 = p的后继if (p->next != NULL) {     // 若p不是表尾，p的后继的前驱 = p的前驱p->next->prior = p->prior;}}// 5. 释放被删除节点的内存delete p;return OK;
}
// 5. 打印链表（不带头节点，从首元开始遍历），空表时输出“空表”，非空表输出所有元素
void PrintDuLinkList(DuLinkList L) {if (L == NULL) {  // 不带头节点的空表cout << "当前双向链表元素：空表" << endl;return;}DuLNode *p = L;  // 从首元节点开始遍历（L即首元）cout << "当前双向链表元素：";while (p != NULL) {cout << p->data << " ";p = p->next;}cout << endl;
}

程序运行结果如下：

Python代码如下：

# 定义状态常量（对应原C++的宏定义）
OK = 1
ERROR = 0
OVERFLOW = -2
# 1. 双向链表节点类（对应原C++的DuLNode结构体）
class DuLNode:def __init__(self, data=0):self.data = data          # 数据域（默认值0，对应原ElemType=int）self.prior = None         # 前驱引用（替代C++的prior指针，初始无引用）self.next = None          # 后继引用（替代C++的next指针，初始无引用）
# 2. 双向链表核心类（封装所有操作，对应原C++的函数集合）
class DoublyLinkedList:def __init__(self):self.head = None  # 链表头引用（对应原C++的L，空表时为None）def InitDuLinkList(self):"""初始化双向链表（不带头节点，空表标识为head=None，对应原C++ InitDuLinkList）"""self.head = None  # 不带头节点，空表无任何节点，直接置为Nonereturn OK  # 无需分配内存，初始化一定成功def GetElem_DuL(self, i):"""查找第i个节点（1-based，首元为第1个），返回节点对象；未找到返回None（对应原C++ GetElem_DuL）"""# 边界条件：空表或i<1直接返回Noneif self.head is None or i < 1:return Nonej = 1  # 计数器：从首元节点开始计数p = self.head  # 从首元节点开始遍历（不带头节点，head即首元）# 遍历到第i个节点，或p为None（i超出表长）while p is not None and j < i:p = p.nextj += 1# 仅当j==i且p不为None时，返回找到的节点return p if (j == i and p is not None) else Nonedef ListInsert_DuL(self, i, e):"""在第i个节点前插入元素e，返回状态码（OK/ERROR/OVERFLOW，对应原C++ ListInsert_DuL）"""# 1. 合法性初步判断：i<1直接非法if i < 1:return ERROR# 2. 创建新节点（模拟C++的new DuLNode）try:s = DuLNode(e)except MemoryError:# 内存分配失败（Python中极少发生，对应原C++的!s）return OVERFLOW# 3. 场景1：插入到第1个位置（成为新首元）if i == 1:s.next = self.head  # 新节点的后继指向原首元（空表时head=None，无问题）if self.head is not None:  # 若原链表非空，原首元的前驱指向新节点self.head.prior = sself.head = s  # 链表头引用指向新首元return OK# 4. 场景2：插入到第i（i>1）个节点前p = self.GetElem_DuL(i)  # 找到第i个节点pif p is None:  # 未找到第i个节点（i超出表长）return ERROR  # Python无需手动释放节点（垃圾回收自动处理）# 5. 修改4个引用完成插入（顺序不可颠倒，避免断链）s.prior = p.prior        # 新节点的前驱 = p的前驱（p的前驱一定存在，因i>1）s.prior.next = s         # p的前驱的后继 = 新节点s.next = p               # 新节点的后继 = pp.prior = s              # p的前驱 = 新节点return OKdef ListDelete_DuL(self, i):"""删除第i个节点，返回状态码（OK/ERROR，对应原C++ ListDelete_DuL）"""# 1. 边界条件：空表或i<1直接非法if self.head is None or i < 1:return ERROR# 2. 找到第i个节点pp = self.GetElem_DuL(i)if p is None:  # 未找到第i个节点（i超出表长）return ERROR# 3. 场景1：删除首元节点（p的prior为None，因i=1）if p.prior is None:self.head = p.next  # 链表头引用指向新首元（p的后继）if self.head is not None:  # 若新首元存在，其前驱置为None（首元无前置）self.head.prior = None# 4. 场景2：删除非首元节点（p的prior不为None）else:p.prior.next = p.next  # p的前驱的后继 = p的后继if p.next is not None:  # 若p不是表尾，p的后继的前驱 = p的前驱p.next.prior = p.prior# Python无需手动释放节点（垃圾回收自动处理无引用节点）return OKdef PrintDuLinkList(self):"""打印链表（从首元开始，空表输出“空表”，对应原C++ PrintDuLinkList）"""if self.head is None:  # 不带头节点的空表print("当前双向链表元素：空表")return# 从首元节点开始遍历（head即首元）p = self.headprint("当前双向链表元素：", end="")while p is not None:print(p.data, end=" ")p = p.nextprint()  # 换行
# 3. 主函数（测试流程，完全对应原C++ main函数）
def main():# 初始化双向链表dl_list = DoublyLinkedList()if dl_list.InitDuLinkList() != OK:print("双向链表初始化失败！")return 1print("双向链表初始化成功！（空表时L=NULL）")# 测试插入操作（所有元素插入到第1个位置前，逆序存储）print("\n============ 测试插入操作 ============")# 输入插入元素个数try:n = int(input("请输入要插入的元素个数："))except ValueError:print("输入无效！元素个数必须为正整数。")return 1if n <= 0:print("元素个数必须为正整数！")return 1# 输入n个元素并插入print(f"请依次输入{n}个元素（将插入到链表第1个位置前）：")for k in range(1, n + 1):try:e = int(input(f"请输入第{k}个元素："))except ValueError:print(f"输入无效！第{k}个元素必须为整数，跳过该元素。")continue# 执行插入并输出结果if dl_list.ListInsert_DuL(1, e) == OK:print(f"插入元素 {e} 到位置1前成功！")else:print(f"插入元素 {e} 到位置1前失败！")# 打印插入后的链表dl_list.PrintDuLinkList()# 测试删除操作print("\n============ 测试删除操作 ============")try:del_pos = int(input(f"请输入要删除的位置（1~{n}）："))except ValueError:print("输入无效！删除位置必须为整数。")return 1# 执行删除并输出结果if dl_list.ListDelete_DuL(del_pos) == OK:print(f"删除位置{del_pos}的元素成功！")dl_list.PrintDuLinkList()else:print(f"删除位置{del_pos}不合法或元素不存在！")# Python无需手动释放内存（垃圾回收自动处理所有节点）return 0
# 执行主函数
if __name__ == "__main__":main()

程序运行结果如下：

Java代码如下：

import java.util.InputMismatchException;
import java.util.Scanner;
// 不带头节点的双向链表主类
public class DoublyLinkedList {// 状态常量（对应原C++的宏定义）public static final int OK = 1;public static final int ERROR = 0;public static final int OVERFLOW = -2;// 双向链表节点类（对应原C++的DuLNode结构体，内部类实现）static class DuLNode {int data;          // 数据域（对应原ElemType=int）DuLNode prior;     // 前驱引用（替代C++指针，首元节点的prior为null）DuLNode next;      // 后继引用（替代C++指针，表尾节点的next为null）// 构造器：初始化数据域public DuLNode(int data) {this.data = data;this.prior = null;this.next = null;}}private DuLNode head;  // 链表头引用（对应原C++的L，空表时为null）private Scanner scanner; // 输入工具（替代C++的cin）// 构造器：初始化输入工具public DoublyLinkedList() {this.head = null;    // 不带头节点，初始为空表this.scanner = new Scanner(System.in);}// -------------------------- 核心函数实现（与原C++一一对应） --------------------------/*** 1. 初始化双向链表（不带头节点）* 空表标识：head=null（无任何节点），对应原C++ InitDuLinkList*/public int InitDuLinkList() {this.head = null; // 空表直接置head为null，无需分配内存return OK;        // 初始化一定成功}/*** 2. 查找第i个节点（1-based，首元为第1个）* 返回值：找到返回节点引用，未找到（空表/i非法/i超出表长）返回null，对应原C++ GetElem_DuL*/public DuLNode GetElem_DuL(int i) {// 边界条件：空表或i<1直接返回nullif (this.head == null || i < 1) {return null;}int j = 1;          // 计数器：从首元节点开始计数DuLNode p = this.head; // 从首元节点开始遍历（不带头节点，head即首元）// 遍历到第i个节点，或p为null（i超出表长）while (p != null && j < i) {p = p.next;j++;}// 仅当j==i且p不为null时，返回找到的节点return (j == i && p != null) ? p : null;}/*** 3. 插入元素e到第i个节点前（不带头节点）* 返回状态码：OK/ERROR/OVERFLOW，对应原C++ ListInsert_DuL*/public int ListInsert_DuL(int i, int e) {// 1. 合法性初步判断：i<1直接非法if (i < 1) {return ERROR;}// 2. 创建新节点（模拟C++的new DuLNode，Java内存分配失败时抛OutOfMemoryError）DuLNode s;try {s = new DuLNode(e);} catch (OutOfMemoryError e1) {return OVERFLOW; // 对应原C++的内存分配失败（!s）}// 3. 场景1：插入到第1个位置（成为新首元）if (i == 1) {s.next = this.head; // 新节点的后继指向原首元（空表时head=null，无问题）if (this.head != null) { // 若原链表非空，原首元的前驱指向新节点this.head.prior = s;}this.head = s; // 链表头引用指向新首元return OK;}// 4. 场景2：插入到第i（i>1）个节点前DuLNode p = GetElem_DuL(i); // 找到第i个节点pif (p == null) { // 未找到第i个节点（i超出表长）return ERROR; // Java无需手动释放s（垃圾回收自动处理）}// 5. 修改4个引用完成插入（顺序不可颠倒，避免断链）s.prior = p.prior;        // 新节点的前驱 = p的前驱（p的前驱一定存在，因i>1）s.prior.next = s;         // p的前驱的后继 = 新节点s.next = p;                // 新节点的后继 = pp.prior = s;               // p的前驱 = 新节点return OK;}/*** 4. 删除第i个节点（不带头节点）* 返回状态码：OK/ERROR，对应原C++ ListDelete_DuL*/public int ListDelete_DuL(int i) {// 1. 边界条件：空表或i<1直接非法if (this.head == null || i < 1) {return ERROR;}// 2. 找到第i个节点pDuLNode p = GetElem_DuL(i);if (p == null) { // 未找到第i个节点（i超出表长）return ERROR;}// 3. 场景1：删除首元节点（p的prior为null，因i=1）if (p.prior == null) {this.head = p.next; // 链表头引用指向新首元（p的后继）if (this.head != null) { // 若新首元存在，其前驱置为null（首元无前置）this.head.prior = null;}}// 4. 场景2：删除非首元节点（p的prior不为null）else {p.prior.next = p.next;  // p的前驱的后继 = p的后继if (p.next != null) {     // 若p不是表尾，p的后继的前驱 = p的前驱p.next.prior = p.prior;}}// Java无需手动释放p（垃圾回收自动处理无引用节点）return OK;}/*** 5. 打印链表（不带头节点，从首元开始）* 空表输出“空表”，非空表输出所有元素，对应原C++ PrintDuLinkList*/public void PrintDuLinkList() {if (this.head == null) { // 不带头节点的空表System.out.println("当前双向链表元素：空表");return;}// 从首元节点开始遍历（head即首元）DuLNode p = this.head;System.out.print("当前双向链表元素：");while (p != null) {System.out.print(p.data + " ");p = p.next;}System.out.println();}// -------------------------- 主函数（测试流程，对应原C++ main） --------------------------public static void main(String[] args) {DoublyLinkedList dlList = new DoublyLinkedList();int n = 0, e = 0, delPos = 0;// 1. 初始化双向链表if (dlList.InitDuLinkList() != OK) {System.out.println("双向链表初始化失败！");return;}System.out.println("双向链表初始化成功！（空表时L=NULL）");// 2. 测试插入操作（所有元素插入到第1个位置前，逆序存储）System.out.println("\n============ 测试插入操作 ============");// 输入插入元素个数while (true) {try {System.out.print("请输入要插入的元素个数：");n = dlList.scanner.nextInt();if (n > 0) {break;} else {System.out.println("元素个数必须为正整数！请重新输入：");}} catch (InputMismatchException ex) {System.out.println("输入无效！请输入整数：");dlList.scanner.next(); // 清除无效输入缓存，避免死循环}}// 输入n个元素并插入System.out.println("请依次输入" + n + "个元素（将插入到链表第1个位置前）：");for (int k = 1; k <= n; k++) {while (true) {try {System.out.print("请输入第" + k + "个元素：");e = dlList.scanner.nextInt();break;} catch (InputMismatchException ex) {System.out.println("输入无效！请输入整数：");dlList.scanner.next(); // 清除无效输入}}// 执行插入并输出结果if (dlList.ListInsert_DuL(1, e) == OK) {System.out.println("插入元素 " + e + " 到位置1前成功！");} else {System.out.println("插入元素 " + e + " 到位置1前失败！");}}dlList.PrintDuLinkList();// 3. 测试删除操作System.out.println("\n============ 测试删除操作 ============");while (true) {try {System.out.print("请输入要删除的位置（1~" + n + "）：");delPos = dlList.scanner.nextInt();if (delPos >= 1 && delPos <= n) {break;} else {System.out.println("删除位置需在1~" + n + "之间！请重新输入：");}} catch (InputMismatchException ex) {System.out.println("输入无效！请输入整数：");dlList.scanner.next(); // 清除无效输入}}// 执行删除并输出结果if (dlList.ListDelete_DuL(delPos) == OK) {System.out.println("删除位置" + delPos + "的元素成功！");dlList.PrintDuLinkList();} else {System.out.println("删除位置" + delPos + "不合法或元素不存在！");}// Java无需手动释放内存（垃圾回收自动处理）dlList.scanner.close(); // 关闭输入流}
}

程序运行结果如下：

五、不带头节点双向链表的特性总结

特性	具体说明
空表标识	L=NULL（无任何节点），判断简单直接。
内存占用	比带表头节点节省一个节点的内存（无需额外表头）。
首元操作复杂度	插入 / 删除首元时需修改L指针，逻辑稍复杂（需处理空表→非空表、非空表→空表的转换）。
边界条件处理	需频繁判断L==NULL（空表）和p->prior==NULL（首元），否则易出现空指针错误。
适用场景	内存受限、对空间效率要求高的场景（如嵌入式系统），但代码复杂度略高于带表头版本。

六、与带表头节点的双向链表的算法对比

操作	不带头节点版本	带表头节点版本
初始化	L=NULL（无需分配内存）	创建表头节点（L=new DuLNode），L->next=NULL
查找起点	从L（首元）开始	从L->next（首元）开始
插入首元	需修改L为新节点，处理原首元的prior	无需修改L，直接插入表头后
删除首元	需修改L为原首元的next，处理新首元的prior	无需修改L，直接删除表头后的首元
空表判断	L==NULL	L->next==NULL