双向链表添加元素操作_双向链表后插元素

创建双向链表

先创建链表并且初始化

添加元素操作

Size一个都没有的时候

证明是空链表

前插法

意思就是往前添加元素

第一步 : 创建结点

可以用C++ 的 new 创建结点 或者 用面向过程 的 function 来 创建

函数声明

//创建双向链表结点 
//创建链表头结点的函数
//参数:LinkNode* where = nullptr  
//LinkNode* where目的是给list->next赋值和list->prev不初始化数据域
LinkNode* creatorLinkNode(LinkNode* where = nullptr);

//创建双向链表结点 
//参数:const ElemType &elem  
//const ElemType &elem 目的是给 新结点的数据域初始化、不初始化指针域
LinkNode* creatorLinkNode(const ElemType& elem);
1
2
3
4
5
6
7
8
9
10

函数实现

LinkNode* creatorLinkNode(LinkNode* where) {

	LinkNode* newNode = new LinkNode;
	newNode->prev = where;
	newNode->next = where;
	return newNode;

}

LinkNode* creatorLinkNode(const ElemType& elem) {
	LinkNode* newNode = new LinkNode{ elem };
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

创建结点

第二步 : 链接结点

函数声明

void Link(LinkNode*& node, LinkNode*& newnode);
1

函数实现

void Link(LinkNode*& node, LinkNode*& newnode) {

	if (node->next){

		node->next->prev = newnode;
		newnode->next = node->next;
	}
	newnode->prev = node;
	node->next = newnode;
}
1
2
3
4
5
6
7
8
9
10

链接结点操作:

第一步

第二步

第三步

把链表的头结点传递到Link函数

Link(List.list, Newnode);
1

第四步 链表的个数+1

++List.size;
1

前插法添加完成

前插法 代码

void LinkListInsert_froot(LinkList& List, LinkNode*& Newnode) {
	Link(List.list, Newnode);
	++List.size;
}
1
2
3
4

后插法

意思就是往前添加元素

第一步 : 创建结点

可以用C++ 的 new 创建结点 或者 用面向过程 的 function 来 创建

函数声明

//创建双向链表结点 
//创建链表头结点的函数
//参数:LinkNode* where = nullptr  
//LinkNode* where目的是给list->next赋值和list->prev不初始化数据域
LinkNode* creatorLinkNode(LinkNode* where = nullptr);

//创建双向链表结点 
//参数:const ElemType &elem  
//const ElemType &elem 目的是给 新结点的数据域初始化、不初始化指针域
LinkNode* creatorLinkNode(const ElemType& elem);
1
2
3
4
5
6
7
8
9
10

函数实现

LinkNode* creatorLinkNode(LinkNode* where) {

	LinkNode* newNode = new LinkNode;
	newNode->prev = where;
	newNode->next = where;
	return newNode;

}

LinkNode* creatorLinkNode(const ElemType& elem) {
	LinkNode* newNode = new LinkNode{ elem };
	return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

创建结点

循环找到末尾结点

第二步 : 链接结点

函数声明

void Link(LinkNode*& node, LinkNode*& newnode);
1

函数实现

void Link(LinkNode*& node, LinkNode*& newnode) {

	if (node->next){

		node->next->prev = newnode;
		newnode->next = node->next;
	}
	newnode->prev = node;
	node->next = newnode;
}
1
2
3
4
5
6
7
8
9
10

链接结点操作:

第一步

第二步

第三步

把current传递到Link函数

Link(current, Newnode);
1

第四步 链表的个数+1

++List.size;
1

尾插法添加完成

尾插法 代码

void LinkListInsert_back(LinkList& List, LinkNode*& Newnode) {
	
	LinkNode* current = List.list;
	while (current->next) {

		current = current->next;
	}
	
	Link(current, Newnode);
	++List.size;	
}
1
2
3
4
5
6
7
8
9
10
11