面相对象（三）：模拟链表

面向对象的基本原理是对对象建模，让抽象的逻辑封装成具象的行为，更方便人们理解和使用。在前面的文章中我写了关于继承的一些理解，一般来说这里应该讨论与继承同为面向对象三个主要特征的多态与封装了。但是我想多态与封装是一种伴随着类的定义自然而然形成的现象，只有先接触了一定数量的类对象，我们才能更好地理解多态；也只有对一个类有了切实的应用，才能更好体会封装的精妙。因此，这些内容不会直接出现在这里。今天我希望分享的是如何去运用类创建一个链表。

链表由一系列结点（链表中每一个元素称为结点）组成，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

以上是百度百科中关于链表的描述。需要说明的是，在本文中，我们只讨论最基础的单向无循环链表，实际业务中，链表可能会比基础形态更加复杂。链表的每个结点，都只有一个前驱结点和一个后继结点，因此会形成一个结点串。
链表的优点是，由于只需要更改结点的地址域就可以实现元素的插入和删除，不需要像列表一样对更改之后的全部元素索引进行整体调整，因此在进行这两个操作时较为高效。与普通列表相比，链表利用了内存中的零碎空间，将整个表格分成一个个的结点，分别存到内存空着的地方，因此在处理内存空间时比较灵活。但是缺点是由于链表不存储索引，当需要取出固定位置的元素值时，链表必须从头开始按图索骥，来找到目标，这意味着链表的查改效率相对不高。实践中，我们会根据业务需求进行使用。

现在让我们来建模一个最基础的单向无循环链表。

1. 定义结点
   显然，链表中的结点可以被建模成一个类。这个类应该有两个属性，即数值域和地址域。单个结点在创建时应该输入数值域，而地址域则应该赋值为None，因为他还没有被加入到链表中。

点击查看代码

class SingleNode(object):def __init__(self, data):self.item = dataself.next = None

1. 定义整条链表
   有了结点，我们就有了形成链表的基本单位。链表对象应该拥有一些行为可以让我们来操作这些结点。但是首先，我们必须要有结点。所在在创建链表对象时，先应该传入第一个结点对象，并将其设置为我们的头结点（即链表开始的地方）。头结点会在每次链表被访问时第一个被访问到，在单向无循环链表中，没有结点的地址域会指向头结点。

点击查看代码

class SingleLinkedList(object):def __init__(self,node=None):self.head = node  # 将传入的节点作为头节点

2. 为链表添加功能-头插法与尾插法
   头插法是指在链表头部添加结点，而尾插法恰恰相反。注意我们每次插入一个值，都是要将其先实例化为一个结点，之后才可以进行操作。

点击查看代码

    def add(self,item):              # 头插法new_node = SingleNode(item)  # 创建新节点new_node.next = self.head    # 将新节点的next指针指向原本的头节点self.head = new_node         # 并将新节点作为头节点def append(self,item):           # 尾插法new_node = SingleNode(item)cur = self.head              # 将当前结点定位到头结点while cur:                   # 遍历链表，找到最后一个节点if cur.next ==None:cur.next = new_node  # 将新节点添加到链表尾部breakelse:cur = cur.nextelse:self.head = new_node    # 如果没有进入while循环，说明头结点为空，则直接将新节点作为头节点

3. 为链表添加功能-遍历与查看链表长度
   遍历链表只需要按顺序输出每个结点的数值域，并顺着地址域找到下一个结点即可。
   查看长度在此基础上进行统计即可。

点击查看代码

    def length(self):      # 计算链表长度cur =self.headcount = 0while cur:         # 由于初始条件为count=0，每次拿到一个非空结点之后count+1，并将cur指向下一个结点即可 count += 1    cur = cur.nextreturn countdef travel(self):        # 遍历链表cur = self.headwhile cur:print(cur.item)cur = cur.next

4. 为链表添加功能-在指定位置插入值
   正常情况下在指定位置插入值只需要将原本位于此处的结点地址域打开，并将新的结点接入即可。

点击查看代码

    def insert(self,pos,item):if pos <= 0:self.add(item)elif pos > self.length():self.append(item)else:count =0cur = self.headwhile count < pos-1:        # 通过循环找到插入位置的前一个节点count += 1cur = cur.nextnew_node = SingleNode(item)new_node.next = cur.next    # 将新节点的next指针指向原本的cur节点的下一个节点cur.next = new_node         # 将原本的cur节点的next指针指向新节点

5. 为链表添加功能-删除指定值
   删除值的操作一般不需要指定位置，而是通过值来判断。最基础的情况下，我们只删除找到的第一个结点，并将他前一个结点的地址域直接指向它的下一个结点，以此来让这个结点处于无法被找到的状态（但他并未被从内存中删除）

点击查看代码

    def remove(self,item):cur = self.headif cur ==None:             # 如果链表为空，则直接返回print(f'链表为空，不存在{item}')returnelif cur.item == item:     # 如果头节点就是要删除的节点，则直接将头节点指向下一个节点self.head = cur.nextreturncount =0while cur:count +=1pre = cur              # 用pre记录前一个节点cur = cur.nextif cur.item ==item:pre.next =cur.next  # 将pre节点的next指针指向cur节点的下一个节点returnprint(f'未找到{item}')       # 如果没有找到要删除的节点，则打印提示信息

6. 为链表添加功能-搜寻某个值是否在链表中
   此功能较为简单，就不再补充代码。

以上，就是对于链表的建模，实现了链表的基本功能。