安亭网站建设,深圳网站建设网站制作哪家好,wordpress the content,平台与网站有什么区别目录
单链表 1.1 无头单链表 1.2 有头单链表单向循环链表双链表 3.1 双链表 3.2 双向循环链表总结与对比 一、单链表
1. 无头单链表#xff08;Headless Singly Linked List#xff09;
定义#xff1a;链表无头结点#xff0c;直接由头指针指向第一个数据节点。
特点Headless Singly Linked List
定义链表无头结点直接由头指针指向第一个数据节点。
特点
插入/删除第一个节点需特殊处理。空链表时头指针为NULL。
核心代码
typedef struct LNode {int data;struct LNode *next;
} LNode, *LinkList;bool InitList(LinkList *L) {*L NULL;return true;
}bool insert_head(LinkList *L, LNode *new) {if (new NULL) return false;new-next *L;*L new;return true;
}示例操作
int main() {LinkList list;InitList(list);LNode *node newnode(11);insert_head(list, node); // 头部插入// ... 其他操作return 0;
}2. 有头单链表Singly Linked List with Header
定义链表包含头结点头指针始终指向头结点。
优点
插入/删除第一个节点与普通节点操作统一。空链表时头指针不为NULL统一处理逻辑。
核心代码
bool InitList(LinkList *L) {*L (LNode*)malloc(sizeof(LNode));(*L)-next NULL;return true;
}bool insert_head(LinkList L, LNode *new) {new-next L-next;L-next new;return true;
}bool insert_tail(LinkList L, LNode *new) {LNode *p L;while (p-next ! NULL) p p-next;p-next new;return true;
}示例操作
int main() {LinkList list;InitList(list);LNode *node newnode(11);insert_head(list, node); // 头部插入node newnode(88);insert_tail(list, node); // 尾部插入// ... 其他操作return 0;
}二、单向循环链表Circular Linked List
定义链表最后一个节点的next指向头结点形成循环。
特点
支持从任意节点开始遍历整个链表。删除操作需注意头结点的特殊处理。
核心代码
bool InitList(DLinkList *L) {*L (LNode*)malloc(sizeof(LNode));(*L)-next *L;return true;
}bool insert_head(LinkList L, LNode *new) {new-next L-next;L-next new;return true;
}LNode* delete_tail(LinkList L) {LNode *p L, *q L-next;while (q-next ! L) {p q;q q-next;}p-next L;return q;
}三、双链表Doubly Linked List
1. 双链表
定义每个节点包含prev和next指针支持双向遍历。
特点
可高效实现插入/删除操作需同时维护前后指针。需额外存储空间。
核心代码
typedef struct DNode {int data;struct DNode *prev, *next;
} DNode, *DLinkList;bool insert_head(DLinkList L, DNode *new) {new-next L-next;new-prev L;if (L-next ! NULL) L-next-prev new;L-next new;return true;
}DNode* delete(DLinkList L, DNode *node) {if (node L) return NULL;node-prev-next node-next;if (node-next ! NULL) node-next-prev node-prev;return node;
}2. 双向循环链表Circular Doubly Linked List
定义双链表最后一个节点的next指向头结点头结点的prev指向尾节点。
特点
支持高效双向遍历和循环操作。操作需处理循环指针。
核心代码
bool InitList(DLinkList *L) {*L (DNode*)malloc(sizeof(DNode));(*L)-next *L;(*L)-prev *L;return true;
}bool insert_head(DLinkList L, DNode *new) {new-next L-next;new-prev L;L-next-prev new;L-next new;return true;
}DNode* delete_tail(DLinkList L) {DNode *p L-prev;p-prev-next L;L-prev p-prev;return p;
}四、总结与对比
结构类型插入/删除时间复杂度优点缺点无头单链表O(n)简单头部操作需特殊处理有头单链表O(1)头插操作统一需额外头结点空间单向循环链表O(1)头插支持循环遍历需处理循环指针双链表O(1)双向操作支持双向遍历空间占用更大双向循环链表O(1)双向操作完全循环遍历实现复杂度最高 关键点总结
头结点的作用统一操作逻辑避免空指针问题。循环链表的优势遍历无需判断尾节点适合需要循环遍历的场景。双链表的适用场景需要频繁双向遍历或快速删除节点的场景如浏览器历史记录。
