单链表的 Python 实现

一、节点

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

class Node(object):
    def __init__(self, data, next=None):
        """包含一个数据域，一个 next 域的节点，next 是对下一个数据的引用
        """
        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("--------")

A/B

单链表的Python实现（列表实现）

单链表的 Python 实现

一、节点

二、单链表

Search

Table of Contents