线性表之链表

链表

链表是线性表的一种，是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

#mermaid-svg-7I2jSZAppPjtwoWG .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-7I2jSZAppPjtwoWG .label text{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .node rect,#mermaid-svg-7I2jSZAppPjtwoWG .node circle,#mermaid-svg-7I2jSZAppPjtwoWG .node ellipse,#mermaid-svg-7I2jSZAppPjtwoWG .node polygon,#mermaid-svg-7I2jSZAppPjtwoWG .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-7I2jSZAppPjtwoWG .node .label{text-align:center;fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .node.clickable{cursor:pointer}#mermaid-svg-7I2jSZAppPjtwoWG .arrowheadPath{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-7I2jSZAppPjtwoWG .flowchart-link{stroke:#333;fill:none}#mermaid-svg-7I2jSZAppPjtwoWG .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-7I2jSZAppPjtwoWG .edgeLabel rect{opacity:0.9}#mermaid-svg-7I2jSZAppPjtwoWG .edgeLabel span{color:#333}#mermaid-svg-7I2jSZAppPjtwoWG .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-7I2jSZAppPjtwoWG .cluster text{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-7I2jSZAppPjtwoWG .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-7I2jSZAppPjtwoWG text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-7I2jSZAppPjtwoWG .actor-line{stroke:grey}#mermaid-svg-7I2jSZAppPjtwoWG .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-7I2jSZAppPjtwoWG .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-7I2jSZAppPjtwoWG #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-7I2jSZAppPjtwoWG .sequenceNumber{fill:#fff}#mermaid-svg-7I2jSZAppPjtwoWG #sequencenumber{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG #crosshead path{fill:#333;stroke:#333}#mermaid-svg-7I2jSZAppPjtwoWG .messageText{fill:#333;stroke:#333}#mermaid-svg-7I2jSZAppPjtwoWG .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-7I2jSZAppPjtwoWG .labelText,#mermaid-svg-7I2jSZAppPjtwoWG .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-7I2jSZAppPjtwoWG .loopText,#mermaid-svg-7I2jSZAppPjtwoWG .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-7I2jSZAppPjtwoWG .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-7I2jSZAppPjtwoWG .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-7I2jSZAppPjtwoWG .noteText,#mermaid-svg-7I2jSZAppPjtwoWG .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-7I2jSZAppPjtwoWG .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-7I2jSZAppPjtwoWG .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-7I2jSZAppPjtwoWG .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-7I2jSZAppPjtwoWG .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG .section{stroke:none;opacity:0.2}#mermaid-svg-7I2jSZAppPjtwoWG .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-7I2jSZAppPjtwoWG .section2{fill:#fff400}#mermaid-svg-7I2jSZAppPjtwoWG .section1,#mermaid-svg-7I2jSZAppPjtwoWG .section3{fill:#fff;opacity:0.2}#mermaid-svg-7I2jSZAppPjtwoWG .sectionTitle0{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .sectionTitle1{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .sectionTitle2{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .sectionTitle3{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-7I2jSZAppPjtwoWG .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG .grid path{stroke-width:0}#mermaid-svg-7I2jSZAppPjtwoWG .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-7I2jSZAppPjtwoWG .task{stroke-width:2}#mermaid-svg-7I2jSZAppPjtwoWG .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG .taskText:not([font-size]){font-size:11px}#mermaid-svg-7I2jSZAppPjtwoWG .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-7I2jSZAppPjtwoWG .task.clickable{cursor:pointer}#mermaid-svg-7I2jSZAppPjtwoWG .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-7I2jSZAppPjtwoWG .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-7I2jSZAppPjtwoWG .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-7I2jSZAppPjtwoWG .taskText0,#mermaid-svg-7I2jSZAppPjtwoWG .taskText1,#mermaid-svg-7I2jSZAppPjtwoWG .taskText2,#mermaid-svg-7I2jSZAppPjtwoWG .taskText3{fill:#fff}#mermaid-svg-7I2jSZAppPjtwoWG .task0,#mermaid-svg-7I2jSZAppPjtwoWG .task1,#mermaid-svg-7I2jSZAppPjtwoWG .task2,#mermaid-svg-7I2jSZAppPjtwoWG .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-7I2jSZAppPjtwoWG .taskTextOutside0,#mermaid-svg-7I2jSZAppPjtwoWG .taskTextOutside2{fill:#000}#mermaid-svg-7I2jSZAppPjtwoWG .taskTextOutside1,#mermaid-svg-7I2jSZAppPjtwoWG .taskTextOutside3{fill:#000}#mermaid-svg-7I2jSZAppPjtwoWG .active0,#mermaid-svg-7I2jSZAppPjtwoWG .active1,#mermaid-svg-7I2jSZAppPjtwoWG .active2,#mermaid-svg-7I2jSZAppPjtwoWG .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-7I2jSZAppPjtwoWG .activeText0,#mermaid-svg-7I2jSZAppPjtwoWG .activeText1,#mermaid-svg-7I2jSZAppPjtwoWG .activeText2,#mermaid-svg-7I2jSZAppPjtwoWG .activeText3{fill:#000 !important}#mermaid-svg-7I2jSZAppPjtwoWG .done0,#mermaid-svg-7I2jSZAppPjtwoWG .done1,#mermaid-svg-7I2jSZAppPjtwoWG .done2,#mermaid-svg-7I2jSZAppPjtwoWG .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-7I2jSZAppPjtwoWG .doneText0,#mermaid-svg-7I2jSZAppPjtwoWG .doneText1,#mermaid-svg-7I2jSZAppPjtwoWG .doneText2,#mermaid-svg-7I2jSZAppPjtwoWG .doneText3{fill:#000 !important}#mermaid-svg-7I2jSZAppPjtwoWG .crit0,#mermaid-svg-7I2jSZAppPjtwoWG .crit1,#mermaid-svg-7I2jSZAppPjtwoWG .crit2,#mermaid-svg-7I2jSZAppPjtwoWG .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-7I2jSZAppPjtwoWG .activeCrit0,#mermaid-svg-7I2jSZAppPjtwoWG .activeCrit1,#mermaid-svg-7I2jSZAppPjtwoWG .activeCrit2,#mermaid-svg-7I2jSZAppPjtwoWG .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-7I2jSZAppPjtwoWG .doneCrit0,#mermaid-svg-7I2jSZAppPjtwoWG .doneCrit1,#mermaid-svg-7I2jSZAppPjtwoWG .doneCrit2,#mermaid-svg-7I2jSZAppPjtwoWG .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-7I2jSZAppPjtwoWG .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-7I2jSZAppPjtwoWG .milestoneText{font-style:italic}#mermaid-svg-7I2jSZAppPjtwoWG .doneCritText0,#mermaid-svg-7I2jSZAppPjtwoWG .doneCritText1,#mermaid-svg-7I2jSZAppPjtwoWG .doneCritText2,#mermaid-svg-7I2jSZAppPjtwoWG .doneCritText3{fill:#000 !important}#mermaid-svg-7I2jSZAppPjtwoWG .activeCritText0,#mermaid-svg-7I2jSZAppPjtwoWG .activeCritText1,#mermaid-svg-7I2jSZAppPjtwoWG .activeCritText2,#mermaid-svg-7I2jSZAppPjtwoWG .activeCritText3{fill:#000 !important}#mermaid-svg-7I2jSZAppPjtwoWG .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-7I2jSZAppPjtwoWG g.classGroup text .title{font-weight:bolder}#mermaid-svg-7I2jSZAppPjtwoWG g.clickable{cursor:pointer}#mermaid-svg-7I2jSZAppPjtwoWG g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-7I2jSZAppPjtwoWG g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-7I2jSZAppPjtwoWG .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-7I2jSZAppPjtwoWG .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-7I2jSZAppPjtwoWG .dashed-line{stroke-dasharray:3}#mermaid-svg-7I2jSZAppPjtwoWG #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG .commit-id,#mermaid-svg-7I2jSZAppPjtwoWG .commit-msg,#mermaid-svg-7I2jSZAppPjtwoWG .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-7I2jSZAppPjtwoWG g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-7I2jSZAppPjtwoWG g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-7I2jSZAppPjtwoWG g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-7I2jSZAppPjtwoWG .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-7I2jSZAppPjtwoWG .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-7I2jSZAppPjtwoWG .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-7I2jSZAppPjtwoWG .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-7I2jSZAppPjtwoWG .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-7I2jSZAppPjtwoWG .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-7I2jSZAppPjtwoWG .edgeLabel text{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-7I2jSZAppPjtwoWG .node circle.state-start{fill:black;stroke:black}#mermaid-svg-7I2jSZAppPjtwoWG .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-7I2jSZAppPjtwoWG #statediagram-barbEnd{fill:#9370db}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-state .divider{stroke:#9370db}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-7I2jSZAppPjtwoWG .note-edge{stroke-dasharray:5}#mermaid-svg-7I2jSZAppPjtwoWG .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-7I2jSZAppPjtwoWG .error-icon{fill:#522}#mermaid-svg-7I2jSZAppPjtwoWG .error-text{fill:#522;stroke:#522}#mermaid-svg-7I2jSZAppPjtwoWG .edge-thickness-normal{stroke-width:2px}#mermaid-svg-7I2jSZAppPjtwoWG .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-7I2jSZAppPjtwoWG .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-7I2jSZAppPjtwoWG .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-7I2jSZAppPjtwoWG .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-7I2jSZAppPjtwoWG .marker{fill:#333}#mermaid-svg-7I2jSZAppPjtwoWG .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-7I2jSZAppPjtwoWG { color: rgba(0, 0, 0, 0.75); font: ; } 链表 单向链表 双向链表 循环链表

链表常见操作有：

函数功能insert(node,index)将node插入到链表中下标为index的位置output()输出整个链表delete_node(index)将链表下标为index的元素删除reverse()翻转整个链表

单向链表

在第一个结点(有效元素)之前附设一个结点，称之为头结点；指向头结点的指针，称之为头指针。 对单链表的存取必须从头指针开始进行，由于单链表的最后一个元素没有直接后继，则指针为NULL。 对于头结点，数据域可以不存储任何信息，也可存储如链表长度等附加信息。 小结：

无论链表是否为空，头指针均不为空。头指针是链表的必要条件；链表可以没有结点，但不能没有头指针，头指针是链表的必要条。 //定义结点的结构体 typedef struct Node{ int data; struct Node *next; }Node, *LinkList;

则定义LinkList L;时，L为链表的头指针。

L=(LinkList)malloc(sizeof(Node)); //创建一个结点

此处返回给L的是一个指针，并且赋给了头指针。

L->next=null; //这里说明我创建了一个头结点，即同时运用了头指针和头结点。

示例如下：

#include <stdio.h> #include <stdlib.h> typedef struct Node{ int data; struct Node *next; }Node, *LinkedList; LinkedList insert(LinkedList head, Node *node, int index) { if (head == NULL) { if (index != 0) { printf("failed\n"); return head; } head = node; printf("success\n"); return head; } if (index == 0) { node->next = head; head = node; printf("success\n"); return head; } Node *current_node = head; int count = 0; while (current_node->next != NULL && count < index - 1) { current_node = current_node->next; count++; } if (count == index - 1) { node->next = current_node->next; current_node->next = node; printf("success\n"); return head; } printf("failed\n"); return head; } void output(LinkedList head) { if (head == NULL) { return; } Node *current_node = head; while (current_node != NULL) { printf("%d ", current_node->data); current_node = current_node->next; } printf("\n"); } LinkedList delete_node(LinkedList head, int index) { if (head == NULL) { printf("failed\n"); return head; } Node *current_node = head; int count = 0; if (index == 0) { head = current_node -> next; free(current_node); printf("success\n"); return head; } while (current_node -> next != NULL && count < index - 1) { current_node = current_node -> next; count++; } if (count == index - 1 && current_node -> next != NULL) { Node *delete_node = current_node -> next; current_node -> next = delete_node -> next; free(delete_node); printf("success\n"); return head; } printf("failed\n"); return head; } LinkedList reverse(LinkedList head) { if (head == NULL) { return head; } Node *current_node, *next_node; current_node = head -> next; head -> next = NULL; while (current_node != NULL) { next_node = current_node -> next; current_node -> next = head; head = current_node; current_node = next_node; } return head; } void clear(LinkedList head) { Node *current_node = head; while (current_node != NULL) { Node *delete_node = current_node; current_node = current_node->next; free(delete_node); } } int main() { LinkedList linkedlist = NULL; int count, caseNum, a, b; int i = 0; scanf("%d", &count); while (i++ < count) { scanf("%d", &caseNum); switch (caseNum) { case 1 : scanf("%d %d", &a, &b); Node *node = (Node *)malloc(sizeof(Node)); node -> data = b; node -> next = NULL; linkedlist = insert(linkedlist, node, a); break; case 2 : output(linkedlist); break; case 3 : scanf("%d", &a); linkedlist = delete_node(linkedlist, a); break; case 4 : linkedlist = reverse(linkedlist); break; } } return 0; }

循环链表

循环链表与单链表不同的是，其将最后一个结点的指针指向了头结点，这样的结构使得链表更加灵活方便。 循环链表里没有空指针，故判断结束条件时，不再判断指针是否为空，而是判断指针是否等于某固定指针。 约瑟夫环

#include <stdio.h> #include <stdlib.h> typedef struct Node{ int data; struct Node *next; }Node, *LinkedList; LinkedList insert(LinkedList head, Node *node, int index) { if (head == NULL) { if (index != 0) { return head; } head = node; head->next = head; return head; } if (index == 0) { node->next = head->next; head->next = node; return head; } Node *current_node = head->next; int count = 0; while (current_node != head && count < index - 1) { current_node = current_node->next; count++; } if (count == index - 1) { node->next = current_node->next; current_node->next = node; } if (node == head->next) { head = node; } return head; } // 删除结点并输出 output_josephus void output_josephus(LinkedList head, int m) { Node *current_node = head; head = NULL; while (current_node -> next != current_node) {//判断其是否是最后一个人 for (int i = 1; i < m; ++i) { current_node = current_node -> next; } printf("%d ", current_node -> next -> data); Node *delete_node = current_node -> next; current_node -> next = current_node -> next -> next; free(delete_node); } printf("%d\n", current_node -> data); free(current_node); } int main() { LinkedList linkedlist = NULL; int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { Node *node = (Node *)malloc(sizeof(Node)); node->data = i; node->next = NULL; linkedlist = insert(linkedlist, node, i - 1); } output_josephus(linkedlist, m); return 0; }

双向链表

双向链表又叫双链表，相对于单链表，双链表的指针域有两个指针，分别指向前驱结点和后继结点。有了这样的结构，则可以从头结点遍历到尾结点，也可以从尾结点遍历到头结点。