下面说的线性表主要是线性链表，这里主要将双向链表，单向链表循环链表等是类似的，不再累述。如果发现错误，还望不吝指正。

定义

线性表 （linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

在稍复杂的线性表中，一个数据元素可由多个数据项 （item）组成，此种情况下常把数据元素称为记录 （record），含有大量记录的线性表又称文件 （file）。

线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。

线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。（来自百度百科）

实现

采用的C++实现整个链表的操作过程，对于节点的内存的管理使用了C++11中提供的智能指针shared_ptr，以确保不会发生内存泄露的情况。

对链表操作的实现中采用了两层封装，将涉及到指针的操作封装成了私有方法，避免泄露指针，导致无法控制对象析构的时刻，并且整个链表是非线程安全的。

节点数据结构：

template <typename T>
class Node {
public:
	Node() { _prev = nullptr, _next = nullptr; }
	Node(T data) : Node() { _data = data; }
	void set_data(T data) { _data = data; }
	void set_prev(std::shared_ptr<Node<T>> prev) { _prev = prev; }
	void set_next(std::shared_ptr<Node<T>> next) { _next = next; }
	std::shared_ptr<Node<T>> prev() { return _prev; }
	std::shared_ptr<Node<T>> next() { return _next; }
	T data() { return _data; }

private:
	T _data;
	std::shared_ptr<Node<T>> _prev;
	std::shared_ptr<Node<T>> _next;
};

整个表结构：

整个表包含一个指向头结点的指针和一个指向尾节点的指针，以及表的长度和表的大小的变量。

template <typename T>
class LinearList
{
public:
	LinearList();
	~LinearList();
	void insert_node(T data, int64_t index);
	void delete_node(int64_t index, T& data);
	T get_element(int64_t index);
	int64_t size();
	int64_t length();

private:
	std::shared_ptr<Node<T>> get_ptr(int64_t index);
	std::shared_ptr<Node<T>> get_element_ptr(int64_t index);
	void insert_node_ptr(std::shared_ptr<Node<T>> &data, int64_t index);
	void delete_node_ptr(int64_t index, std::shared_ptr<Node<T>> &data);

private:
	std::shared_ptr<Node<T>> _current;
	std::shared_ptr<Node<T>> _head;
	std::shared_ptr<Node<T>> _tail;
	int64_t _current_index;
	int64_t _size;
	int64_t _length;
};

 

插入新节点：　　

整个链表是一个带空头结点的链表：

1. 寻找插入点

2. 将待插入节点的next指针指向插入点指向的下一节点

3. 将待插入节点的prev指针指向插入点

4. 如果插入点的next指针不为空（不是头结点），将插入点的下一节点的prev指针指向带插入节点

5. 将插入点的next指针指向待插入点

 

 图画的比较丑，简单的表示下程序的执行过程 

template<typename T>
inline void LinearList<T>::insert_node(T data, int64_t index)
{
	if (index < 0 || index > _length)
	{
		index = _length;
	}
	std::shared_ptr<Node<T>> data_ptr = std::make_shared<Node<T>>(data);
	this->insert_node_ptr(data_ptr, index);
}

inline void LinearList<T>::insert_node_ptr(std::shared_ptr<Node<T>> &data, int64_t index)
{
	_ASSERTE(!(index < 0 || index > _length));
	std::shared_ptr<Node<T>> tmp_ptr(_head);
	// 查找插入位置
	for (int64_t i = 0; i < index; ++i)
	{
		tmp_ptr = tmp_ptr->next();
	}
	// 将data插入到tmp_ptr的后面
	data->set_next(tmp_ptr->next());
	data->set_prev(tmp_ptr);
	tmp_ptr->next() == nullptr ? tmp_ptr : tmp_ptr->next()->set_prev(data);
	tmp_ptr->set_next(data);
	_tail = index == _length ? data : _tail;
	++_length;
	_size += sizeof(Node<T&