链表基础

2022.05.14

• • • 链表的遍历
    • 添加结点
    • 链表删除
    • 链表空节点

链表的遍历

#include 
#include 

using namespace std;

const int N = 1010;

struct Node
{
	int val;
	Node* next;	
	
	Node(int _val):val(_val), next(NULL){}
	
};

int main(){
//	Node node = Node(1);
//	Node* p = &node;
	//等价于
	Node* p = new Node(1); // new 返回地址，不加new则返回值
//	auto p = new Node(1);
	Node* q = new Node(2);
	Node* o = new Node(3);
	p->next = q;
	q->next = o;
	// 头结点head一般指的是第一个结点的地址 
	Node* head = p;
	
	// 链表的遍历 
	for(Node* i = head; i != NULL; i = i->next)
		cout << i->val << endl;
		
	Node x = Node(4); 
	Node y = Node(5);
	Node z = Node(6);
	x.next = &y;
	y.next = &z;
	head = &x;
	for(Node* i = head; i != NULL; i = i->next)
		cout << i->val << endl; // 4 5 6
// 	for(Node i = x; i.next != NULL; i = *(i.next))
// 	    cout << i.val << endl; // 4 5
		
//	p->next = p; // p为地址用p->, 若p为Node,这用p. 
//	p->val; 
		
	return 0;
}

添加结点

头插

#include 
#include 

using namespace std;

const int N = 1010;

struct Node
{
	int val;
	Node* next;	
	
	Node(int _val):val(_val), next(NULL){}
};

int main(){
//	Node node = Node(1);
//	Node* p = &node;
	//等价于
	Node* p = new Node(1); // new 返回地址，不加new则返回值
//	auto p = new Node(1);
	Node* q = new Node(2);
	Node* o = new Node(3);
	p->next = q;
	q->next = o;
	// 头结点head一般指的是第一个结点的地址 
	Node* head = p;
	
	// 添加结点 
	Node* u = new Node(4);
	u->next = head;
	head = u;
	
	// 链表的遍历 
	for(Node* i = head; i != NULL; i = i->next)
		cout << i->val << endl;
		
	return 0;
}

链表删除

链表删除：链表的删除是指在遍历的时候遍历不到这个结点

#include 
#include 

using namespace std;

const int N = 1010;

struct Node
{
	int val;
	Node* next;	
	
	Node(int _val):val(_val), next(NULL){}
};

int main(){
//	Node node = Node(1);
//	Node* p = &node;
	//等价于
	Node* p = new Node(1); // new 返回地址，不加new则返回值
//	auto p = new Node(1);
	Node* q = new Node(2);
	Node* o = new Node(3);
	p->next = q;
	q->next = o;
	// 头结点head一般指的是第一个结点的地址 
	Node* head = p;
	
	// 添加结点 
	Node* u = new Node(4);
	u->next = head;
	head = u;
	// 链表的删除是指在遍历的时候遍历不到这个结点
	head->next = head->next->next;  // 4 1 2 3中删除1
		
	// 链表的遍历 
	for(Node* i = head; i != NULL; i = i->next)
		cout << i->val << endl;
		
	return 0;
}

链表空节点

返回空节点：0、NULL或nullptr