C++,python单链表
机器学习入坑者 人气:0一、链表的基本概念
链表是数据元素的线性集合（Linear Collection），物理存储不连续。那么，这种设计的优点是什么？缺点又是什么？
链表的基本结构：
链表是由一系列的“节点”组成在一起的集合，节点（Node）由数据域（data）和指针域（next）组成。
从功能上看，data负责存储数据，next负责存储下一个节点的位置。当然，用更加严格的语句来讲，next存储的是其直接后继的地址，关于直接后继的定义见：
链表的分类：
常见的链表种类有：单向链表、双向链表、单向循环链表、双向循环链表，将会在后面文章中单独介绍各种链表的结构和代码实现，以及对应的链表操作。
链表的基本操作：
链表的基础操作包含：插入、删除、查找、合并等，此外还有：反转、排序、深度复制等。
链表的优点：
- 插入和删除快；
- 存储空间不受限制，可动态申请扩充，不需事先开辟内存；
链表的缺点：
- 相比于数组，链表的需要更多的存储空间（需存储指针）；
- 存储不连续导致其访问时间长；
- 从反向访问角度，单向链表难以反向访问，扩展为双向链表则需要额外存储反向指针；
- 每次节点访问都需要从头部开始；
二、单链表
基本结构：
单链表的结构含有四个概念：头指针、头结点、普通Node、尾结点，下面分别介绍：
- 头指针指向头结点，是单链表的表示，必不可少；
- 头结点是单链表的第一个节点，其数据域内容一般无效；
- 普通Node即用于数据存储和直接后继指针存储的节点；
- 尾结点即链表中最后一个节点，其指针域next为空，其后无节点；
单链表的基本操作：
针对单链表常见的操作有：增、改、查、删等，
常用的操作如下：
（1）增
对链表添加元素一般有三种方法：头插法(add)、尾插法(append)、任意位置插入法(insert)。
（2）改
改动链表中某个节点的data。
（3）查
查找分为按值查找和按位置查找两种，前者表示按照值查找对应位置，后者表示按位置查找对应值；
（4）删
删除分为按值删除和按位置删除两种；前者表示按照值删除对应节点，后者表示按照位置删除对应节点；
实现说明：
按照自己目前所看的资料，一般都会实现下面介绍的这些函数，具体介绍放在python和C++实现中。
1.python实现
（1）节点设计
按照单链表的定义可知，节点包含数据域data和指针域next：
但是由于next和python的内置函数next()重名，所以指针域使用pointer表示。
代码如下：
class Node: def __init__(self, data): """ Args: data: data of node, any type """ self.data = data self.pointer = None
（2）链表类：Single_Linked_List
上述Node类对象即为链表的基本组成结构，可以用于实现头结点、普通节点和尾结点。
因此，链表类只需要提供头指针：
class Single_Linked_List: def __init__(self, node=None): self.__head = node
（3）判断链表是否为空：is_empty()函数
实际上，只需要判断头指针是否指向Node类对象（或是否等于None），就可判断一个链表是否为空：
def is_empty(self): """判断链表是否为空""" if self.__head == None: return True else: return False
（4）头插法：add()函数
在链表头进行节点插入是很常见的插入操作，这种方式使得“先插入的节点在链表尾部”。头插法需要将头指针指向新的节点，并让新的节点指向原来的头结点：
def add(self, data): """Add dnode into head """ # 创建新节点 node = Node(data) # 令新的节点指向原来的头结点 node.pointer = self.__head # 令头指针指向新的节点 self.__head = node
（5）尾插法：append()函数
如果想要链表节点次序和插入次序相同，就需要使用尾插法。在插入之前需要判断链表是否为空，如果不为空才能进行插入（可以调用前面定义的is_empty()函数，但是下述代码没有）。
此外，还需要进行链表的遍历操作，找到最后一个节点。单链表只能从表头开始访问，所以每次尾插都必须遍历。
def append(self, data): """ append node into tail """ node = Node(data) # 头指针为空时即为首节点 if self.__head == None: self.__head = node # 头指针不为空时进行遍历 else: current = self.__head while current.pointer != None: current = current.pointer current.pointer = node
（6）在任意位置插入：insert()函数
前面介绍的头插法和尾插法，其原理相对简单，但是并不能完全满足插入需求。如果知道目标插入的位置，可以采用insert()函数实现任意位置的节点插入。
需要注意的是，在实现insert()函数时必须考虑到“position”参数可能出现的几种情况。比如python中并没有明确的类型要求，所以要检查“position”是不是int类型。
对于核心的节点插入实现功能，需要找到目标插入位置对应的节点，并使得这个节点指向新节点，让新节点指向原位置节点的后一个节点。这个过程类似于铁链中加入铁环的过程，要保证新铁环和原来的两个铁环相连接。
def insert(self, position, data):
"""在任意位置插入节点
Args:
position:插入节点的位置,int
data:插入节点的值
"""
if not isinstance(position, int):
raise ValueError("expect type is 'int', but got {}".format(position.__class__))
# 头插法
if position <= 0:
self.add(data)
# 尾插法
elif position > self.get_length():
self.append(data)
else:
current = self.__head
current_position = 0
node = Node(data)
# 目的：计算出插入位置
while current_position < position -1:
current_position += 1
current = current.pointer
# 首先：必须使得当前节点的pointer指针指向新建的node
# 其次：必须保证新建的node的pointer指向当前节点的后一个节点
node.pointer = current.pointer
current.pointer = node（7）计算链表长度：get_length()函数
对于调用者和类内部的其它函数来做，链表长度是一个非常有用的值。比如在插入函数insert()中，需要判断插入位置是不是大于链表长度。
计算链表长度的实现比较简单，只需要遍历链表的所有节点，并用计数器来统计节点的数目即可。
def get_length(self): """ 获取链表的长度""" # 没有任何node if self.__head == None: return 0 # 节点数统计 else: current = self.__head length = 0 while current != None: current = current.pointer length += 1 return length
（8）遍历所有节点：traversal()函数
链表、树、图等结构都需要遍历操作，其中链表的遍历比较简单，只需要依次的访问所有节点即可。
def traversal(self):
current = self.__head
i = 0
# 循环结束的条件依旧是节点的pointer指向不为空
while current != None:
print("Element {} is {} ".format(i, current.data))
current = current.pointer
i += 1（9）搜索：search()函数
前面提到搜索有按值搜索和按位置搜索两种，它们的原理和实现都十分相似，所以仅以按值搜索为例。
需要注意的是，insert()函数需要判断链表是否为空，并且需要考虑到目标值不在链表中的情况，分别对应不同的返回值。
def search(self, data): """ 返回值为data的第一个节点""" if self.__head == None: return -1 else: current = self.__head current_position = 0 # 遍历节点 while current != None: # 目标值搜索成功 if current.data == data: return current_position # 目标值搜索不到则继续搜索 else: current_position += 1 current = current.pointer # 目标值不存在于链表中 return False
（10）删除：delete()函数
上述的查找中以“按值查找”为例，这次删除中同样以“按值删除”为例，“按位置删除”的实现与之类似。
按值删除，即删除目标值对应的目标节点。在进行遍历时，需要记录当前节点和当前节点的前一个节点。因为，一旦查找大目标值所在的目标节点，需要令目标节点的前一个节点指向目标节点的下一个节点，即完成节点的删除。
def delete(self, data): """ 删除值为data的第一个节点""" if self.is_empty(): return None # 记录当前节点和前一个节点 current = self.__head piror = None while current != None: # 查找成功分为两种情况 if current.data == data: # 目标节点为头结点 if current == self.__head: self.__head = self.__head.pointer return True # 目标节点不是头结点 # 令目标节点的前一个节点指向目标节点的后一个节点 else: piror.pointer = current.pointer return True # 更新当前节点和前一个节点 else: piror = current current = current.pointer return False
2.C++实现
前面的python实现中已经分析了各个函数的作用，以及对应的实现过程。虽然python和C++的语法不同，但是核心过程是类似的，所以下面不再重复对过程的叙述。
（1）节点设计
由于C++的指针必须指定类型，所以需要使用空指针NULL作为pointer的值。
class Node{
public:
int data;
Node *pointer=NULL;
};（2）链表类：SingleLinkedList
遵循声明和实现分类的策略，先对各个函数进行声明。
class SingleLinkedList {
public:
SingleLinkedList();
bool isEmpty();
int getLength();
void add(int data);
void append(int data);
void insert(int position, int data);
void traversal();
int search(int data);
void remove(int data);
private:
Node *head;
};（3）判断链表是否为空：isEmpty()函数
bool SingleLinkedList::isEmpty() {
// 头结点不指向任何结点，为空
if (head->pointer == NULL) {
return true;
}
else {
return false;
}
}（4）头插法：add()函数
void SingleLinkedList::add(int data) {
// 当原列表仅有头结点时，直接插入新节点即可
if (head->pointer == NULL) {
head->pointer = new Node;
head->pointer->data = data;
}
// 当原列表头结点后面含有后继节点时
// 令头结点直接后继为新节点
// 并令新节点的直接后继为原来头结点的直接后继
else {
// 临时存储头结点的直接后继
Node *temp = head->pointer;
head->pointer = new Node;
head->pointer->data = data;
head->pointer->pointer = temp;
}
}（5）尾插法：append()函数
void SingleLinkedList::append(int data) {
Node *current = head->pointer;
// 找到列表的最后一个节点的位置current
// current的指针域为NULL
while (current->pointer!=NULL)
{
current = current->pointer;
}
// 令current的指针域指向新节点，完成插入
current->pointer = new Node;
current->pointer->data = data;
}（6）在任意位置插入：insert()函数
void SingleLinkedList::insert(int position, int data) {
// 头插法
if (position <= 0) {
add(data);
}
// 尾插法
else if (position > getLength()){
append(data);
}
else {
// 令头指针所在的位置为0
int current_position = 0;
Node *current = head;
Node *prior = NULL;
// 查找目标节点位置current，并记录其直接前驱节点piror
while (current_position<position)
{
// 更新当前节点和直接前驱
prior = current;
current = current->pointer;
current_position++;
}
// 目标位置的直接前驱prior指向新节点
// 新节点指向目标位置的节点
prior->pointer = new Node;
prior->pointer->data = data;
prior->pointer->pointer = current;
}
};（7）计算链表长度：getLength()函数
int SingleLinkedList::getLength() {
int counter = 0;
Node *current = head;
// 遍历链表，直到最后一个元素
while (current->pointer!=NULL)
{
counter++;
current = current->pointer;
}
return counter;
}（8）遍历所有节点：traversal()函数
void SingleLinkedList::traversal() {
Node *current;
// 指向头结点的直接后继
current = head->pointer;
int counter = 1;
// 遍历链表，输出每个节点的值
while (current!=NULL)
{
printf("Element in %d is %d \n", counter, current->data);
counter++;
current = current->pointer;
}
}（9）搜索：search()函数
int SingleLinkedList::search(int data) {
int current_position = 1;
Node *current = head->pointer;
while (current!=NULL)
{
// 搜索成功返回当前位置
if (current->data == data) {
return current_position;
}
// 继续更新位置；
current = current->pointer;
current_position++;
}
// 搜索失败，返回-1
return -1;
}（10）删除：remove()函数
void SingleLinkedList::remove(int data) {
Node *current = head->pointer;
Node *prior = head;
// 遍历链表
while (current!=NULL)
{
// 查找到目标位置
if (current->data == data) {
// 令目标位置的直接前驱指向目标节点的直接后继
prior->pointer = current->pointer;
break;
}
// 更新当前节点和其前驱节点
prior = current;
current = current->pointer;
}
}总结：
在使用python实现时，头结点数据域data是有效的。这种方式使得代码中需要很多的“if-else”判断结构，增加了代码的复杂性。
在使用C++实现时，头结点数据域data是无效的，这种方式使得代码更加简洁。
加载全部内容