[数据结构与算法]数据结构-链表

链表的特点

• 查找速度慢，只能从表头开始遍历，直到找到所需要的位置
• 数据增删快，适用于需要对数据进行频繁增删的情况；时间复杂度O(n)，空间复杂读O(1)
• 在内存中存储不连续，可以有效的利用碎片化内存

单链表的结构

链表由一个数据位（存放数据），一个指针位（存放指向下一个节点的指针）构成，如下图所示：

基于c++的单链表实现

仅针对单链表最重要的增删功能进行实现，针对该功能只需要牢牢记住两个个原则：

• 首先记录头节点的位置，再进行操作
• 找到要增加、删除元素的前一个位置，再进行操作

#include<iostream>

using namespace std;

class List
{
private:
	//节点结构
	struct Node
	{
		int data;
		Node* next;
		Node(const int& d) :data(d), next(NULL) {}
	};
	//头节点
	Node* head;
	//清理函数
	void clear()
	{
		Node* p = head;
		while (p)
		{
			Node* temp = p->next;
			delete p;
			p = temp;
		}
	}
	//查找数据d的上一个节点位置的函数
	Node* find(const int& d)
	{
		Node* p = head;
		for (; p; p->next)
		{
			if (p->next->data == d)
			{
				break;
			}
		}
		return p;
	}

public:
	List() { create_list(); }
	~List() { clear(); }
	//创建头节点
	void create_list();
	//末尾插入函数
	void insert_end(const int& d);
	//开头插入函数
	void insert_head(const int& d);
	//指定位置插入函数
	void insert_pos(const int& d, const int& pos);
	//删除指定位置的节点
	void erase_local(const int& pos);
};

//创建头节点
void List::create_list()
{
	head = new Node(0);
}

//链表末尾处插入节点
void List::insert_end(const int& d)
{
	Node* p = new Node(d);
	Node* temp = head;
	while (temp->next != NULL)
	{
		temp = temp->next;
	}
	temp->next = p;
}
//链表开头处插入节点
void List::insert_head(const int& d)
{
	Node* p = new Node(d);
	p->next = head;
	head = p;
}

void List::insert_pos(const int& d, const int& pos)
{
	Node* p = new Node(d);
	Node* temp = head;
	for (int i = 0; i < pos; i++)
	{
		temp = temp->next;
	}
	p->next = temp->next;
	temp->next = p;
}

void List::erase_local(const int& pos)
{
	if (pos == 0)
	{
		Node* temp = head;
		head = head->next;
		delete temp;
	}
	else
	{
		Node* temp = head;
		for (int i = 1; i < pos - 1; i++)
		{
			temp = temp->next;
		}
		Node* del = temp->next;
		temp->next = temp->next->next;
		delete del;
	}
}

int main()
{
	List l;
	l.insert_end(1);
	l.insert_end(2);
	l.insert_end(3);
	l.insert_end(4);
	l.insert_pos(5, 2);
	l.insert_head(6);
	l.erase_local(0);

	return 0;
}