python数据结构实现—链表

看到一篇写的不错的讲解python链表的文章，自己经过学习后，总结一下：
参考链接1：https://segmentfault.com/a/1190000010819283
参考链接2：https://blog.****.net/weixin_39561100/article/details/79818949
感谢！

1. 简单介绍

链表(Linked list)是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。—— 维基百科

链表的基本构造块是节点(Node)。我们通过Python实现一个简单的Node类。
一个单向链表的构造如下图1所示包含两个域：

1. 信息域：当前节点的值(Data or Value)
2. 指针域：指向下一个节点的指针链接(Reference or Link)

注1:必须明确指定链表的第一项的位置。一旦我们知道第一项在哪里，第一项目可以告诉我们第二项是什么，依次类推。按照一个方向遍历，直到最后一项（最后一个节点），最后一项需要知道没有下一项。
注2:这些节点在逻辑上是相连的，但要知道它们在物理内存上并不相连。

2. 实现

2.1 Node类

class Node(object):
    def __init__(self, initdata):
        self.data = initdata
        # 引用None代表没有下一节点
        self.next = None
    # 获得数据
    def getData(self):
        return self.data
    # 获得下一个节点的引用
    def getNext(self):
        return self.next
    # 修改数据
    def setData(self, newdata):
        self.data = newdata
    # 修改下一节点的引用
    def setNext(self, newnext):
        self.next = newnext

创建一个node对象：

>>> tmp = Node(33)
>>> tmp
<__main__.Node object at 0x1022699b0>
>>> tmp.getData()
33

2.2 Unordered List类

只要知道第一个节点（包含第一个项），那么之后的每个节点都可以通过指向下一个节点的链接 依次找到。考虑到这样的情况，Unordered List类只要维护对第一个节点的引用就可以了。Unordered List类本身不包含任何节点对象，它只包含对链表结构中第一个节点的单个引用！

class unOrderedList():
    def __init__(self):
        # 初始化None表示此时链表的头部不引用任何内容
        self.head = None

创建一个空链表：

>>> myList = unOrderedList()

2.2.1 isempty()函数检查空链表

    #检查是否为空链表
    def isEmpty(self):
        return self.head == None

2.2.1 add()在链表前端添加元素

由于是在前端添加，因此最后添加的在最前端。

    #add()在链表前端添加元素
    def add(self, item):
        temp = Node(item) #第一步：创建一个新节点，并将新项作为数据
        temp.setNext(self.head) #第二步：更改新节点的下一个引用以引用旧链表的第一个节点
        self.head = temp #第三步：重新设置链表的头以引用新节点

添加元素——执行mylist.add(26)时候的图解如下:

>>> mylist.add(31)
>>> mylist.add(77)
>>> mylist.add(17)
>>> mylist.add(93)
>>> mylist.add(26)

2.2.2 size()求链表长度

    #size()用于计算链表长度，通过current遍历节点并计数
    def size(self):
        current = self.head
        count = 0
        while current != None:
            current = current.getNext() #获得下一个节点的引用
            count += 1
        return count

通过current遍历链表并对节点计数。图解如下：

2.2.3 search()查找

def search(self, item):
    current = self.head
    found = False
    while current != None and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()
    return found

通过current遍历链表，使用found标记是否找到了正在寻找的项。
图解如下:

2.2.4 remove()删除

    #remove()删除链表节点
    def remove(self, item):
        current = self.head
        found = False
        previous = None
        while not found:
            if current.getValue() == item: #找到节点
                found = True
            else:
                previous = current
                current = current.getNext() # current遍历链表
        if previous == None: #特殊情况：如果要删除的是第一个节点，直接将head指向下一个节点的引用
            self.head = current.getNext() 
        else:
            previous.setNext(current.getNext()) #先前节点的引用更改为当前节点的下一个节点

上面的特殊情况，即要删除的恰好是第一个节点的图解如下：

其他情况，即要删除的是链表中的节点（非第一个）：
我们遍历链表，先搜索，再删除。
1.搜索：
使用previous与current进行移动，借助found标记是否找到。
一旦found为True，current就是对包含要删除的项的节点的引用。
2.删除（修改引用）：
我们把previous的对下一节点的引用设为current的下一节点。
以上两过程的图解如下：

3. 反转链表

对于一个单链表，反转链表后，输出链表的所有元素

3.1 循环实现

循环实现的基本思路是：
1、遍历取出每一个节点，将上一次取出的节点作为当前取出节点的引用
假设初始链表：

循环之前各链表的状态：

cur = pHead
newHead = None
tmp = None

第一次循环：

tmp = cur.next #将tmp保存为cur下一个节点的引用 
cur.next = newHead #此时newHead是None，这一步改变了cur
newHead = cur #将a这个节点取出来，其next为None
cur = tmp #恢复cur

第二次循环：

第三次循环：

第四次循环：

此时cur为空链表，退出while循环。返回newHead链表，即原链表的反转链表。
完整代码（不改变原链表）：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead == None or pHead.next == None:
            return pHead  
        cur = pHead 
        tmp = None
        newhead = None  
        while cur:  
            tmp = cur.next   
            cur.next = newhead  
            newhead = cur
            cur = tmp  
        return newhead

改变原链表：

    if not pHead or not pHead.next:
        return pHead
    NewHead = self.ReverseList(pHead.next)
    pHead.next.next = pHead
    pHead.next = None
    return NewHead

#  可以修改原链表的话，更简单
class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head and not head.next:
        	return head
        Node = None
        while head:
        	#tmp = head.next
        	#head.next = Node
        	#Node = head
        	#head = tmp
        	p = head
        	head = head.next
        	p.next = Node
        	Node = p
        return Node

3.1 递归实现

class Solution:
    # 返回ListNode
    def recurse(head,newhead = None):    #递归，head为原链表的头结点，newhead为反转后链表的头结点
		if head is None:
			return 
		if head.next is None:
			newhead=head
		else :
			newhead=recurse(head.next,newhead)
			head.next.next=head
			head.next=None
		return newhead   

假设原始1-2-3-4；
第一次调用recurse，此时（head $\to$→ 1, newhead =None）:
运行到else，第二次调用recurse，此时（head $\to$→ 2, newhead =None）:
运行到else，第三次调用recurse，此时（head $\to$→ 3, newhead =None）:
运行到else，第四次调用recurse，此时（head $\to$→ 4, newhead =None）:
满足if head.next is None:，运行newhead=head，返回newhead，第四次调用recurse结束，newhead指向4；
此时head $\to$→ 3，运行head.next.next=head，head $\to$→ 3 $\to$→ 4 $\to$→ 3（闭环）；
运行head.next=None，断开变成：head $\to$→ 3 和 newhead $\to$→ 4 $\to$→ 3;
返回newhead $\to$→ 4 $\to$→ 3，第三次调用结束；
此时head $\to$→ 2，因为原链表已经断开，head $\to$→ 2 $\to$→ 3， 运行head.next.next=head，head $\to$→ 2 $\to$→ 3 $\to$→ 2（闭环）；（两个链表相交于3）
运行head.next=None，断开变成：head $\to$→ 2 和 newhead $\to$→ 4 $\to$→ 3 $\to$→ 2;
返回newhead $\to$→ 4 $\to$→ 3 $\to$→ 2;，第二次调用结束；
此时head $\to$→ 1，因为原链表已经断开，head $\to$→ 1 $\to$→ 2， 运行head.next.next=head，head $\to$→ 1 $\to$→ 2 $\to$→ 1（闭环）；（两个链表相交于3）
运行head.next=None，断开变成：head $\to$→ 1 和 newhead $\to$→ 4 $\to$→ 3 $\to$→ 2 $\to$→ 1 ;
返回newhead $\to$→ 4 $\to$→ 3 $\to$→ 2 $\to$→ 1 ，第一次调用结束；
即最后返回新链表head：newhead：newhead $\to$→ 4 $\to$→ 3 $\to$→ 2 $\to$→ 1。