Python双向链表实现详解：从节点定义到完整操作

# Functions  函数声明
class Node():
    """实例化节点类"""
    def __init__(self, item):
        self.item = item
        self.prev = None
        self.next = None

class Linklist():
    """
    存储所有节点类
    """
    def __init__(self):
        """
        初始化一个头结点
        默认为空
        """
        self.head = None

    # 1. 链表是否为空
    def is_empty(self):
        return self.head == None

    # 2. 链表的长度
    def length(self):
        """
        返回节点的长度
        实例化一个游标
        使用这个游标遍历所有的数据
        使用一个计数器，遍历一个数据，自增一，最后输出计数器
        """
        # 实例化游标
        cur = self.head
        # 技术器
        # 如果链表为空，不会进入循环，直接输出 0
        count = 0
        # 遍历所有的数据
        while cur != None:
            count +=1
            cur = cur.next
        return count

    # 3. 遍历链表
    def treval(self):
        """
        遍历链表，获取所有的数据
        使用游标，遍历整个链表，每次输出cur.item 的值
        注意链表为空的情况，
        """
        # 实例化一个游标
        cur = self.head
        # 遍历链表
        while cur != None:
            print(cur.item, end=' ')
            cur = cur.next
        print()
    # 4. 链表头部添加元素
    def add(self, item):
        """
        头部添加数据
        分析：
        1、头部添加数据，链表为空时： self.head 指向node
        2、链表不为空时： 先将node.next = self.head.next, 再讲 self.head = node
        """
        # 实例化节点
        node = Node(item)
        # 添加数据
        # 判断链表是否为空
        if self.is_empty():
            # 为空，直接将self.head 指向node
            self.head=node
        else:
            # 不为空，先将noede
            node.next = self.head
            self.head.prev=node
            self.head=node

    # 5. 链表尾部添加元素
    def append(self,item):
        """
        尾部添加数据
        分析：
        要先将指针指向尾部的节点
        最后的节点的 cur.next = node, node.prev = cur
        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        # 移动游标到最后一个节点
        # 如果链表为空
        # 直接使用头插法
        if self.is_empty():
            self.add(item)
        else:
            while cur.next != None:
                # cur.next 不为空，则进入循环， 上次循环，是进入上上个节点，但 将cur  = cur.next，就指向了最后一个节点
                cur = cur.next
            node.prev = cur
            cur.next = node

    # 6. 链表指定位置添加元素
    def insert(self, index, item):
        """
        指定位置添加数据
        分析
        单链表中需要实例化两个有游标
        双向链表，直接向指针指向索引的位置
        将这个位置节点的 cur.
        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        # 起始位置
        count = 0
        if index<=0:
            # 使用头插法
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 移动游标
            while count < index:
                # 增加一
                count += 1
                # 移动游标到索引位置
                cur = cur.next
            node.next = cur
            node.prev = cur.prev
            cur.prev.next = node
            cur.prev = node


    # 7. 链表删除节点
    def remove(self,item):
        """
        删除指定的节点
        首先实例化节点，遍历链表，找到该节点，删除该节点
        """
        # 实例化游标
        cur = self.head
        # 遍历链表，找到该节点
        while cur != None:
            if cur.item == item:
                if self.head == cur:
                    self.head = cur.next
                    if cur.next:
                        cur.next.prev = None
                else:
                    cur.prev.next = cur.next
                    # 如果有下个节点，防止最后一个节点
                    if cur.next:
                        cur.next.prev = cur.prev
                    pass
                break
            else:
                cur = cur.next

    # # 8. 查找节点是否存在
    def search(self, item):
        """
        查看节点是否存在
        分析
        遍历链表，查看每一个节点的数据区
        空链表
        只有头节点
        只有尾节点
        """
        # 实例化一个游标
        cur = self.head

        # 遍历链表
        while cur != None:
            if cur.item == item:
                return True
            else:
                cur = cur.next
        return False

# 程序的入口
if __name__ == "__main__":
    s = Linklist()
    print(s.is_empty())  #  True
    s.append(100) 
    s.append(200)
    s.append(300)
    s.add(6)
    s.insert(1, 10)
    s.search(6)
    s.treval()   # 6 10 100 200 300 
    s.remove(100)
    s.treval()   # 6 10 200 300 
    pass