链表的Python实现与实例分析

妖狐艹你老母 2022-05-31 11:52 222阅读 0赞

链表(Linked List)，是一种在逻辑上连续，但在物理存储单元上不一定连续的线性存储结构。包括存储数据元素的数据域和存储下一个节点地址的指针域。

在存储结构中，有顺序存储的数组(Array List)，为什么还要链表呢？因为在有些情况下，Linked List相对Array List是有优势的

1.  你的应用不会随机访问数据。因为如果你需要Linked List中的第n个元素的时候，你需要从第一个元素顺序数到第n个数据，然后读取数据。此时的复杂度为O(n)，而对于Array List是O(1)。
2.  你的应用更多的插入和删除元素，更少的按索引读取数据（如果只是遍历，区别不大）。因为插入和删除元素不涉及重排数据，其复杂度为O(1)，而 Array List 为O(n)。

### Python实现 ###

在 Python 中，虽然没有显式的指针，但每个变量，除了基本数据类型（int，float 等），都是一个『引用』。因此，链表可以通过定义节点类和引用来实现。

节点类中包括节点数据和下一个节点地址，即引用

链表类中则是链表的各种操作，下面给出单链表的Python实现，并给出向链表添加节点的操作

# @Author: 郭 璞
    # @blog: http://blog.csdn.net/marksinoberg
    
    class Node:
        def __init__(self, data, next):
            self.data = data
            self.next = next
    
    class LianBiao:
        def __init__(self):
            self.root = None
    
        # 给单链表添加元素节点
        def addNode(self, data):
            newNode = Node(data=data, next=None)
            if self.root==None:
                self.root = newNode
            else:
                # 有头结点，则需要遍历到尾部节点，进行链表增加操作
                cursor = self.root
                while cursor.next!= None:
                    cursor = cursor.next
                cursor.next = newNode

注：代码参考自博客：[Python 实现一个全面的单链表][Python]，该博客中还有更多的操作，可以借鉴并尝试自己去实现一下

### 应用实例 ###

约瑟夫问题：n个人围成一个圈，每个人分别标注为1、2、…、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。

解约瑟夫问题的一种方法是模拟这个过程，模拟的载体可以是队列，也可以是链表

在专栏文章 [队列的Python实现][Python 1] 中，用队列以一个简单的实例求解了这个问题。

如果需要用链表解决该问题，则需要循环链表，即最后一个节点接头结点。相对于队列，循环链表的差异在于不需要频繁的入队出队，只需要一直循环遍历链表，把第k个节点删除直至留下最后一个节点。

在单链表的基础上，只要将最后一个节点链接上头结点即实现循环链表

#循环链表解决约瑟夫问题
    class Node:
        def __init__(self, data):
            self.data = data
            self.next = None
    
    class LoopLinkedList:
        def __init__(self):
            self.root = None
    
        # 在循环链表尾部添加节点，尾部即头结点上一个
        def addNode(self, data):
            newNode = Node(data)
            if self.root==None:
                self.root = newNode
            else:
                cursor = self.root
                while cursor.next!= self.root:
                    cursor = cursor.next
                cursor.next = newNode
            newNode.next=self.root      #链接成环
    
        #链表长度
        def size(self):
            if self.root == None:
                return 0
            cursor = self.root
            i=1
            while cursor.next != self.root:
                i+=1
                cursor = cursor.next
            return i
    
    #约瑟夫问题仿真函数
    def circle(num,nameList):
        linkedList=LoopLinkedList()
        for i in range(len(nameList)):
            linkedList.addNode(nameList[i])
        i=1
        pre = linkedList.root
        cursor = linkedList.root
        while linkedList.size()!=1:
            if i!=num:
                pre=cursor
                cursor=cursor.next
                i+=1
            else :
                pre.next=cursor.next    #删除当前节点需要用上一个节点连接下一个节点
                cursor=pre.next
                linkedList.root=cursor  #重新选择头结点是为了计算链表长度
                i=1
        return cursor.data
    
    #主函数
    if __name__=='__main__':
        nameList=["Bill","David","Susan","Jane","Kent","Brad"]
        print(circle(7,nameList))
    #输出结果
    Kent

[Python]: http://blog.csdn.net/marksinoberg/article/details/69310033
[Python 1]: http://blog.csdn.net/songyunli1111/article/details/79344594