数据结构——顺序表与链表
目录
前言
一线性表
二顺序表
1实现
2相关面试题
2.1移除元素
2.2删除有序数组中的重复项
3.3合并两个有序数组
3问题
三链表
1链表的分类
1.1单向或者双向
1.2带头或者不带头
1.3循环或者非循环
2实现
2.1尾插与头插
2.2尾删与头删
2.3pos前插入节点与删除pos位置
四相关练习题
链表的中间结点
移除链表元素
反转链表
链表分割
合并两个有序链表
链表中倒数第k个结点
相交链表
环形链表
环形链表 II
链表的回文结构
随机链表的复制
五双链表
实现
六总结
七其它知识
前言
学习顺序表和链表一定要画图！！！图画的好学起来就简单些！！！
一线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。 但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式的形式储存
二顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储
一般分为两种：
静态储存（不常用）
动态储存（实践常用）
1实现
实现顺序表一般是实现动态顺序表的增删查改
//SqList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SqList
{
SLDataType*_a;
int _size;
int _capacity;
}SL;
void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPushBack(SL* ps,SLDataType x);
void SLPushFront(SL*ps,SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLPrint(SL* ps);
void SLInsert(SL* ps,int pos,SLDataType x);
void SLErase(SL* ps,int pos);
int SLFindPos(SL* ps,SLDataType x);
//SqList.c
#include "SqList.h"
// 实现时进行的ps都要进行检查，防止为空出现越界访问
void SLInit(SL *ps)
{
assert(ps);
// 这里可malloc也可不malloc
ps->_a = NULL;
ps->_capacity = 0;
ps->_size = 0;
}
void SLDestory(SL *ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = 0;
ps->_size = 0;
}
static void SLCheckCapacity(SL *ps)
{
if (ps->_capacity == ps->_size)
{
int newcapacity = ps->_capacity == 0 ? 2 : ps->_capacity * 2;
SLDataType *new = (SLDataType *)realloc(ps->_a, newcapacity); // ps->a为空是相当于malloc
if (new == NULL)
{
perror("realloc error");
exit(-1);
}
ps->_a = new;
ps->_capacity = newcapacity;
}
}
void SLPushBack(SL *ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->_a[ps->_size] = x;
ps->_size++;
}
void SLPushFront(SL *ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
for (int end = ps->_size; end > 0; end--)
{
ps->_a[end] = ps->_a[end - 1];
}
ps->_a[0] = x;
ps->_size++;
}
void SLPopBack(SL *ps)
{
assert(ps);
// ps->_size为0进行删除不符合规定(没数据怎么删)
assert(ps->_size > 0);
// ps->_a[ps->_size-1]=-1;//1删除数据让新数据进行覆盖即可;2如果该位置的值刚好是-1(不是int类型)呢?
ps->_size--;
}
void SLPopFront(SL *ps)
{
assert(ps);
assert(ps->_size > 0);
for (int begin = 0; begin < ps->_size - 1; begin++)
{
ps->_a[begin] = ps->_a[begin + 1];
}
ps->_size--;
}
void SLPrint(SL *ps)
{
for (int i = 0; i < ps->_size; i++)
{
printf("%d ", ps->_a[i]);
}
printf("\n");
}
void SLInsert(SL *ps, int pos, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);
assert(pos >= 0 && pos <= ps->_size);
for (int end = ps->_size; end > pos; end--)
{
ps->_a[end] = ps->_a[end - 1];
}
ps->_a[pos] = x;
ps->_size++;
}
void SLErase(SL *ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->_size);
for (int begin = pos; begin < ps->_size - 1; begin++)
{
ps->_a[begin] = ps->_a[begin + 1];
}
ps->_size--;
}
int SLFindPos(SL *ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->_size; i++)
{
if (ps->_a[i] == x)
return i;
}
return -1;
}
//Test.c
// #include"SqList.h"//实现函数SqList.c先进行汇编后生成的文件与Test.c一起编译
#include "SqList.c"
void Test1()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPrint(&s);
SLPushFront(&s, 5);
SLPrint(&s);
SLDestory(&s);
}
void Test2()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPushBack(&s, 5);
SLPrint(&s);
SLPopBack(&s);
SLPopBack(&s);
SLPopFront(&s);
SLPrint(&s);
SLDestory(&s);
}
void Test3()
{
SL s;
SLInit(&s);
SLInsert(&s, 0, 10);
SLPrint(&s);
SLErase(&s, 0);
SLPrint(&s);
SLDestory(&s);
}
void Test4()
{
SL s;
SLInit(&s);
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPrint(&s);
int pos = SLFindPos(&s, 2);
if (pos != -1)
{
SLErase(&s, pos);
}
SLPrint(&s);
}
int main()
{
// Test1();
// Test2();
// Test3();
Test4();
return 0;
}2相关面试题
2.1移除元素
思路1 O(N) = N O(n) = n
定义一个辅助数组，把不是val的值尾插到该数组中，最后再拷贝到原数组中；
思路2 O(N) = N O(n) = 1
定义两个指针src，des；
int removeElement(int *nums, int numsSize, int val)
{
int src = 0, des = 0;
while (des < numsSize)
{
if (nums[des] != val)
nums[src++] = nums[des++];
else
des++;
}
return src;
}2.2删除有序数组中的重复项
思路：
定义两个指针src=0，des=1;
当nums[src]==nums[des]时只需des++即可
如果不相等，这时 nums[++src] = nums[des++] （注意是先++src再赋值）
本质就是利用两个指针进行去重操作
int removeDuplicates(int *nums, int numsSize)
{
int src = 0, des = 1;
while (des < numsSize)
{
if (nums[src] == nums[des])
des++;
else
nums[++src] = nums[des++];
}
return src + 1;
}3.3合并两个有序数组
思路1 O(N) = N O(n) = N
开辟一个辅助数组，定义两个指针分别指向两个数组起始位置，取小的进行尾插到辅助数组后指向小位置的指针向后移动
思路2 O(N) = N O(n) = 1
题目要我们把结果放到nums1中且已经开好足够的空间；
如果按照思路1的方法取下的尾插到nums1中势必会造成数组丢失（nums1中元素被覆盖）
所以我们定义两个指针i1,i2分别指向两个数组末尾(num1的末尾是等于m)，再定义指针i指向num1的真正末尾处，取大的数放到该位置后i--,指向大的数的位置的指针(例如是i1)--
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int i1 = m - 1, i2 = n - 1, i = nums1Size - 1;
//关键在移动比较的是i1和i2,哪个停下来就说明哪个走完了
while (i1 >= 0 && i2 >= 0)
{
if (nums1[i1] > nums2[i2]) nums1[i--] = nums1[i1--];
else nums1[i--] = nums2[i2--];
}
//i2没走完要进行拷贝过去
while (i2 >= 0) nums1[i--] = nums2[i2--];
}3问题
1.尾插效率还行；
但如果是头插或者在任意位置进行插入或者删除时就需要移动数据，效率差；
2.进行扩容时可能导致频繁扩容或者扩容出来的空间可能被浪费
（比如扩容100个只存了1个）
解决上面的问题，用一种新的数据结构——链表来解决！
三链表
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
有点像火车的形状
1链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构；
1.1单向或者双向
1.2带头或者不带头
1.3循环或者非循环
但最常用的只有：
2实现
首先在传参数上：传的是指针还是指针的地址？
头节点head变量是指针变量，进行尾插时与顺序表一样：也是要传地址过去（因为需要涉及链表的修改，把尾节点的下一个链接上一个新节点）；如果不传地址，直接传指针的话会找不到新节点（形参的改变不影响实参（指针也是一样！））
2.1尾插与头插
void SLTPushBack(SLNode **phead, SLTDataType x)
{
SLNode *node = CreateNode(x);
if (*phead == NULL)
{
*phead = node;
}
else
{
SLNode *tail = *phead;
while (tail->_next != NULL)
{
tail = tail->_next;
}
tail->_next = node;
// 问题1.tail->next是链接不到node的;2.tail是局部变量，这样写会引发内存泄漏
// while(tail!=NULL)
// {
// tail=tail->_next;
// }
// tail=node;
}
}
void SLTPushFront(SLNode **pphead, SLTDataType x)
{
SLNode *node = CreateNode(x);
node->_next = *pphead;
*pphead = node;
}
2.2尾删与头删
void SLTPopBack(SLNode **pphead)
{
assert(*pphead);
// 1.一个节点
// 2.多个节点
if ((*pphead)->_next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
// 找尾
SLNode *prev = NULL;
SLNode *tail = *pphead;
while (tail->_next != NULL)
{
prev = tail;
tail = tail->_next;
}
free(tail);
prev->_next = NULL;
tail == NULL;
}
}
那如果是这样写呢？
void SLTPopBack(SLNode **pphead)
{
// 找尾
SLNode *prev = *pphead;//这里修改
SLNode *tail = *pphead;
while (tail->_next != NULL)
{
prev = tail;
tail = tail->_next;
}
free(tail);
prev->_next = NULL;
tail == NULL;
}
void SLTPopFront(SLNode **pphead)
{
assert(*pphead);
//一个节点/多个节点
SLNode *tmp = (*pphead)->_next;
free(*pphead);
*pphead = tmp;
} 
2.3pos前插入节点与删除pos位置
void SLTErase(SLNode **pphead, SLNode *pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if(*pphead==pos)
{
//头删
SLTPopFront(pphead);
}
else
{
SLNode *prev = *pphead;
while (prev->_next!= pos)
{
prev = prev->_next;
}
prev->_next=pos->_next;
free(pos);
pos=NULL;
}
}
void SLTErase(SLNode **pphead, SLNode *pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
if(*pphead==pos)
{
//头删
SLTPopFront(pphead);
}
else
{
SLNode *prev = *pphead;
while (prev->_next!= pos)
{
prev = prev->_next;
}
prev->_next=pos->_next;
free(pos);
pos=NULL;
}
}
还有两个相似的接口：在pos后插入节点和删除pos后的节点：没有头插与头删的情况比较简单
void SLTInsertAfter(SLNode **pphead, SLNode *pos, SLTDataType x)
{
assert(pphead);
assert(*pphead);
assert(pos);
SLNode* newnode=CreateNode(x);
newnode->_next=pos->_next;
pos->_next=newnode;
}
void SLTEraseAfter(SLNode **pphead, SLNode *pos)
{
assert(pphead);
assert(*pphead);
assert(pos);
SLNode* next=pos->_next;
pos->_next=pos->_next->_next;
free(next);
next=NULL;
}四相关练习题
链表的中间结点
struct ListNode *middleNode(struct ListNode *head)
{
struct ListNode *slow = head;
struct ListNode *fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}移除链表元素
思路一：
套用实现删除pos位置接口的思路，要分为两种情况：删除节点是不是头节点
struct ListNode *removeElements(struct ListNode *head, int val)
{
struct ListNode *cur = head;
struct ListNode *prev = NULL;
while (cur != NULL)
{
if (cur->val == val)
{
struct ListNode *next = cur->next;
if (cur == head)
head = next; // 头删
free(cur);
cur = next;
if (prev)
prev->next = next; // 不是头删的情况
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
思路2：
将不是删除的节点链接到新链表中，返回新链表的头节点
struct ListNode *removeElements(struct ListNode *head, int val)
{
if (head == NULL)
return NULL;
struct ListNode *ret = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *cur = head;
struct ListNode *tail = ret;
while (cur)
{
if (cur->val != val)
{
tail->next = cur;
tail = tail->next;
cur = cur->next;
}
else
{
struct ListNode *next = cur->next;
free(cur);
cur = next;
}
}
tail->next = NULL;
struct ListNode *ans = ret->next;
free(ret);
ret = NULL;
return ans;
}反转链表
思路1：创建新链表进行一次头插操作
思路2：定义三个指针prev,cur,next：修改链表箭头指向
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* ret = NULL;
while (head)
{
struct ListNode *next = head->next;
// 头插
head->next = ret;
ret = head;
head = next;
}
return ret;
}
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL)
return NULL;
struct ListNode *prev = NULL, *cur = head, *next = cur->next;
while (cur)
{
cur->next = prev;
prev = cur;
cur = next;
if (next)
next = next->next;
}
return prev;
}链表分割
思路：定义两个链表：一个储存小于x的节点，一个储存大于x的节点；最后合并两个链表（建议定义带哨兵位链表，不用额外去判断特殊情况（其中一个链表可能为空））
class Partition
{
public:
ListNode *partition(ListNode *pHead, int x)
{
ListNode *small = NULL, *tail1 = NULL;
ListNode *big = NULL, *tail2 = NULL;
while (pHead)
{
if (pHead->val < x)
{
if (small == NULL)
small = tail1 = pHead;
else
{
tail1->next = pHead;
tail1 = tail1->next;
}
}
else
{
if (big == NULL)
big = tail2 = pHead;
else
{
tail2->next = pHead;
tail2 = tail2->next;
}
}
pHead = pHead->next;
}
if (tail1 == NULL)
return big;
if (tail2 == NULL)
return small;
tail1->next = big;
tail2->next = NULL;
return small;
}
};合并两个有序链表
思路：两个链表从头开始比较，取小的尾插到新链表后往后走
struct ListNode *mergeTwoLists(struct ListNode *list1, struct ListNode *list2)
{
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
struct ListNode *list = NULL, *tail = NULL;
while (list1 && list2)
{
if (list1->val < list2->val)
{
if (list == NULL)
list = tail = list1;
else
{
tail->next = list1;
tail = list1;
}
list1 = list1->next;
}
else
{
if (list == NULL)
list = tail = list2;
else
{
tail->next = list2;
tail = list2;
}
list2 = list2->next;
}
}
if (list1)
tail->next = list1;
if (list2)
tail->next = list2;
return list;
}链表中倒数第k个结点
思路1：模拟
先遍历出有多少个节点cnt，再用cnt - k 得出需要走节点到达倒数第k个节点
（cnt - k <0 则直接返回NULL）
struct ListNode *FindKthToTail(struct ListNode *pListHead, int k)
{
struct ListNode *cur = pListHead;
int cnt = 0;
while (cur)
{
cnt++;
cur = cur->next;
}
cnt = cnt - k;
if (cnt < 0)
return NULL;
while (cnt--)
{
pListHead = pListHead->next;
}
return pListHead;
}思路2：快慢双指针
struct ListNode *FindKthToTail(struct ListNode *pListHead, int k)
{
struct ListNode *slow = pListHead, *fast = pListHead;
while (k--)
{
if (fast == NULL)
return NULL;
fast = fast->next;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}相交链表
思路1：
两层for循环来判断AB链表是否有节点是相等的
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
while (headA)
{
struct ListNode *head = headB;
while (head)
{
if (headA == head)
return head;
head = head->next;
}
headA = headA->next;
}
return NULL;
}思路2：双指针
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
struct ListNode *curA = headA, *curB = headB;
int lenA = 1, lenB = 1;
while (curA->next)
{
lenA++;
curA = curA->next;
}
while (curB->next)
{
lenB++;
curB = curB->next;
}
if (curA != curB)
return NULL; // 尾节点不同就一定不相交
struct ListNode *longNode = headA, *shortNode = headB;
if (lenA < lenB)
{
longNode = headB;
shortNode = headA;
}
int tmp = abs(lenA - lenB);
// 长的先走tmp步
while (tmp--)
{
longNode = longNode->next;
}
while (longNode != shortNode)
{
longNode = longNode->next;
shortNode = shortNode->next;
}
return longNode;
}环形链表
思路1：利用set容器储存节点地址，判断next是否在set容器中
class Solution
{
public:
bool hasCycle(ListNode *head)
{
unordered_set<ListNode *> hash;
while (head)
{
if (hash.count(head->next))
return true;
hash.insert(head);
head = head->next;
}
return false;
}
};思路2：快慢双指针
定义两个指针slow fast：slow走一步，fast走两步；如果相等就有环
bool hasCycle(struct ListNode *head)
{
struct ListNode *slow = head, *fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
总结：1如果N是偶数就追上了；
2如果N是奇数，C是奇数，要第二圈才能追上；
3如果N是奇数，C是偶数，就永远追不上；
第3个结论是否成立呢？
把X换成N的等式：
环形链表 II
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode *slow = head, *fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}链表的回文结构
思路：找到链表中间节点，将中间节点后半段的链表进行逆置后进行比较val
ListNode *GainMiddle(ListNode *A)
{
ListNode *slow = A, *fast = A;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
ListNode *Reverse(ListNode *A)
{
ListNode *head = NULL;
while (A)
{
ListNode *next = A->next;
A->next = head;
head = A;
A = next;
}
return head;
}
class PalindromeList
{
public:
bool chkPalindrome(ListNode *A)
{
ListNode *mid = GainMiddle(A);
ListNode *rhead = Reverse(mid);
while (rhead && A)
{
if (rhead->val != A->val)
return false;
rhead = rhead->next;
A = A->next;
}
return true;
}
};随机链表的复制
思路1（O(N) = N^2）
a先拷贝一个新链表；
b遍历一遍，找到原链表的节点->random指向节点的相对位置cnt；
c通过cnt再次遍历一遍，找到新链表的节点->random指向的节点
struct Node *copyRandomList(struct Node *head)
{
if (head == NULL)
return NULL;
struct Node *head1 = NULL, *tail = NULL;
struct Node *cur = head;
while (cur)
{
// 拷贝节点到新链表中
struct Node *copy = (struct Node *)malloc(sizeof(struct Node));
copy->val = cur->val;
if (head1 == NULL)
head1 = tail = copy;
else
{
tail->next = copy;
tail = tail->next;
}
cur = cur->next;
}
tail->next = NULL; // 新链表拷贝完成后结尾置NULL
cur = head;
struct Node *cur1 = head1;
while (cur)
{
if (cur->random == NULL)
cur1->random = NULL;
else
{
int cnt = 0;
struct Node *tmp = head;
while (cur->random != tmp)
{
cnt++;
tmp = tmp->next;
}
// 此时cnt是cur->random的相对位置,新链表对应的节点根据cnt找到random
tmp = head1;
while (cnt)
{
tmp = tmp->next;
cnt--;
}
cur1->random = tmp;
}
cur = cur->next;
cur1 = cur1->next;
}
return head1;
}思路2（O(N) = N）
a拷贝节点放到原节点后面；
b拷贝节点->random = 原节点->random->next；
c最后把拷贝节点连到新链表中
struct Node *copyRandomList(struct Node *head)
{
if (head == NULL)
return NULL;
struct Node *cur = head;
while (cur)
{
struct Node *copy = (struct Node *)malloc(sizeof(struct Node));
copy->val = cur->val;
// 插入在原节点的后面
copy->next = cur->next;
cur->next = copy;
cur = copy->next;
}
cur = head;
while (cur)
{
// 完成节点随机指向
struct Node *copy = cur->next;
if (cur->random == NULL)
{
copy->random = NULL;
}
else
copy->random = cur->random->next;
cur = copy->next;
}
struct Node *ret = NULL, *tail = NULL;
cur = head;
while (cur)
{
// 获取新链表
struct Node *copy = cur->next;
struct Node *next = copy->next;
if (ret == NULL)
ret = tail = copy;
else
{
tail->next = copy;
tail = tail->next;
}
cur->next = next;
cur = next;
}
return ret;
}五双链表
以上我们实现或者是在做题时用到的都是单链表（无哨兵位）：结构简单，但一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等；
而双链表(带头)：实践用的最多，一般用在单独存储数据；虽然结构较复杂，但实现出来后会发现它比单链表具有很多优势（如插入删除方便），实用性也比较强！
实现
//DList.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DListDateType;
typedef struct DListNode
{
DListDateType _val;
struct DListNode *_next;
struct DListNode *_prev;
} DList;
DList *CreateNode(DListDateType val);
DList *Init();
void Print(DList *head);
void DLPushBack(DList *head, DListDateType val);
void DLPushFront(DList *head, DListDateType val);
void DLPopBack(DList *head);
void DLPopFront(DList *head);
DList *DLFind(DList *head, DListDateType val);
void DLInsert(DList *pos, DListDateType val);
void DLErase(DList *pos);
void Destoty(DList *head);void DLPushBack(DList *head, DListDateType val)
{
assert(head);
DList *NewNode = CreateNode(val);
DList *tail = head->_prev;
tail->_next = NewNode;
NewNode->_prev = tail;
NewNode->_next = head;
head->_prev = NewNode;
}
void Print(DList *head)
{
assert(head);
DList *cur = head->_next;
printf("哨兵位<=>");
while (cur != head)
{
printf("%d<=>", cur->_val);
cur = cur->_next;
}
printf("哨兵位\n");
}
void DLPopBack(DList *head)
{
assert(head);
assert(head->_next != head); // 至少有节点删除
DList *tail = head->_prev;
DList *prev = tail->_prev;
prev->_next = head;
head->_prev = prev;
free(tail);
tail = NULL;
}
void DLPushFront(DList *head, DListDateType val)
{
assert(head);
DList *NewNode = CreateNode(val);
DList *first = head->_next;
NewNode->_next = first;
first->_prev = NewNode;
head->_next = NewNode;
NewNode->_prev = head;
}
void DLPopFront(DList *head)
{
assert(head);
assert(head->_next != head);
DList *first = head->_next;
DList *second = first->_next;
head->_next = second;
second->_prev = head;
free(first);
first = NULL;
}
void DLInsert(DList *pos, DListDateType val)
{
assert(pos);
DList *node = CreateNode(val);
DList *prev = pos->_prev;
prev->_next = node;
node->_prev = prev;
node->_next = pos;
pos->_prev = node;
}
void DLErase(DList *pos)
{
assert(pos);
DList *next = pos->_next;
DList *prev = pos->_prev;
prev->_next = next;
next->_prev = prev;
free(pos);
// pos=NULL;形参的改变不影响实参
}
其它接口
void Destory(DList *head)
{
assert(head);
DList *cur = head->_next;
while (cur != head)
{
DList *next = cur->_next;
free(cur);
cur = next;
}
free(cur);
// cur=NULL;
}
DList *DLFind(DList *head, DListDateType val)
{
assert(head);
DList *cur = head->_next;
while (cur != head)
{
if (cur->_val == val)
return cur;
cur = cur->_next;
}
return NULL;
}六总结
顺序表
问题：a.头部插入或者删除效率低：O(N) = N，需要挪动数据；
b.空间不够需要扩容，扩容有一定的消耗且有可能存在一定的浪费；
c.只适合尾插尾删；
优点：支持下标随机访问；
链表（双向）
问题：下标随机访问不方便：O(N) = N；
优点：a.插入与删除效率高：O(N) = 1，只需要改变指针指向；
b.按需申请释放，合理利用空间，不存在浪费
七其它知识
在学习计算机的基础知识时，我们知道：计算机进行运算靠的是CPU，而存储靠的是内存和磁盘，那为什么储存会有两个呢？
内存是带电储存，读写速度更快；而磁盘是不带电储存，读写速度较慢；这也就决定了两者根据场景来进行需要用那个来储存数据
CPU运行速度快，这也取决于在它附件的三个高速缓存和寄存器 先把数据加载进来：
CPU对数据的访问时，首先要从缓存里看下在不在？在的话就是命中，不在的话就是不命中；
由于顺序表储存是在一大段连续的空间中，CPU访问时，如果不在，它会一次加载一段数据到缓存中，那么接下来访问下一个时就是在缓存区中了，直接进行访问；
而链表逻辑上连续，而物理上是不连续的，CPU访问时某个节点时加载一段数据到缓存，后面的节点是大概率没被加载到缓存中的，所以下次访问下个节点时有需要进行加载，而缓存空间不大，这就造成缓存污染问题
以上便是全部内容，有问题欢迎在评论区指正，感谢观看！