目录

前言：

1、带头+双向+循环链表的实现

1.1、malloc结点

1.2、链表初始化ListNode* ListInit();

1.3、链表的打印void ListPrint(ListNode* phead);

1.4、链表尾插

void ListPushBack(ListNode* phead, LTDataType x)

1.5、链表头插

void ListPushFront(ListNode* phead, LTDataType x);

1.6、链表尾删

void ListPopBack(ListNode* plist);

1.7、双向链表头删void ListPopFront(ListNode* phead);

1.8、双向链表查找ListNode* ListFind(ListNode* phead, LTDataType x);

1.9、双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x);

1.10、双向链表删除pos位置的结点void ListErase(ListNode* pos);

1.11、求链表的长度int ListSize(ListNode* phead);

1.12、双向链表的销毁void ListDestory(ListNode* phead);

2、oj题目

3、顺序表和链表的区别

前言：

可知链表的结构非常多样，以下情况组合起来就有八种链表结构：

1.单向带头循环链表

2.单向带头不循环链表

3.单向不带头循环链表

4单向不带头不循环链表

5.双向带头循环链表

6.双向带头不循环链表

7.双向不带头循环链表

8.双向不带头不循环链表

 双向带头循环链表：结构复杂、操作简单，为最优链表

1、带头+双向+循环链表的实现

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}listNode;

1.1、malloc结点

ListNode* BuyListNode(LTDataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc fail");exit(-1);}node->data = x;node->next = NULL;node->prev = NULL;return node;
}

1.2、链表初始化
ListNode* ListInit();

初始化哨兵位的头结点

ListNode* ListInit()
{ListNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

1.3、链表的打印
void ListPrint(ListNode* phead);

void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;if (cur == phead){printf("NULL\n");}while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

1.4、链表尾插

void ListPushBack(ListNode* phead, LTDataType x)

不需要传二级指针，因为我们不需要改变哨兵位的头
//而是改变头指针指向里面的结构

void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

1.5、链表头插

void ListPushFront(ListNode* phead, LTDataType x);

void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = cur;cur->prev = newnode;
}

1.6、链表尾删

void ListPopBack(ListNode* plist);

// 双向链表尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* tail = phead->prev;tail->prev->next = phead;phead->prev = tail->prev;free(tail);
}

1.7、双向链表头删
void ListPopFront(ListNode* phead);

void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead);ListNode* del = phead->next;phead->next = phead->next->next;phead->next->prev = phead;free(del);del = NULL;
}

1.8、双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);

ListNode* ListFind(ListNode* phead, LTDataType x)
{ListNode* cur = phead->next;if (phead->next == NULL){return NULL;}while (phead->next->data != x){phead = phead->next;if (phead->next == cur){return NULL;}}return phead->next;return NULL;
}

1.9、双向链表在pos的前面进行插入

void ListInsert(ListNode* pos, LTDataType x);

void ListInsert(ListNode* pos, LTDataType x)
{ListNode* newnode = BuyListNode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}

头插可以直接复用，ListInsert( phead -> next, x )

尾插也可以复用，因为是循环，哨兵位前一个便是尾，所以再哨兵位之前插入就可以

ListInsert( phead , x )

1.10、双向链表删除pos位置的结点
void ListErase(ListNode* pos);

void ListErase(ListNode* pos)
{pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);
}

头删可以直接服用，ListErase( phead -> next )

尾删,ListErase( phead -> prev )

1.11、求链表的长度
int ListSize(ListNode* phead);

int ListSize(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;int size = 0;while (cur != phead){++size;cur = cur->next;}return size;
}

1.12、双向链表的销毁
void ListDestory(ListNode* phead);

void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;int size = 0;while (cur != phead){ListNode* next = cur->next;ListErase(cur);cur = next;}free(phead);
}

2、oj题目

给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点 或空结点。 要求返回这个链表的深度拷贝。

Loading Question... - 力扣（LeetCode）https://leetcode.cn/problems/copy-list-with-random-pointer/description/

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。 

深拷贝应该正好由 n 个 全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。

每个节点用一个 [val,random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
你的代码 只接受原链表的头节点 head 作为传入参数。

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;//1.链接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;}//控制randomcur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random ->next;}cur = copy->next;}cur = head;struct Node* copyHead = NULL,*copyTail = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(copyTail == NULL){copyHead = copyTail = copy;}else{copyTail->next = copy;copyTail = copyTail->next;}cur->next = next;cur = next;}return copyHead;
}

3、顺序表和链表的区别

   不同点                                 顺序表                                                                链表

存储空间上                       物理上一定连续                                  逻辑上连续，但物理上不一定 连续

随机访问                              支持：O(1)                                                       不支持：O(N)           

任意位置插入

            |                   可能需要搬移元素，效率低 O(N)                               只需修改指针指向

或者删除元素 

插入                         动态顺序表，空间不够时需要 扩容                             没有容量的概念

应用场景                        元素高效存储+频繁访问                                    任意位置插入和删除频繁

缓存利用率                                      高                                                                      低 

备注：缓存利用率参考存储体系结构 以及 局部原理性。

 与程序员相关的CPU缓存知识 | 酷 壳 - CoolShellhttps://coolshell.cn/articles/20793.html