链表
一、 何为链表
引用维基百科的介绍, 链表(Linked list)是一种常见的基础数据结构, 是一种线性表, 但是并不会按照线性的顺序存储结构,是一种"在物理空间上非连续、非顺序的存储结构"。
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表通常由一连串节点组成，每个节点包含:
- 链域： 它的值是线性表的上一个/下一个元素的位置，即地址。
- 数据域： 它的值是存储的相应实例数据的值。
二、链表的优缺点
优点 ：
- 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
- 相比数组结构，对于元素的插入和删除操作来说，链表的效率要比数组高，因为每个节点都有链域存储指向下一个节点的指针，因此进行插入和删除的操作时不需要频繁的移动其他的元素，只需要修改对应位置附近节点的链域的值即可。
缺点
- 查询链表只能通过指针顺序访问，效率相对低下，查询可能需要O(n)的时间复杂度。
- 因为链表的每个节点都含有链域，所占用的空间较多。
三、单链表的实现(C++)
- 定义节点的结构
template<class T>
struct ListNode
{
T m_tElement; // 数据域
ListNode<T>* m_pNext; // 链域
// 构造函数
ListNode(){}
ListNode(const T& theElement) {this->m_tElement = theElement;}
ListNode(const T& theElement, ListNode<T>* theNext)
{
this->m_tElement = theElement;
this->m_pNext = theNext;
}
}
- 定义链表类
template<class T>
class SingleList
{
public:
// 构造函数与析构函数
SingleList();
SingleList(const SingleList<T>& theList);
~SingleList();
// 类方法
bool empty() const {return m_iLength == 0;} // 判断链表是否为空
int size() const {return m_iLength;} // 返回链表长度
int indexOf(const T& theElement) const;
T& get(int theIndex) const;
void insert(int theIndex, const T& theElement);
void delete(int theIndex);
void update(int theIndex, const T& theElement);
private:
void checkIndex(theIndex); // 确认是否索引值是否合法
int m_iLength; // 链表的长度
ListNode<T>* m_pFirstNode; // 链表的头节点
}
- 构造函数的实现
// 无参构造函数
template<class T>
SingleList<T>::SingleList()
{
m_pFirstNode = NULL;
m_iLength = 0;
}
// 复制构造函数
template<class T>
SingleList<T>::SingleList(const SingleList<T>& theList)
{
m_iLength = theList.m_iLength;
// 判断源链表是否为空链表
if(m_iLength == 0)
{
m_pFirstNode = NULL;
return;
}
ListNode<T>* otherNode = theList.m_pFirstNode;
m_pFirstNode = new ListNode<T>(otherNode->m_tElement);
ListNode<T>* thisNode = m_pFirstNode;
otherNode = otherNode->m_pNext;
while (otherNode != NULL)
{
// 当源链表后续还有节点时，复制链表剩下的其他节点
thisNode->m_pNext = new ListNode<T>(otherNode->m_tElement);
thisNode = thisNode->m_pNext;
otherNode = otherNode->m_pNext;
}
thisNode->next = NULL;
}
- 析构函数的实现
template<class T>
SingleList<T>::~SingleList()
{
while (m_pFirstNode != NULL)
{
ListNode<T>* tempNode = m_pFirstNode;
delete m_pFirstNode;
m_pFirstNode = tempNode;
}
}
-
类方法的实现
int indexOf(const T& theElement) const
// 返回指定元素的索引值
template<class T>
int SingleList<T>::indexOf(const T& theElement) const
{
ListNode<T>* currNode = m_pFirstNode;
int index = 0;
while (currNode != NULL && currNode->m_tElement != theElement)
{
currNode = currNode->m_pNext;
++index;
}
if (currNode == NULL)
{
return -1;
}
if (currNode != NULL)
return index;
}
T& get(int theIndex) const
// 返回指定索引的元素
template<class T>
T& SingleList<T>::get(int theIndex) const
{
checkIndex(theIndex);
ListNode<T>* currNode = m_pFirstNode;
// 找到索引值对应的元素
for(int i = 0; i < theIndex; ++i)
currNode = currNode->m_pNext;
// 返回元素的值
return currNode->m_tElement;
}
void insert(int theIndex, T& theElement)
// 在指定位置插入元素
template<class T>
void SingleList<T>::insert(int theIndex, const T& theElement)
{ // 判断索引值是否合法
checkIndex(theIndex);
if (theIndex == 0)
{
m_pFirstNode = new ListNode<T>(theElement, m_pFirstNode)
}
if (theIndex > 0)
{
ListNode<T>* currNode = m_pFirstNode;
// 因为要在指定位置插入元素, 因此去找指定位置的前一个元素
for (int i = 0; i < theIndex - 1; ++i)
currNode = currNode->m_pNext;
ListNode<T>* newNode = new ListNode<T>(theElement, currNode->m_pNext);
}
++m_iLength;
}
void delete(int theIndex)
// 删除指定位置的元素
template<class T>
void SingleList<T>::delete(int theIndex)
{
checkIndex(theIndex);
ListNode<T>* targetNode;
if (theIndex == 0)
{
targetNode = m_pFirstNode;
m_pFirstNode = m_pFirstNode->m_pNext;
}
if (theIndex > 0)
{
ListNode<T>* prevNode = m_pFirstNode;
for (int i = 0; i < theIndex - 1; ++i)
prevNode = prevNode->m_pNext;
targetNode = prevNode->m_pNext;
prevNode->m_pNext = targetNode->m_pNext;
}
delete targetNode;
--m_iLength;
}
void update(int theIndex, const T& theElement)
// 修改指定位置元素的值
template<class T>
void SingleList<T>::update(int theIndex, const T& theElement)
{
// 判断索引值是否合法
checkIndex(theIndex);
//
if (theIndex == 0)
{
m_pFirstNode->m_tElement = theElement;
return ;
}
ListNode<T>* currNode = m_pFirstNode;
for (int i = 0; i < theIndex; ++i)
currNode = currNode->m_pNext;
currNode->m_tElement = theElement;
}
void checkIndex(int theIndex)
// 检查索引值是否合法
template<class T>
void SingleList<T>::checkIndex(int theIndex)
{
if (theIndex < 0 || theIndex > m_iLength - 1)
std::cout << "Error Index Value" << std::endl;
}
四、结语
这是我第一次做类似的学习笔记，借鉴了网上许多的博客以及书籍的资料和内容，在这里做个记录，若是有错误或不恰当之处，希望各路大神能不吝赐教，指点小弟不足之处。
