数据结构——链表

c++数据结构p3

链表

• 链表的每一个节点都是独立分配出来的
• 从当前节点能够找到下一个节点
  Node(链表)=date(数据域）+next(地址域）
  地址域：存储的是下一个节点的地址
  最后一个地址域是nullptr

struct Node{
  int data;
  Node *next;
}

特点：每一个节点都是在堆内存上独立new出来的。节点内存不连续
优点：

1. 内存利用率高，不需要大块连续内存
2. 插入和删除节点不需要移动其他节点，时间复杂度O(1)
3. 不需要专门进行扩容操作

缺点：

1. 内存占用空间大，每一个节点多出存放地址的空间
2. 内存不连续，无法进行内存的随机访问
3. 链表的搜索效率不高，只能从节点开始逐节点遍历

#include <iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

//节点类型
struct Node {
	Node(int data = 0) :data_(data), next_(nullptr) {}
	//节点类型的构造函数
	int data_;
	Node* next_;
};

//单链表代码实现
//只有在找尾节点指针才指向下一个
class Clink {
public:
	Clink() {
		//给head_初始化指向指向头节点
		head_ = new Node();
	}
	~Clink() {
		//delete []head_;删除数组类指针[]指针
		//head_=nullptr;
		//链表遍历每一个节点
		Node* p = head_;
		while (p != nullptr) {
			head_ = head_->next_;
			delete p;
			p = head_;
		}
		head_ = nullptr;
	}
public:
	//单链表尾插法  O(n)
	//若head_:头节点  tail_:尾节点  O(1)
	void insertTail(int val) {
		//先找的当前链表的末尾节点
		Node* p = head_;
		while (p->next_ != nullptr) {
			p = p->next_;
		}
		//生成新的节点
		Node* node = new Node(val);
		//把生成的新节点挂在尾节点后面
		p->next_ = node;
	}
	//单链表头插法
	void insertHead(int val) {//O(1)
		Node* node = new Node(val);
		node->next_ = head_->next_;
		head_->next_ = node;
	}
	//单链表删除第一个节点
	//删除0(1),搜索+删除0(n)
	void Remove(int val) {
		Node* q = head_;
		Node* p = head_->next_;
		while (p != nullptr) {
			if (p->data_ == val) {
				q->next_ = p->next_;
				delete p;
				return;
			}
			else {
				q = p;
				p = p->next_;
			}
		}
	}
	//单链表删除多个节点
	void RemoveAll(int val) {
		Node* q = head_;
		Node* p = head_->next_;
		while (p != nullptr) {
			if (p->data_ == val) {
				q->next_ = p->next_;
				delete p;
				//对指针p进行重置
				p = q->next_;
			}
			else {
				q = p;
				p = p->next_;
			}
		}
	}
	//搜索  list  O(n)数组搜索 下表访问/随机访问arr[i] O(1)     搜索O（n）
	bool Find(int val) {
		Node* p = head_->next_;
		while (p->next_ != nullptr) {
			if (p->data_ == val) {
				return true;
			}
			else {
				p = p->next_;
			}
		}
		return false;
	}
	//链表的打印
	void Show() {//从第一个节点打印到最后一个节点
		Node* p = head_->next_;
		while (p != nullptr) {
			cout << p->data_ << " ";
			p = p->next_;
		}
		cout << endl;
	}
private:
	Node* head_;//指向链表的头节点
};


int main() {
	Clink link;
	srand(time(0));
	for (int i = 0; i < 10; i++) {
		int val = rand() % 100;
		link.insertHead(val);
		cout << val << " ";
	}
	cout << endl;

	link.insertTail(200);
	link.Show();

	link.Remove(200);
	link.Show();


	return 0;
}