• 用C++和Java实现带头节点的双向循环链表，要继承linearList类，并实现它的所有功能，另外，必须实现双向迭代器。 实现带头节点的双向循环链表，要具有以下的功能： 判断表是否空，如果空则返回true，不空返回...
• 无头单向非循环链表的实现 常见的单链表面试题 DLinkList.h #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int DLDataType; typedef struct ListNode { ...
无头单向非循环链表的实现 常见的单链表面试题 DLinkList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int DLDataType;
typedef struct ListNode {
DLDataType data;
struct ListNode *prev;
struct ListNode *next;
}ListNode;

typedef struct List {
}List;

void ListInit(List *plist);
void ListDestory(List *plist);
void ListPrint(List *plist);

void ListPushBack(List *plist, DLDataType data);
void ListPopBack(List *plist);
void ListPushFront(List *plist, DLDataType data);
void ListPopFront(List *plist);

ListNode* ListFind(List *plist, DLDataType data);
void ListInsert(ListNode* pos, DLDataType data);//在指定位置前插入元素
void ListErase(ListNode* pos);

#include"DLinkList.h"

void ListInit(List *plist)
{
assert(plist);
}

{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}

void ListDestory(List *plist)
{
assert(plist);
{
ListNode* next = cur->next;
free(cur);
cur = next;
}

}

void ListPrint(List *plist)
{
assert(plist);
{
printf("%d <=> ", cur->data);
cur = cur->next;
}
printf("NULL\n");
}

void ListPushBack(List *plist, DLDataType data)
{
assert(plist);

tail->next = node;
node->next = cur;
node->prev = tail;
cur->prev = node;
}

void ListPopBack(List *plist)
{
assert(plist);
ListNode* tail = cur->prev;
ListNode* prev = tail->prev;

cur->prev = prev;
prev->next = cur;
free(tail);
}

void ListPushFront(List* plist, DLDataType data)
{
assert(plist);
ListNode* next = cur->next;

cur->next = node;
next->prev = node;
node->next = next;
node->prev = cur;
}

void ListPopFront(List* plist)
{
assert(plist);
ListNode* cur = prev->next;
ListNode* next = cur->next;

//链表中只有头节点时，不做处理
if (prev == cur)
return;

prev->next = next;
next->prev = prev;
free(cur);
cur = NULL;
}

ListNode* ListFind(List *plist, DLDataType data)
{
assert(plist);

{
if (cur->data == data)
return cur;
else
cur = cur->next;
}
return NULL;
}

void ListInsert(ListNode* pos, DLDataType data)
{
assert(pos);
ListNode* prev = pos->prev;

prev->next = node;
node->next = pos;
node->prev = prev;
pos->prev = node;
}

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

prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}

展开全文
• 带头节点 (非头指针) 双向循环链表 (doubly linked list) bidirectional circular linked list：双向循环链表 建议使用带头结点，而非头指针双向循环链表。 1. 双向链表 双向链表的每个数据结点中都有两个指针，...


带头节点 (非头指针) 双向循环链表 (doubly linked list)

建议使用带头结点，而非头指针的双向循环链表。
1. 双向链表
双向链表的每个数据结点中都有两个指针，分别指向直接后继 (next) 和直接前驱 (prev) 。

2. 双向循环链表
本节图片参考 https://www.cnblogs.com/skywang12345/p/3561803.html
双向链表和单链表都是由节点组成，双向链表的每个数据结点中都有两个指针，分别指向直接后继 (next) 和直接前驱 (prev) 。
双向循环链表最后一个结点的直接后继 (next) 指向表头 (head) 结点，而不像双向链表置为 NULL。
在判断是否到达表尾时，判断该结点直接后继 (next) 是否是表头结点，当直接后继 (next) 等于表头指针时，说明已到表尾。而不像双向链表那样判断直接后继 (next) 是否为 NULL。
从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

头节点 (非头指针) 双向循环链表示例图

表头 head 为空，head 的后继节点 (next) 为节点 10 (数据为 10 的节点)；节点 10 的后继节点 (next) 是节点 20 (数据为 20 的节点)，节点 20 的前继节点 (prev) 是节点 10；节点 20 的后继节点 (next) 是节点 30，节点 30 的前继节点 (prev) 是节点 20；…；末尾节点的后继节点 (next) 是表头 head。
2.1 头节点 (非头指针) 双向循环链表删除节点

头节点 (非头指针) 双向循环链表删除节点示例图

删除节点 30 (数据为 30 的节点) 删除之前：节点 20 的后继节点 (next) 为节点 30，节点 30 的前继节点 (prev) 为节点 20。节点 30 的后继节点 (next) 为节点 40，节点 40 的前继节点 (prev) 为节点 30。 删除之后：节点 20 的后继节点 (next) 为节点 40，节点 40 的前继节点 (prev) 为节点 20。
2.2 头节点 (非头指针) 双向循环链添加节点

头节点 (非头指针) 双向循环链表添加节点示例图

在节点 10 与 节点 20 之间添加节点 15 添加之前：节点 10 的后继节点 (next) 为节点 20，节点 20 的前继节点 (prev) 为节点 10。 添加之后：节点 10 的后继节点 (next) 为节点 15，节点 15 的前继节点 (prev) 为节点 10。节点 15 的后继节点 (next) 为节点 20，节点 20 的前继节点 (prev) 为节点 15。

3. 带头节点 (非头指针) 双向循环链表 (doubly linked list)

3.1 insert_first - delete_node - display
//============================================================================
// Name        : doubly linked list
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Description : Hello World in C++, Ansi-style
//============================================================================

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#define MAX_NODE_LEN 401
#define NULL 0

#include <stdio.h>

typedef struct NODE {
int data;
struct NODE *prev;
struct NODE *next;
} Node;

Node node_array[MAX_NODE_LEN];
int node_array_idx = 0;

{

node->next->prev = node;
}

void delete_node(const Node *node)
{
Node *prev_node = node->prev;
Node *next_node = node->next;
// current node - node

prev_node->next = next_node;
next_node->prev = prev_node;
}

void delete_node_v1(const Node *node)
{
// current node - node

node->prev->next = node->next;
node->next->prev = node->prev;
}

void delete_node_v2(Node *node)
{
// current node - node

node->prev->next = node->next;
node->next->prev = node->prev;

node->next = node->next = NULL;
}

{
int n = 1;

{
printf("node %d: %d\n", n, node->data);
++n;
node = node->next;
}
}

int main()
{
// 头节点 (非头指针)
Node root;

// initialization
// root.prev = &(root);
// root.next = &(root);
root.prev = root.next = &(root);
root.data = 0;

for (int i = 0; i < MAX_NODE_LEN; ++i)
{
node_array[i].prev = NULL;
node_array[i].next = NULL;
node_array[i].data = 0;
}

// insert 0
node_array[0].data = 0;
insert_first(&root, &(node_array[0]));

// insert 2
node_array[2].data = 2;
insert_first(&root, &(node_array[2]));

// insert 4
node_array[4].data = 4;
insert_first(&root, &(node_array[4]));

// insert 6
node_array[6].data = 6;
insert_first(&root, &(node_array[6]));

// insert 8
node_array[8].data = 8;
insert_first(&root, &(node_array[8]));

display(&root);

// delete 4
delete_node_v1(&(node_array[4]));
printf("\ndelete data %d\n", 4);
display(&root);

// delete 0
delete_node_v1(&(node_array[0]));
printf("\ndelete data %d\n", 0);
display(&root);

// delete 8
delete_node_v1(&(node_array[8]));
printf("\ndelete data %d\n", 8);
display(&root);

// insert 10
node_array[10].data = 10;
insert_first(&root, &(node_array[10]));
printf("\ninsert data %d\n", 10);
display(&root);

/********************************* traverse function *********************************/
{
Node *tmp_node;
{
tmp_node = ptr_node->next;
if (2 == ptr_node->data) {
delete_node(ptr_node);
}

ptr_node = tmp_node;
}
}
/********************************* traverse function *********************************/

printf("\ndelete data %d\n", 2);
display(&root);

// insert 12
node_array[12].data = 12;
insert_first(&root, &(node_array[12]));
printf("\ninsert data %d\n", 12);
display(&root);

/********************************* traverse function *********************************/
{
Node *tmp_node;
{
tmp_node = ptr_node->prev;
if (10 == ptr_node->data) {
delete_node(ptr_node);
}

ptr_node = tmp_node;
}
}
/********************************* traverse function *********************************/

printf("\ndelete data %d\n", 10);
display(&root);

return 0;
}


node 1: 8
node 2: 6
node 3: 4
node 4: 2
node 5: 0

delete data 4
node 1: 8
node 2: 6
node 3: 2
node 4: 0

delete data 0
node 1: 8
node 2: 6
node 3: 2

delete data 8
node 1: 6
node 2: 2

insert data 10
node 1: 10
node 2: 6
node 3: 2

delete data 2
node 1: 10
node 2: 6

insert data 12
node 1: 12
node 2: 10
node 3: 6

delete data 10
node 1: 12
node 2: 6
请按任意键继续. . .

3.2 insert_first - delete_node_v1 - display
//============================================================================
// Name        : doubly linked list
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Description : Hello World in C++, Ansi-style
//============================================================================

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#define MAX_NODE_LEN 401
#define NULL 0

#include <stdio.h>

typedef struct NODE {
int data;
struct NODE *prev;
struct NODE *next;
} Node;

Node node_array[MAX_NODE_LEN];
int node_array_idx = 0;

{

node->next->prev = node;
}

void delete_node(const Node *node)
{
Node *prev_node = node->prev;
Node *next_node = node->next;
// current node - node

prev_node->next = next_node;
next_node->prev = prev_node;
}

void delete_node_v1(const Node *node)
{
// current node - node

node->prev->next = node->next;
node->next->prev = node->prev;
}

void delete_node_v2(Node *node)
{
// current node - node

node->prev->next = node->next;
node->next->prev = node->prev;

node->next = node->next = NULL;
}

{
int n = 1;

{
printf("node %d: %d\n", n, node->data);
++n;
node = node->next;
}
}

int main()
{
// 头节点 (非头指针)
Node root;

// initialization
// root.prev = &(root);
// root.next = &(root);
root.prev = root.next = &(root);
root.data = 0;

for (int i = 0; i < MAX_NODE_LEN; ++i)
{
node_array[i].prev = NULL;
node_array[i].next = NULL;
node_array[i].data = 0;
}

// insert 0
node_array[0].data = 0;
insert_first(&root, &(node_array[0]));

// insert 2
node_array[2].data = 2;
insert_first(&root, &(node_array[2]));

// insert 4
node_array[4].data = 4;
insert_first(&root, &(node_array[4]));

// insert 6
node_array[6].data = 6;
insert_first(&root, &(node_array[6]));

// insert 8
node_array[8].data = 8;
insert_first(&root, &(node_array[8]));

display(&root);

// delete 4
delete_node_v1(&(node_array[4]));
printf("\ndelete data %d\n", 4);
display(&root);

// delete 0
delete_node_v1(&(node_array[0]));
printf("\ndelete data %d\n", 0);
display(&root);

// delete 8
delete_node_v1(&(node_array[8]));
printf("\ndelete data %d\n", 8);
display(&root);

// insert 10
node_array[10].data = 10;
insert_first(&root, &(node_array[10]));
printf("\ninsert data %d\n", 10);
display(&root);

/********************************* traverse function *********************************/
{
Node *tmp_node;
{
tmp_node = ptr_node->next;
if (2 == ptr_node->data) {
delete_node_v1(ptr_node);
}

ptr_node = tmp_node;
}
}
/********************************* traverse function *********************************/

printf("\ndelete data %d\n", 2);
display(&root);

// insert 12
node_array[12].data = 12;
insert_first(&root, &(node_array[12]));
printf("\ninsert data %d\n", 12);
display(&root);

/********************************* traverse function *********************************/
{
Node *tmp_node;
{
tmp_node = ptr_node->prev;
if (10 == ptr_node->data) {
delete_node_v1(ptr_node);
}

ptr_node = tmp_node;
}
}
/********************************* traverse function *********************************/

printf("\ndelete data %d\n", 10);
display(&root);

return 0;
}


node 1: 8
node 2: 6
node 3: 4
node 4: 2
node 5: 0

delete data 4
node 1: 8
node 2: 6
node 3: 2
node 4: 0

delete data 0
node 1: 8
node 2: 6
node 3: 2

delete data 8
node 1: 6
node 2: 2

insert data 10
node 1: 10
node 2: 6
node 3: 2

delete data 2
node 1: 10
node 2: 6

insert data 12
node 1: 12
node 2: 10
node 3: 6

delete data 10
node 1: 12
node 2: 6
请按任意键继续. . .

3.3 insert_first - delete_node_v1 - display_v1
//============================================================================
// Name        : doubly linked list
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Description : Hello World in C++, Ansi-style
//============================================================================

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#define MAX_NODE_LEN 401
#define NULL 0

#include <stdio.h>

typedef struct NODE {
int data;
struct NODE *prev;
struct NODE *next;
} Node;

Node node_array[MAX_NODE_LEN];
int node_array_idx = 0;

{

node->next->prev = node;
}

void delete_node(const Node *node)
{
Node *prev_node = node->prev;
Node *next_node = node->next;
// current node - node

prev_node->next = next_node;
next_node->prev = prev_node;
}

void delete_node_v1(const Node *node)
{
// current node - node

node->prev->next = node->next;
node->next->prev = node->prev;
}

void delete_node_v2(Node *node)
{
// current node - node

node->prev->next = node->next;
node->next->prev = node->prev;

node->next = node->next = NULL;
}

{
int n = 1;

{
printf("node %d: %d\n", n, node->data);
++n;
node = node->next;
}
}

{
int n = 1;

{
printf("node %d: %d\n", n, node->data);
++n;
node = node->prev;
}
}

int main()
{
// 头节点 (非头指针)
Node root;

// initialization
// root.prev = &(root);
// root.next = &(root);
root.prev = root.next = &(root);
root.data = 0;

for (int i = 0; i < MAX_NODE_LEN; ++i)
{
node_array[i].prev = NULL;
node_array[i].next = NULL;
node_array[i].data = 0;
}

// insert 0
node_array[0].data = 0;
insert_first(&root, &(node_array[0]));

// insert 2
node_array[2].data = 2;
insert_first(&root, &(node_array[2]));

// insert 4
node_array[4].data = 4;
insert_first(&root, &(node_array[4]));

// insert 6
node_array[6].data = 6;
insert_first(&root, &(node_array[6]));

// insert 8
node_array[8].data = 8;
insert_first(&root, &(node_array[8]));

display_v1(&root);

// delete 4
delete_node_v1(&(node_array[4]));
printf("\ndelete data %d\n", 4);
display_v1(&root);

// delete 0
delete_node_v1(&(node_array[0]));
printf("\ndelete data %d\n", 0);
display_v1(&root);

// delete 8
delete_node_v1(&(node_array[8]));
printf("\ndelete data %d\n", 8);
display_v1(&root);

// insert 10
node_array[10].data = 10;
insert_first(&root, &(node_array[10]));
printf("\ninsert data %d\n", 10);
display_v1(&root);

/********************************* traverse function *********************************/
{
Node *tmp_node;
{
tmp_node = ptr_node->next;
if (2 == ptr_node->data) {
delete_node_v1(ptr_node);
}

ptr_node = tmp_node;
}
}
/********************************* traverse function *********************************/

printf("\ndelete data %d\n", 2);
display_v1(&root);

// insert 12
node_array[12].data = 12;
insert_first(&root, &(node_array[12]));
printf("\ninsert data %d\n", 12);
display_v1(&root);

/********************************* traverse function *********************************/
{
Node *tmp_node;
{
tmp_node = ptr_node->prev;
if (10 == ptr_node->data) {
delete_node_v1(ptr_node);
}

ptr_node = tmp_node;
}
}
/********************************* traverse function *********************************/

printf("\ndelete data %d\n", 10);
display_v1(&root);

return 0;
}


node 1: 0
node 2: 2
node 3: 4
node 4: 6
node 5: 8

delete data 4
node 1: 0
node 2: 2
node 3: 6
node 4: 8

delete data 0
node 1: 2
node 2: 6
node 3: 8

delete data 8
node 1: 2
node 2: 6

insert data 10
node 1: 2
node 2: 6
node 3: 10

delete data 2
node 1: 6
node 2: 10

insert data 12
node 1: 6
node 2: 10
node 3: 12

delete data 10
node 1: 6
node 2: 12
请按任意键继续. . .


3.4 在任意节点之后插入新节点
//============================================================================
// Name        : doubly linked list
// Author      : Yongqiang Cheng
// Version     : Version 1.0.0
// Description : Hello World in C++, Ansi-style
//============================================================================

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#define MAX_NODE_LEN 401
#define NULL 0

#include <stdio.h>

typedef struct NODE {
int data;
struct NODE *prev;
struct NODE *next;
} Node;

Node node_array[MAX_NODE_LEN];
int node_array_idx = 0;

{

node->next->prev = node;
}

void delete_node(const Node *node)
{
Node *prev_node = node->prev;
Node *next_node = node->next;
// current node - node

prev_node->next = next_node;
next_node->prev = prev_node;
}

void delete_node_v1(const Node *node)
{
// current node - node

node->prev->next = node->next;
node->next->prev = node->prev;
}

void delete_node_v2(Node *node)
{
// current node - node

node->prev->next = node->next;
node->next->prev = node->prev;

node->next = node->next = NULL;
}

{
int n = 1;

{
printf("node %d: %d\n", n, node->data);
++n;
node = node->next;
}
}

{
int n = 1;

{
printf("node %d: %d\n", n, node->data);
++n;
node = node->prev;
}
}

int main()
{
// 头节点 (非头指针)
Node root;

// initialization
// root.prev = &(root);
// root.next = &(root);
root.prev = root.next = &(root);
root.data = 0;

for (int i = 0; i < MAX_NODE_LEN; ++i)
{
node_array[i].prev = NULL;
node_array[i].next = NULL;
node_array[i].data = 0;
}

// insert 0
node_array[0].data = 0;
insert_first(&root, &(node_array[0]));

// insert 2
node_array[2].data = 2;
insert_first(&root, &(node_array[2]));

// insert 4
node_array[4].data = 4;
insert_first(&root, &(node_array[4]));

// insert 6
node_array[6].data = 6;
insert_first(&root, &(node_array[6]));

// insert 8
node_array[8].data = 8;
insert_first(&root, &(node_array[8]));

display(&root);

// insert 10
node_array[10].data = 10;
insert_first(&root, &(node_array[10]));
printf("\ninsert data %d\n", 10);
display(&root);

/********************************* traverse function *********************************/
{
Node *tmp_node;
{
tmp_node = ptr_node->prev;
if (8 == ptr_node->data) {
// insert 24
node_array[24].data = 24;
insert_first(ptr_node, &(node_array[24]));
}

ptr_node = tmp_node;
}
}
/********************************* traverse function *********************************/

printf("\ninsert data %d\n", 24);
display(&root);

return 0;
}


node 1: 8
node 2: 6
node 3: 4
node 4: 2
node 5: 0

insert data 10
node 1: 10
node 2: 8
node 3: 6
node 4: 4
node 5: 2
node 6: 0

insert data 24
node 1: 10
node 2: 8
node 3: 24
node 4: 6
node 5: 4
node 6: 2
node 7: 0
请按任意键继续. . .


References
https://www.cnblogs.com/skywang12345/p/3561803.html https://www.alphacodingskills.com/ds/circular-doubly-linked-list.php
展开全文
• 带头结点的双向循环链表

千次阅读 2020-08-07 11:44:14
1.双向循环链表的节点中有一个数据域，两个指针域，其一指向直接后继，另一指向直接前驱。 2.带头节点的双向循环链表如图所示： 3.删除节点时的指针变化 4.插入一个节点时的指针变化 #ifndef _DCLIST_H_ #define...
1.双向循环链表的节点中有一个数据域，两个指针域，其一指向直接后继，另一指向直接前驱。  2.带头节点的双向循环链表如图所示：
3.删除节点时的指针变化  4.插入一个节点时的指针变化  5.带头节点的双向循环链表的实现
#ifndef _DCLIST_H_
#define _DCLIST_H_

#include "common.h"
//带头结点的双向循环链表
//节点
typedef struct DCListNode
{
ElemType data;
struct DCListNode *next;
struct DCListNode *prev;
}DCListNode;
//链表
typedef DCListNode* DCList;
//声明
//
//申请一个节点
//可以接收各种类型
{
DCListNode* _S= (DCListNode *)malloc(sizeof(DCListNode));
assert(_S!= NULL);
_S->data = v;
_S->next = _S->prev = _S;

return _S;
}
//初始化
{
}
//打印
{
//打印时需要把头结点刨去
{
printf("%d->", p->data);
p = p->next;
}
printf("Over!\n");
}
//尾插
{
//不用去寻找最后一个数据的原因是具有头结点
//并且循环，可以直接找到尾数据
}
//头插
{
//先连接前驱和后继
s->prev->next = s;
s->next->prev = s;
}
//尾删
{
return;

free(p);

}
//头删
{
//进行条件判断 判空 如果只有头结点时
{
return;
}
//用指针p标记要删除的节点
p->next->prev = p->prev;
p->prev->next = p->next;
free(p);
}
//求长度
{//注意不包括头结点
size_t size = 0;
{
size++;
p = p->next;
}
return size;
}
//取首元素
{
}
//取尾元素
{
return;*/
}
//清除（保留头结点并且循环完整，数据节点清除掉）
{
//相等的话 什么都不做
//（如果只有头结点，则不进行任何操作）
{
p->prev->next = p->next;
p->next->prev = p->prev;
free(p);
}
}
//销毁 （不保留头结点）
{
}
//查找
{
{
p = p->next;
}
//为什么if判断放后面不放while前面
//因为还有包括p在最后一个节点时的情况
{
return NULL;
}
return p;
}
//按值删除
{
if (s == NULL)
{
printf("该元素不存在\n");
return;
}
s->prev->next = s->next;
s->next->prev = s->prev;
free(s);
}
//排序
{
//思想：先把第一个节点和后面节点断开，然后让后面节点按值插入
//只有一个节点 不需要进行排序
return;
//断开后面节点
DCListNode *q = p->next;
{
q = p;//q标记p
p = p->next;//p往后走

//按值插入
//标记第一个节点
//寻找位置
while (tmp != phead&&tmp->data < p->data)//如果只有一个节点，不会进入这个循环
tmp = tmp->next;

p->next = tmp;
p->prev = tmp->prev;
p->next->prev = p;
p->prev->next = p;
}

}
//按值插入
{
//寻找插入位置
{
p = p->next;
}
//只有头结点时也符合以下条件
s->next = p;
s->prev = p->prev;
s->next->prev = s;
s->prev->next = s;
}
//逆置
{
//只有一个节点 不需要逆置
return;
//断开后面节点
DCListNode *q = p->next;
//进行逆置（进行头插）
// 不需要借用第三个指针 注意因为是双向循环
{
p = q;
q = q->next;

p->next->prev = p;
p->prev->next = p;
}
}

展开全文
• 带头双向循环链表 结构描述： 带头双向循环链表:结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以店会发现结构会带来很多...
带头双向循环链表
结构描述：
带头双向循环链表:结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以店会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
LTDataType _data;
struct ListNode* _next;
struct ListNode* _prev;
}ListNode;

{
}Linklist;
接口声明：
//创建新节点
ListNode* createNode(LTDataType x);
// 初始化.
// 双向链表销毁
// 双向链表打印
// 双向链表尾插
// 双向链表尾删
// 双向链表头插
// 双向链表头删
// 双向链表查找
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
下面开始实现每一个接口，完成接口定义：其中接口实现可以按照如下的链表结构来理解其中指针的指向

（1）初始化：

// 创建返回链表的头结点.
{

}
（2）创建新节点
//创建新节点
ListNode* createNode(LTDataType x)
{
struct ListNode* newnode= (struct ListNode*)malloc(sizeof(struct ListNode));
newnode->_data = x;
newnode->_next = newnode->_prev = NULL;
return newnode;
}
（3）尾插：
根据上述示例结构，在尾部插入一个新节点

代码如下：更改四个指针指向即可完成
//尾插
{

struct ListNode* newnode = createNode(x);

tail->_next = newnode;
newnode->_prev = tail;

}
考虑只有头结点情况

发现以上代码对于只包含头结点的空链表依然适用，尾插不需要对只包含头结点的空链表特殊处理
（4）尾删

// 双向链表尾删
{
//空链表不能删除，破坏双向带头循环链表结构
return;
struct ListNode* prev = tail->_prev;
free(tail);
}
考虑只有头结点 是否可以删除尾结点操作

删除后会破坏了双向带头循环链表的结构，所以仅包含头结点的双向带头循环链表无法完成尾删操作
（5）头插

//头插
{
struct ListNode* newnode = createNode(x);

newnode->_next = next;
next->_prev = newnode;
}
(6)头删

头删是删除第一个数据节点，如果空链表  无法删除，否则破坏链表结构
// 双向链表头删
{
return;

struct ListNode* nextnext = next->_next;
free(next);

}
（7）任意位置插入/删除
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
struct ListNode* newnode = createNode(x);
struct ListNode* prev = pos->_prev;

pos->_prev = newnode;
newnode->_next = pos;

prev->_next = newnode;
newnode->_prev = prev;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
if (pos->_next == pos->_prev)
return;
struct ListNode* next = pos->_next;

struct ListNode* prev = pos->_prev;
free(pos);
next->_prev = prev;

prev->_next = next;
}
（8）遍历链表打印
void ListPrint(Linklist* plist)
{
{
printf("%d ", cur->_data);
cur = cur->_next;
}
printf("\n");
}
（9）链表销毁
//销毁链表
{
{
struct ListNode* next = cur->_next;
free(cur);
cur = next;
}
}
（10）测试代码:
#include<stdio.h>

void test()
{
ListInit(&plist);
printf("尾插：\n");
ListPushBack(&plist,1);
ListPushBack(&plist, 2);
ListPushBack(&plist, 3);
ListPushBack(&plist, 4);
ListPushBack(&plist, 5);
ListPrint(&plist);
printf("尾删：\n");
ListPopBack(&plist);
ListPrint(&plist);
ListPopBack(&plist);
ListPrint(&plist);
ListPopBack(&plist);
ListPrint(&plist);
ListPopBack(&plist);
ListPrint(&plist);
ListPopBack(&plist);
ListPrint(&plist);
printf("头插：\n");
ListPushFront(&plist, 1);
ListPushFront(&plist, 2);
ListPushFront(&plist, 3);
ListPushFront(&plist, 4);
ListPushFront(&plist, 5);
ListPrint(&plist);
printf("头删：\n");
ListPopFront(&plist);
ListPrint(&plist);
ListPopFront(&plist);
ListPrint(&plist);
ListPopFront(&plist);
ListPrint(&plist);
ListPopFront(&plist);
ListPrint(&plist);
ListPopFront(&plist);
ListPrint(&plist);
}

int main()
{
test();
}
执行结果如下：


展开全文
• 双向带头循环链表

多人点赞 2021-04-17 20:23:09
如上图所示，即一个最简单的双向循环链表的示意图，链表中每一个结点都由三部分组成，包括数据域，next指针，prev指针 其中，next指针指向下一个结点，prev指针指向它的前一个结点，这样一来就构成了一个头尾相连...
• 若是不清楚链表的结构，该篇文章不适合观看，这里只做文字说明，没有链表结构的图示
• 单链表、双向链表、循环链表

千次阅读 多人点赞 2019-07-26 14:26:09
学习三种常见的链表结构，他们分别是：单链表、双向链表和循环链表。 单链表 单链表有两个较特殊节点，结点和尾节点。结点用来记录链表的基地址，可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向...
• 双向链表的建立和单链表的建立差不多，只不过单链表只是指向一个方向，而双链表指向两个方向。...首先我们先创立一个表头，即只有一个节点的循环链表，只有一个节点意味着front指针和tail指针都指向自身 //创建表头 d
• ·什么是带头结点的双向循环链表 我们直接给出带头结点的双向循环链表的图示： 那么有无结点的区别是什么呢？ 节点是为了操作的统一、方便而设立的，一般来说，节点放在第一元素节点之前，其数据域一般无...
• 在之前的文章中，我写过一篇关于C语言实现双向链表博文，介绍了双向链表的实现过程以及双向链表的优势，接下来我首先给大家介绍一下循环链表和双向链表的区别，之后再给大家介绍双向循环链表的具体实现。 循环链表和...
• 查找元素 ...//**双向循环链表 查找元素或元素指针** #include<stdio.h> #include<Stdio.h> typedef struct node { int data; struct node *next, *pre; }link; //生成该链表 link *creat...
• 建立双向循环链表，实现双向循环链表的删除操作。 #include <stdio.h> int nodeNum = 5; struct node { int t; node * llink; node * rlink; }; //建表 struct node *creatlist() { int i = 0; int...
• 图展示的是一个单向循环链表，他跟以上的单向链表对比只是多了一个指向结点的 指针，因此，他们的算法几乎是一样的。 第一，设计节点。 单向循环链表的节点跟单向链表完全一致。 第二，初始化空链表。 跟单向链表...
• 双向链表也叫双链表，是链表...一般我们都构造双向循环链表。 简单的画一个双向循环简易图： 下面就用C++实现一下基本操作 当然也有 C 语言 版的，只是单链表操作 （https://blog.csdn.net/Paranoid_cc/artic...
• 在之前我们写了不带头结点的单链表，但它在数据操作时也有繁琐之处，而双向带头结点循环链表则优化了单链表的操作，使链表更加方便。双向带头结点循环链表在单链表的基础上增加了以下几点： （1）在数据结构上附加一...
• 1、首先这里采用的还是有空头的方法，注意下，双向循环链表结点的Front指针和Tail指针都指向自己，它和单链表的不同就是它有两个指针，因为，你想，要想循环，就必须要知道自己前面和后面是谁，然后头尾一连就是...
• 本次博文是关于利用C++模板的方式实现的双向循环链表以及双向循环链表的基本操作，在之前的博文C++语言实现双向链表中，已经给大家分析了双向循环链表的结构，并以图示的方式给大家解释了双向循环链表的基本操作。...
• 什么是双向循环链表 1、拥有两个指针域prior以及next，一个数据域data 2、尾部的next指针 指向结点 存储结构 typedef struct DuLNode { ElemType data; struct DuLNode *prior; struct DuLNode *next; }DuLNode...
• 文章目录一、什么是双向循环链表？二、带头结点的双向循环链表的实现 一、什么是双向循环链表？ 双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同，双向链表也有带头结点结构和不带头结点结构两种...
• 双向循环链表中，每个结点包括三个域，分别是数据域（data域）、指向后继结点的指针域（next域）和指向前驱结点的指针域（pre域）。 双向循环链表结点结构 和单链表相同，双向链表也有带头结点结构和不带头...
• 不带头结点的双向循环链表

千次阅读 2019-05-21 18:46:36
基本概念 循环链表：将单链表中最后一个结点的next指向结点或者空指针，就使得整个单链表形成一个环，这种头尾相接的单链表...双向循环链表：将二者结合起来，结点有两个指针域，且最后一个结点的next指向...
• 双向循环链表的长度Problem statement: 问题陈述： Given a linked list, write a program that checks whether the given Linked List contains a loop or not and if the loop is present then return the count...
• 概念：链表是一种物理存储结构上非连续、非顺序的...2、带头双向循环链表 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结...
• 双向循环链表 每个结点有两个指针域，分别指向前驱结点和后继结点，尾结点的后继指针指向结点，结点的前驱指针指向尾结点。整体形成一个双向连通的环。 创建一个结点类： class Node(object): """结点...

...