单链表的Python实现

悠悠 2022-05-28 02:20 200阅读 0赞

# 单链表的Python实现 #

## 一、节点 ##

节点，即C语言里使用struct语句定义的一种非基础数据类型，在Python中，定义一个class类。

class Node(object):
    '''包含一个数据域，一个next域的节点，next是对下一个数据的引用'''
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    
    
    class TwoWayNode(Node):
    '''继承Node类的双指针节点类，新包含一个previous的引用'''
    def __init__(self, data, previous=None, next=None):
        Node.__init__(self, data, next)
        self.previous = previous
    
    
    def main():
        pass
    
    if __name__ == "__main__":
        main()

## 二、单链表 ##

单链表，指的是由多个节点形成的链式结构，一个节点包括一个数据域及一个next域。  
除头结点外，每个节点都有且仅有一个前驱；除尾节点外，每个节点有且仅有一个后继。  
ADT思想（忽略）。  
定义一个单链表类，依次给出以下的方法：  
\* 1、 在首部插入节点  
\* 2、在尾部插入节点  
\* 3、在任意位置插入节点  
\* 4、从首部删除节点  
\* 5、从尾部删除节点  
\* 6、从任意位置删除节点  
\* 7、遍历输出  
\* 8、根据数值查找单链表中是否存在项，返回True or False及索引位置  
\* 9、根据给出的索引替换掉相应位置的值

from node import Node
    
    class SingleList(object):
    '''以节点的方式实现链表，默认实现空列表'''
        def __init__(self):
            self.head = None
    
        # 在开始处插入
        def add_node_first(self, data):
            self.head = Node(data, self.head)
    
        # 在末尾插入，若为空列表则直接插入，否则遍历到尾部
        def add_node_last(self, data):
            new_node = Node(data)
            if self.head is None:
                self.head = new_node
            else:
                probe = self.head
                while probe.next is not None:
                    probe = probe.next
                probe.next = new_node
    
        # 任意位置添加节点，若index小于零，加在首部，若index大于链表长度，加在尾部
        def add_node_anywhere(self, index, data):
            if self.head is None or index <= 0:
                self.head = Node(data, self.head)
            else:
                probe = self.head
                while index >1 and probe.next is not None:
                    probe = probe.next
                    index -= 1
                probe.next = Node(data, probe.next)
    
        # 从首部删除节点
        def pop_node_first(self):
            if self.head is not None:
                removed_item = self.head.data
                self.head = self.head.next
                return removed_item
            else:
                return -1
    
        # 从尾部删除节点
        def pop_node_last(self):
            if self.head is None:
                return -1
            elif self.head.next is None:
                removed_item = self.head.data
                self.head = None
            else:
                probe = self.head
                while probe.next.next is not None:
                    probe = probe.next
                removed_item = probe.next.data
                probe.next = None
            return removed_item
    
        # 任意位置删除节点，若index小于零，则删除首部节点，若index大于链表长度，则删除尾部节点
        def pop_node_anywhere(self, index):
            if index <= 0 or self.head.next is None:
                removed_item = self.head.data
                self.head = self.head.next
                return removed_item
            else:
                probe = self.head
                while index > 1 and probe.next.next is not None:
                    probe = probe.next
                    index -= 1
                removed_item = probe.next.data
                probe.next = probe.next.next
                return removed_item
    
        # 遍历输出
        def traverse(self):
            probe = self.head
            while probe is not None:
                print(probe.data)
                probe = probe.next
    
        # 根据数值查找链表有没有该数据
        def search(self, data):
            probe = self.head
            cnt = 0
            while probe is not None and data != probe.data:
                probe = probe.next
                cnt += 1
            if probe is not None:
                return "In", cnt
            else:
                return "Not in", -1
    
        # 根据索引位置替换数据
        def replace(self, index, new_data):
            probe = self.head
            while index > 0 and probe is not None:
                probe = probe.next
                index -= 1
            if probe is None:
                return -1
            else:
                probe.data = new_data
                return "Done"
    
    
    # 测试用例
    a = SingleList()
    a.add_node_first(1)
    a.add_node_first(2)
    a.add_node_first(3)
    print(a.search(2))
    a.add_node_first(4)
    a.add_node_last(5)
    a.add_node_first(6)
    a.add_node_anywhere(100,33)
    a.pop_node_anywhere(2)
    a.traverse()
    
    print("--------")