Python数据结构与算法-链表对比(单向链表、单向循环链表、双向链表)

2025-08-08

让GPT实现了一下单链表、单循环链表和双向链表，大体看一看差异。

首先是两个节点基类和链表基类，双向节点继承了基础的单项节点。链表基类则将空链表判断、长度判断、搜索写入基类：

class Node():
    def __init__(self, item):
        super().__init__(item)
        self.item = item
        self.next = None

# 双向节点
class DoubleNode(Node):
    def __init__(self, item):
        super().__init__(item)  # 调用父类的__init__方法。
        self.prev = None
        self.next = None

class BaseLinkedList:
    """链表基类：封装通用方法"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head is None

    def length(self):
        count = 0
        for _ in self:  # 用迭代器遍历
            count += 1
        return count

    def search(self, item):
        for node in self:
            if node.item == item:
                return True
        return False

    def __iter__(self):
        """迭代器方法，子类必须重写"""
        raise NotImplementedError
        # 这儿就是一个提醒，意思是父类没有实现这个方法

我们具体来看看三个链表实现上的差异：

单向链表单向循环链表双向链表
class SingleLinkedList(BaseLinkedList): def __init__(self): super().__init__()class SingleCircularLinkedList(SingleLinkedList):class DoubleLinkedList(BaseLinkedList): def __init__(self): super().__init__()
def __iter__(self): cur = self._head while cur: yield cur cur = cur.nextdef __iter__(self): *"""循环链表迭代器""" *if self.is_empty(): return cur = self._head while True: yield cur cur = cur.next if cur == self._head: # 回到起点就停 breakdef __iter__(self): cur = self._head while cur: yield cur cur = cur.next
def add(self, item): node = Node(item) node.next = self._head self._head = nodedef add(self, item): node = Node(item) if self.is_empty(): self._head = node node.next = self._head else: cur = self._head while cur.next != self._head: cur = cur.next node.next = self._head self._head = node cur.next = self._headdef add(self, item): node = DoubleNode(item) node.next = self._head if self._head: self._head.prev = node self._head = node
def append(self, item): node = Node(item) if self.is_empty(): self._head = node else: cur = self._head while cur.next: cur = cur.next cur.next = nodedef append(self, item): node = Node(item) if self.is_empty(): self._head = node node.next = self._head else: cur = self._head while cur.next != self._head: cur = cur.next cur.next = node node.next = self._headdef append(self, item): node = DoubleNode(item) if self.is_empty(): self._head = node else: cur = self._head while cur.next: cur = cur.next cur.next = node node.prev = cur
def insert(self, pos, item): if pos <= 0: self.add(item) elif pos >= self.length(): self.append(item) else: node = Node(item) cur = self._head for _ in range(pos - 1): cur = cur.next node.next = cur.next cur.next = nodedef insert(self, pos, item): if pos <= 0: self.add(item) elif pos >= self.length(): self.append(item) else: node = DoubleNode(item) cur = self._head for _ in range(pos - 1): cur = cur.next node.next = cur.next node.prev = cur cur.next.prev = node cur.next = nodedef remove(self, item): cur = self._head pre = None while cur: if cur.item == item: if pre is None: self._head = cur.next else: pre.next = cur.next return True pre = cur cur = cur.next return False
def remove(self, item): cur = self._head pre = None while cur: if cur.item == item: if pre is None: self._head = cur.next else: pre.next = cur.next return True pre = cur cur = cur.next return Falsedef remove(self, item): if self.is_empty(): return False cur = self._head pre = None while True: if cur.item == item: if cur == self._head: # 找到尾节点 tail = self._head while tail.next != self._head: tail = tail.next if self._head == self._head.next: self._head = None else: self._head = self._head.next tail.next = self._head else: pre.next = cur.next return True pre = cur cur = cur.next if cur == self._head: break return Falsedef remove(self, item): cur = self._head while cur: if cur.item == item: if cur.prev: cur.prev.next = cur.next else: self._head = cur.next if cur.next: cur.next.prev = cur.prev return True cur = cur.next return False

第一行定义，单向链表和双向链表都继承BaseLinkedList，而单向循环链表继承单项链表。

第二行迭代器，单向和双向链表一致，而单向循环链表首位相连，循环时候需要注意，避免死循环。

第三行add，链表头插入，单向链表常规操作，双向链表考虑一下头指针，单向循环列表需要最后一个元素的指针指回到新的链表，所以需要循环找最后一个元素。

第四行append，链表尾部插入，单向链表常规操作，双向链表类似，单向循环链表也就是需要特殊判断下末尾位置。

第五行insert，三个表大差不差。

第五行remove剔除元素，考虑情况略多一些，其他类似。

完整代码

# 单链表个人测试
# 为了进一步学习使用下python继承相关的面向对象特点
# 红茶半两酒
# 2025/08/08
# -*- coding: utf-8 -*-

# ========== 节点基类 ==========
# 单向节点
class Node():
    def __init__(self, item):
        super().__init__(item)
        self.item = item
        self.next = None

# 双向节点
class DoubleNode(Node):
    def __init__(self, item):
        super().__init__(item)  # 调用父类的__init__方法。
        self.prev = None
        self.next = None

# ========== 链表基类 ==========
class BaseLinkedList:
    """链表基类：封装通用方法"""
    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head is None

    def length(self):
        count = 0
        for _ in self:  # 用迭代器遍历
            count += 1
        return count

    def search(self, item):
        for node in self:
            if node.item == item:
                return True
        return False

    def __iter__(self):
        """迭代器方法，子类必须重写"""
        raise NotImplementedError
        # 这儿就是一个提醒，意思是父类没有实现这个方法

# ========== 单向链表 ==========
class SingleLinkedList(BaseLinkedList):
    def __init__(self):
        super().__init__()

    def __iter__(self):
        cur = self._head
        while cur:
            yield cur
            # 类似于return cur，但是可以保存记忆，同时可以节省内存
            cur = cur.next

    def add(self, item):
        node = Node(item)
        node.next = self._head
        self._head = node

    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node

    def insert(self, pos, item):
        if pos &lt;= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            node = Node(item)
            cur = self._head
            for _ in range(pos - 1):
                cur = cur.next
            node.next = cur.next
            cur.next = node

    def remove(self, item):
        cur = self._head
        pre = None
        while cur:
            if cur.item == item:
                if pre is None:
                    self._head = cur.next
                else:
                    pre.next = cur.next
                return True
            pre = cur
            cur = cur.next
        return False

# ========== 单向循环链表 ==========
class SingleCircularLinkedList(SingleLinkedList):
    def __iter__(self):
        """循环链表迭代器"""
        if self.is_empty():
            return
        cur = self._head
        while True:
            yield cur
            cur = cur.next
            if cur == self._head:  # 回到起点就停
                break

    def append(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            cur.next = node
            node.next = self._head

    def add(self, item):
        node = Node(item)
        if self.is_empty():
            self._head = node
            node.next = self._head
        else:
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
            node.next = self._head
            self._head = node
            cur.next = self._head

    def remove(self, item):
        if self.is_empty():
            return False
        cur = self._head
        pre = None
        while True:
            if cur.item == item:
                if cur == self._head:
                    # 找到尾节点
                    tail = self._head
                    while tail.next != self._head:
                        tail = tail.next
                    if self._head == self._head.next:
                        self._head = None
                    else:
                        self._head = self._head.next
                        tail.next = self._head
                else:
                    pre.next = cur.next
                return True
            pre = cur
            cur = cur.next
            if cur == self._head:
                break
        return False

# ========== 双向链表 ==========
class DoubleLinkedList(BaseLinkedList):
    def __init__(self):
        super().__init__()

    def __iter__(self):
        cur = self._head
        while cur:
            yield cur
            cur = cur.next

    def add(self, item):
        node = DoubleNode(item)
        node.next = self._head
        if self._head:
            self._head.prev = node
        self._head = node

    def append(self, item):
        node = DoubleNode(item)
        if self.is_empty():
            self._head = node
        else:
            cur = self._head
            while cur.next:
                cur = cur.next
            cur.next = node
            node.prev = cur

    def insert(self, pos, item):
        if pos &lt;= 0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            node = DoubleNode(item)
            cur = self._head
            for _ in range(pos - 1):
                cur = cur.next
            node.next = cur.next
            node.prev = cur
            cur.next.prev = node
            cur.next = node

    def remove(self, item):
        cur = self._head
        while cur:
            if cur.item == item:
                if cur.prev:
                    cur.prev.next = cur.next
                else:
                    self._head = cur.next
                if cur.next:
                    cur.next.prev = cur.prev
                return True
            cur = cur.next
        return False

# ========== 测试 ==========
if __name__ == "__main__":
    print("=== 单向链表 ===")
    sll = SingleLinkedList()
    sll.append(1)
    sll.append(2)
    sll.add(0)
    for node in sll:
        print(node.item)

    print("\n=== 单向循环链表 ===")
    scll = SingleCircularLinkedList()
    scll.append(1)
    scll.append(2)
    scll.add(0)
    for node in scll:
        print(node.item)

    print("\n=== 双向链表 ===")
    dll = DoubleLinkedList()
    dll.append(1)
    dll.append(2)
    dll.add(0)
    for node in dll:
        print(node.item)
← 返回