一、结构属性
- 相邻元素之间通过指针连接；
- 最后一个元素的后继指针为NULL；
- 链表的空间能够按需分配；
- 没有内存空间的浪费。
1 // 结构体定义链表 2 struct ListNode { 3 int val; 4 struct ListNode *next; 5 ListNode(int x) : 6 val(x), next(NULL) { 7 } 8 };
二、链表的优缺点
- 链表的优点：
- 链表可以在常数时间内扩展；
- 容易添加新元素。
- 链表的缺点：
- 访问单个元素的时间开销问题过大；
- 有时难对链表操作，如果要删除最后一项，则必须遍历到倒数第二项，并对其后继操作。
- 链表中的额外指针引用需要浪费内存。
三、基本操作
- 创建链表；
1 ListNode* CreateList(){ 2 ListNode* head, *p; 3 head = new ListNode(NULL); //设定头指针 4 p = head; // 声明移动指针一开始指向头节点 5 for(int i = 0; i < 6; i ++ ){ 6 ListNode *s = new ListNode(i); //声明一个用来存储数据的链表结点 7 p->next = s; // 将此节点与指针结点连接 8 p = s; //保证 p 一直指向最后一个结点 9 } 10 head = head->next; //第一个指针没有存储任何数据 11 return head; 12 }
- 遍历链表
1 void traversalList(ListNode* head){ 2 ListNode* p = head; 3 while( p != NULL){ 4 cout << p->val <<" "; 5 p = p->next; 6 } 7 }
- 从链表中插入一个元素；
代码：
1 ListNode* InsertList(ListNode* head){ 2 ListNode* p = head; 3 ListNode* arg = new ListNode(9); //要插入的元素； 4 for(int i = 0; i < 2; i ++){ //将链表指针指向第三个元素 5 p = p->next; 6 } 7 ListNode* temp = p->next; //利用一个中介指针 将当前节点的后继存储 8 p->next = arg; // 使 arg 插入到当前节点的后面 9 p->next->next = temp; // 将之前的后继接回来 10 11 return head; 12 }
实现过程：
- 从链表中删除一个元素；
代码：
1 ListNode* DeleteList(ListNode* head){ 2 ListNode* p = head; 3 for(int i = 0; i < 2; i ++){// 将链表指针指向要删除的结点的前一位 4 p = p->next; 5 } 6 ListNode* temp = p->next->next; //记录要删除结点的后继 7 p->next = temp; // 将后继直接存储到当前节点的next位置 8 9 return head; 10 }
实现过程：
- 反转链表；
1 ListNode* ReserveList(ListNode* head){ 2 ListNode* pre = NULL; 3 ListNode* cur = head; 4 ListNode* temp; 5 while(cur != NULL){ 6 temp = cur->next; //记录当前结点的后继 7 cur->next = pre; //将当前节点的前驱存储到当前结点的后继位置 8 pre = cur; //将前驱指针向后移动一位至当前结点 9 cur = temp; // 将当前指针向后移动一位至后继 10 } 11 return pre; 12 }
- 删除链表。
1 ListNode* DeleteAllList(ListNode* head){ 2 ListNode* p = head; 3 ListNode* temp; 4 while( p != NULL){ 5 temp = p; // 用临时变量存储当前结点 6 p = p->next; //当前位置指针指向下一节点 7 delete temp; // 删除当前结点 8 } 9 return p; 10 }