当前位置：首页 > 文章列表 > 数据库 > MySQL > 四种常见链表的实现及时间复杂度分析（Python3版）

四种常见链表的实现及时间复杂度分析（Python3版）

来源：SegmentFault 2023-02-24 20:00:00 0浏览收藏

编程并不是一个机械性的工作，而是需要有思考，有创新的工作，语法是固定的，但解决问题的思路则是依靠人的思维，这就需要我们坚持学习和更新自己的知识。今天golang学习网就整理分享《四种常见链表的实现及时间复杂度分析（Python3版）》，文章讲解的知识点主要包括区块链、MySQL、Linux、python、人工智能，如果你对数据库方面的知识点感兴趣，就不要错过golang学习网，在这可以对大家的知识积累有所帮助，助力开发能力的提升。

四种常见的链表包括：单向链表，单向循环链表，双向链表，双向循环链表。
要实现的链表操作包括

class Node(object):
    """单节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None


class DoubleNode(Node):
    """双节点"""

    def __init__(self, elem):
        super(DoubleNode, self).__init__(elem)
        self.prev = None

四种链表的实现中，每一个类都继承自

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# __author__ = 'zhao zi yang'

class Node(object):
    """单节点"""

    def __init__(self, elem):
        self.elem = elem
        self.next = None


class DoubleNode(Node):
    """双节点"""

    def __init__(self, elem):
        super(DoubleNode, self).__init__(elem)
        self.prev = None


class SingleLinkList(object):
    """单链表"""

    def __init__(self, node=None):
        self.head = node

    def is_empty(self) -> bool:
        """链表是否为空 O(1)"""
        return self.head is None

    def length(self) -> int:
        """链表长度 O(n)"""
        count, cur = 0, self.head
        while cur is not None:
            cur = cur.next  # 不要写错cur = self.head.next, self.__next不是活动指针
            count += 1
        return count

    def traversing(self) -> '':
        """遍历所有节点 O(n)"""
        cur = self.head  # 不是 self._head
        while cur is not None:
            print(cur.elem, end=' ')
            cur = cur.next
        return ''

    def add(self, item) -> None:
        """头部添加节点 O(1)"""
        node = Node(item)
        node.next = self.head
        self.head = node

    def append(self, item) -> None:
        """尾部添加节点 O(n)"""
        node = Node(item)
        cur = self.head
        if self.is_empty():
            self.head = node
        else:
            while cur.next is not None:
                cur = cur.next
            cur.next = node

    def insert(self, position: int, item) -> None:
        """
        节点插入到某个位置 O(n)
        :param position: 0表示第1个位置
        :param item:
        :return: None
        """
        if position = self.length():
            self.append(item)
        else:
            node = Node(item)
            count, cur = 1, self.head
            while count  None:
        """删除链表中的一个节点 O(n)"""
        pre, cur = None, self.head
        while cur is not None:
            if cur.elem == item:
                if cur == self.head:
                    self.head = cur.next
                    break  # 只remove第一个元素
                pre.next = cur.next
                break
            pre = cur
            cur = cur.next

    def search(self, item) -> bool:
        """查找节点是否存在 O(n)"""
        cur = self.head
        while cur is not None:
            if cur.elem == item:
                return True
            cur = cur.next
        return False


class SingleCycleLinkList(SingleLinkList):
    """单向循环链表"""

    def __init__(self, node=None):
        if node:
            node.next = node
        super(SingleCycleLinkList, self).__init__(node=node)

    def length(self) -> int:
        """链表长度 O(n)"""
        if self.is_empty():
            return 0
        count, cur = 1, self.head
        while cur.next != self.head:
            cur = cur.next  # 不要写错cur = self.head.next, self.__next不是活动指针
            count += 1
        return count

    def traversing(self) -> '':
        """遍历所有节点 O(n)"""
        if not self.is_empty():
            cur = self.head  # 不是 self._head
            while cur.next != self.head:
                print(cur.elem, end=' ')
                cur = cur.next
            print(cur.elem, end=' ')
        return ''

    def add(self, item) -> None:
        """头部添加节点 O(n)"""
        node = Node(item)
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            # 退出while循环之后cur指向尾结点
            node.next = self.head
            self.head = node
            cur.next = self.head

    def append(self, item) -> None:
        """尾部添加节点 O(n)"""
        node = Node(item)
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = node
            node.next = self.head

    def insert(self, position: int, item) -> None:
        """
        节点插入到某个位置 O(n)
        :param position: 0表示第1个位置
        :param item:
        :return: None
        """
        if position = self.length():
            self.append(item)
        else:
            node = Node(item)
            count, cur = 1, self.head
            while count  None:
        """删除链表中的一个节点 O(n)"""
        if self.is_empty():
            return
        pre, cur = None, self.head
        while cur.next != self.head:
            if cur.elem == item:
                # 移除头结点
                if cur == self.head:
                    rear = self.head
                    while rear.next != self.head:
                        rear = rear.next
                    self.head = cur.next
                    rear.next = self.head
                # 移除中间节点
                else:
                    pre.next = cur.next
                return  # 结束。只remove第一个元素
            pre = cur
            cur = cur.next
        # 移除尾结点
        if cur.elem == item:
            if cur == self.head:
                self.head = None
            else:
                pre.next = self.head  # 或者 pre.next = cur.next

    def search(self, item) -> bool:
        """查找节点是否存在 O(n)"""
        if self.is_empty():
            return False
        else:
            cur = self.head
            while cur.next != self.head:
                if cur.elem == item:
                    return True
                cur = cur.next
            return cur.elem == item


class DoubleLinkList(SingleLinkList):
    """双链表"""

    def add(self, item) -> None:
        """头部添加节点 O(1)"""
        node = DoubleNode(item)
        node.next = self.head
        self.head = node
        if node.next:  # 当原链表为空时
            node.next.prev = node

    def append(self, item) -> None:
        """尾部添加节点 O(n)"""
        node = DoubleNode(item)
        cur = self.head
        if self.is_empty():
            self.head = node
        else:
            while cur.next is not None:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self, position: int, item) -> None:
        """
        节点插入到某个位置 O(n)
        :param position: 0表示第1个位置
        :param item:
        :return: None
        """
        if position = self.length():
            self.append(item)
        else:
            node = DoubleNode(item)
            count, cur = 1, self.head
            while count  None:
        """删除链表中的一个节点 O(n)"""
        cur = self.head
        while cur is not None:
            if cur.elem == item:
                if cur == self.head:
                    self.head = cur.next
                    if self.head:  # 只有一个节点的特殊情况
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    if cur.next:
                        cur.next.prev = cur.prev
                break  # 只remove第一个元素
            cur = cur.next


class DoubleCycleLinkList(SingleCycleLinkList):
    """双向循环链表"""

    def __init__(self, node=None):
        if node:
            node.next = node
            node.prev = node
        super(DoubleCycleLinkList, self).__init__(node=node)

    def add(self, item) -> None:
        """头部添加节点 O(n)"""
        node = DoubleNode(item)
        if self.is_empty():
            self.head = node
            node.next = node
            node.prev = node
        else:
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            # 退出while循环之后cur指向尾结点，双向循环链表需要改动5个指针
            node.next = self.head  # 1.node.next指向原来的头结点
            node.prev = cur  # 2.node.prev指向尾结点，当前cur指向的节点
            cur.next.prev = node  # 3.原来头结点的prev指向要插入的node
            self.head = node  # 4.self.head指向要插入的node
            cur.next = node  # 5.尾结点的next指向要插入的node

    def append(self, item) -> None:
        """尾部添加节点 O(n)"""
        node = DoubleNode(item)
        if self.is_empty():
            self.head = node
            node.next = node
            node.prev = node
        else:
            cur = self.head
            # 退出while循环之后cur指向尾结点，双向循环链表需要改动4个指针
            while cur.next != self.head:
                cur = cur.next
            cur.next.prev = node  # 1.原来头结点的.prev指向要插入的node
            cur.next = node  # 2.原来尾结点.next指向要插入的node
            node.prev = cur  # 3.node.prev指向原来的尾节点
            node.next = self.head  # 4.node.next指向头结点

    def insert(self, position: int, item) -> None:
        """
        节点插入到某个位置 O(n)
        :param position: 0表示第1个位置
        :param item:
        :return: None
        """
        if position = self.length():
            self.append(item)
        else:
            node = DoubleNode(item)
            count, cur = 1, self.head
            while count  None:
        """删除链表中的一个节点 O(n)"""
        if self.is_empty():
            return
        cur = self.head
        while cur.next != self.head:
            if cur.elem == item:
                # 移除头结点
                if cur == self.head:
                    cur.prev.next = cur.next
                    cur.next.prev = cur.prev
                    self.head = cur.next
                # 移除中间节点
                else:
                    cur.prev.next = cur.next
                    cur.next.prev = cur.prev
                return  # 结束。只remove第一个元素
            cur = cur.next
        # 移除尾结点
        if cur.elem == item:
            if cur == self.head:  # 当链表只有一个节点时
                self.head = None
            else:
                cur.next.prev = cur.prev
                cur.prev.next = cur.next


if __name__ == '__main__':
    print("----single_link_list-----")
    single_link_list = SingleLinkList()
    single_link_list.remove('test')
    print(single_link_list.is_empty(), single_link_list.length())
    single_link_list.insert(-1, 'zhao')
    print(single_link_list.is_empty(), single_link_list.length())
    single_link_list.insert(3, 'zi')
    print(single_link_list.length())
    single_link_list.append('yang')
    single_link_list.add("head")
    single_link_list.insert(4, "tail")
    print(single_link_list.traversing())
    single_link_list.remove(1)
    print(single_link_list.traversing())
    single_link_list.remove("head")
    print(single_link_list.traversing())
    single_link_list.remove("tail")
    print(single_link_list.traversing())
    single_link_list.remove('zi')
    print(single_link_list.traversing())

    print("\n----single_cycle_link_list-----")
    single_cycle_link_list = SingleCycleLinkList()
    single_cycle_link_list.remove('test')
    print(single_cycle_link_list.is_empty(), single_cycle_link_list.length())
    single_cycle_link_list.insert(-1, 'zhao')
    print(single_cycle_link_list.is_empty(), single_cycle_link_list.length())
    single_cycle_link_list.insert(3, 'zi')
    print(single_cycle_link_list.length())
    single_cycle_link_list.append('yang')
    single_cycle_link_list.add("head")
    single_cycle_link_list.insert(4, "tail")
    print(single_cycle_link_list.traversing())
    single_cycle_link_list.remove(1)
    print(single_cycle_link_list.traversing())
    single_cycle_link_list.remove("head")
    print(single_cycle_link_list.traversing())
    single_cycle_link_list.remove("tail")
    print(single_cycle_link_list.traversing())
    single_cycle_link_list.remove('zi')
    print(single_cycle_link_list.traversing())

    print("\n----double_link_list-----")
    double_link_list = DoubleLinkList()
    double_link_list.remove('test')
    print(double_link_list.is_empty(), double_link_list.length())
    double_link_list.insert(-1, 'zhao')
    print(double_link_list.is_empty(), double_link_list.length())
    double_link_list.insert(3, 'zi')
    print(double_link_list.length())
    double_link_list.append('yang')
    double_link_list.add("head")
    double_link_list.insert(4, "tail")
    print(double_link_list.traversing())
    double_link_list.remove(1)
    print(double_link_list.traversing())
    double_link_list.remove("head")
    print(double_link_list.traversing())
    double_link_list.remove("tail")
    print(double_link_list.traversing())
    double_link_list.remove('zi')
    print(double_link_list.traversing())

    print("\n----double_cycle_link_list-----")
    double_cycle_link_list = DoubleCycleLinkList()
    double_cycle_link_list.remove('test')
    print(double_cycle_link_list.is_empty(), double_cycle_link_list.length())
    double_cycle_link_list.insert(-1, 'zhao')
    print(double_cycle_link_list.is_empty(), double_cycle_link_list.length())
    double_cycle_link_list.insert(3, 'zi')
    print(double_cycle_link_list.length())
    double_cycle_link_list.append('yang')
    double_cycle_link_list.add("head")
    double_cycle_link_list.insert(4, "tail")
    print(double_cycle_link_list.traversing())
    double_cycle_link_list.remove(1)
    print(double_cycle_link_list.traversing())
    double_cycle_link_list.remove("head")
    print(double_cycle_link_list.traversing())
    double_cycle_link_list.remove("tail")
    print(double_cycle_link_list.traversing())
    double_cycle_link_list.remove('zi')
    print(double_cycle_link_list.traversing())

结果运行如下：

----single_link_list-----
True 0
False 1
2
head zhao zi yang tail 
head zhao zi yang tail 
zhao zi yang tail 
zhao zi yang 
zhao yang 

----single_cycle_link_list-----
True 0
False 1
2
head zhao zi yang tail 
head zhao zi yang tail 
zhao zi yang tail 
zhao zi yang 
zhao yang 

----double_link_list-----
True 0
False 1
2
head zhao zi yang tail 
head zhao zi yang tail 
zhao zi yang tail 
zhao zi yang 
zhao yang 

----double_cycle_link_list-----
True 0
False 1
2
head zhao zi yang tail 
head zhao zi yang tail 
zhao zi yang tail 
zhao zi yang 
zhao yang

搜索关注微信公众号：寸土币争 ID: