Python--单双向链表实现

于 2019-05-30 09:54:52 发布
阅读量421 收藏
点赞数
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/python_lqx/article/details/90666781
版权
博客主要介绍了链表相关知识，包括单向链表和双向链表。详细阐述了如何设计结点和链表类，实现尾部追加、遍历等功能，还涉及链式编程、插入、弹出、移除等操作，最后对单向链表、双向链表及双向链表容器化进行了代码测试。

摘要生成于 C知道 ，由 DeepSeek-R1 满血版支持， 前往体验 >

实现LinkedList链表

链表有单向链表、双向链表
在这里插入图片描述
对于链表来说

  • 每一个结点都是独立的对象，结点对象有内容，还知道下一个跳是什么
  • 链表则是一个容器，它内部装着一个个结点对象
  • 不管是单向还是双向，建议加一个尾tail，方便追加元素

所以，设计2个类，一个是结点Node类，一个是链表LinkedList类

简单的单向链表

增加append和iternodes

1. 设置两个类

item元素本身，next为下一个元素

class Node:
    def __init__(self, item, next=None):
        self.item = item
        self.next = next
    
    def __repr__(self):
        return str(self.item)

class LinkedList:
    pass

2. 设置头head和尾tail，初始为None

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

    def __repr__(self):
        return str(self.item)

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

3. 尾部追加实现

  • 假设1个都没有，头尾都不动，上一个是None，下一个也是None
  • 假设有一个或多个，只需动尾部
class Node:
    def __init__(self, item, next=None):
        self.item = item
        self.next = next

    def __repr__(self):
        return str(self.item)

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        return self

4. 遍历链表

  • 从头开始遍历，如果头是None，则不进入循环
  • 判断下一个是否为None
class Node:
    def __init__(self, item, next=None):
        self.item = item
        self.next = next

    def __repr__(self):
        return str(self.item)

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        return self

    def iternodes(self):
        current = self.head
        while current:
            yield current
            current = current.next

5. 链式编程，增加add函数

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

    def __repr__(self):
        return str(self.item)

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        return self

    def __add__(self, item):
        return self.append(item)

    def iternodes(self):
        current = self.head
        while current:
            yield current
            current = current.next

6. 测试代码

ll = LinkedList() # 实例化
ll.append(4).append(5).append(6) # 链式编程
ll.append(7) + 8 # 调用add函数
ll + 9 + 10 # 调用add函数

for x in ll.iternodes():
    print(x)

# 执行结果
4
5
6
7
8
9
10

简单的双向链表

1. 设置两个类

item元素本身，next为下一个元素，上一个元素prev

class Node:
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance
    
    def __repr__(self):
        return str(self.item)

class LinkedList:
    pass

2. 设置展示格式

class Node:
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance

    def __repr__(self):
        return "{} <== {} ==> {}".format(
            self.prev.item if self.prev else None,
            self.item, 
            self.next.item if self.next else None
        )

3. 设置头和尾

class Node:
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance

    def __repr__(self):
        return "{} <== {} ==> {}".format(
            self.prev.item if self.prev else None,
            self.item, 
            self.next.item if self.next else None
        )

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

4. 尾部追加和add实现

class Node:
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance

    def __repr__(self):
        return "{} <== {} ==> {}".format(
            self.prev.item if self.prev else None,
            self.item,
            self.next.item if self.next else None
        )

class LinkedList: # Double
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
        else:
            self.tail.next = node # 当前结点的下一个
            node.prev = self.tail
        self.tail = node
        return self
        
    def __add__(self, item):
        return self.append(item)

5. insert 插入

class Node:
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance

    def __repr__(self):
        return "{} <== {} ==> {}".format(
            self.prev.item if self.prev else None,
            self.item,
            self.next.item if self.next else None
        )

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
        self.tail = node
        return self

    def __add__(self, item):
        return self.append(item)

    def insert(self, index, value):
        if index < 0: # 索引为负数,抛异常
            raise IndexError('Not negative')

        current = None
        for i,node in enumerate(self.iternodes()):
            if i == index:
                current = node
                break
        else: # 超界
            self.append(value) # 没找到,当做尾部追加
            return

        # 找到了,容器非空
        newnode = Node(value)
        prev = current.prev
        next = current
        # 开头插入
        if prev is None: # i==0  index==0  self.head==current
            self.head = newnode
        else: # 非开头
            newnode.prev = prev
            prev.next = newnode
        newnode.next = next
        next.prev = newnode

6. pop 尾部弹出

class Node:
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance

    def __repr__(self):
        return "{} <== {} ==> {}".format(
            self.prev.item if self.prev else None,
            self.item,
            self.next.item if self.next else None
        )

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
        self.tail = node
        return self

    def __add__(self, item):
        return self.append(item)

    def insert(self, index, value):
        if index < 0:
            raise IndexError('Not negative')

        current = None
        for i,node in enumerate(self.iternodes()):
            if i == index:
                current = node
                break
        else:
            self.append(value) # 没找到,当做尾部追加
            return

        # 找到了,容器非空
        newnode = Node(value)
        prev = current.prev
        next = current
        # 开头插入
        if prev is None: # i==0  index==0  self.head==current
            self.head = newnode
        else: # 非开头
            newnode.prev = prev
            prev.next = newnode
        newnode.next = next
        next.prev = newnode
    
    def pop(self):
        if self.tail is None:
            raise Exception("empty")
        
        node = self.tail # 当前元素
        prev = node.prev # 前一个元素
        # only one
        if prev is None: # self.head.next is None
            self.head = None
            self.tail = None
        else:
            prev.next = None
            self.tail = prev
            
        value = node.item
        return value

7. remove 移除

class Node:
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance

    def __repr__(self):
        return "{} <== {} ==> {}".format(
            self.prev.item if self.prev else None,
            self.item,
            self.next.item if self.next else None
        )

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
        self.tail = node
        return self

    def __add__(self, item):
        return self.append(item)

    def insert(self, index, value):
        if index < 0:
            raise IndexError('Not negative')

        current = None
        for i,node in enumerate(self.iternodes()):
            if i == index:
                current = node
                break
        else:
            self.append(value) # 没找到,当做尾部追加
            return

        # 找到了,容器非空
        newnode = Node(value)
        prev = current.prev
        next = current
        # 开头插入
        if prev is None: # i==0  index==0  self.head==current
            self.head = newnode
        else: # 非开头
            newnode.prev = prev
            prev.next = newnode
        newnode.next = next
        next.prev = newnode

    def pop(self):
        if self.tail is None:
            raise Exception("empty")

        node = self.tail # 当前元素
        prev = node.prev # 前一个元素
        # only one
        if prev is None: # self.head.next is None
            self.head = None
            self.tail = None
        else:
            prev.next = None
            self.tail = prev

        value = node.item
        return value

    def remove(self, index):
        if self.tail is None:
            raise Exception("empty")

        if index < 0:
            raise IndexError('Not negative')

        current = None
        for i,node in enumerate(self.iternodes()):
            if i == index:
                current = node
                break
        else:
            raise IndexError('out of index') # 没找到

        prev = current.prev
        next = current.next

        if prev is None and next is None: # 只有一个 # self.head == self.tail
            self.head = None
            self.tail = None
        elif prev is None: # 头部移除
            self.head = next
            next.prev = None
        elif next is None: # 尾部移除
            self.tail = prev
            prev.next = None
        else: # 中间移除
            prev.next = next
            next.prev = prev
        
        del current # 关注临时变量,防止未释放占内存

7. iternodes 遍历

class Node:
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance

    def __repr__(self):
        return "{} <== {} ==> {}".format(
            self.prev.item if self.prev else None,
            self.item,
            self.next.item if self.next else None
        )

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
        self.tail = node
        return self

    def __add__(self, item):
        return self.append(item)

    def insert(self, index, value):
        if index < 0:
            raise IndexError('Not negative')

        current = None
        for i,node in enumerate(self.iternodes()):
            if i == index:
                current = node
                break
        else:
            self.append(value) # 没找到,当做尾部追加
            return

        # 找到了,容器非空
        newnode = Node(value)
        prev = current.prev
        next = current
        # 开头插入
        if prev is None: # i==0  index==0  self.head==current
            self.head = newnode
        else: # 非开头
            newnode.prev = prev
            prev.next = newnode
        newnode.next = next
        next.prev = newnode

    def pop(self):
        if self.tail is None:
            raise Exception("empty")

        node = self.tail # 当前元素
        prev = node.prev # 前一个元素
        # only one
        if prev is None: # self.head.next is None
            self.head = None
            self.tail = None
        else:
            prev.next = None
            self.tail = prev

        value = node.item
        return value

    def remove(self, index):
        if self.tail is None:
            raise Exception("empty")

        if index < 0:
            raise IndexError('Not negative')

        current = None
        for i,node in enumerate(self.iternodes()):
            if i == index:
                current = node
                break
        else:
            raise IndexError('out of index') # 没找到

        prev = current.prev
        next = current.next

        if prev is None and next is None: # 只有一个 # self.head == self.tail
            self.head = None
            self.tail = None
        elif prev is None: # 头部移除
            self.head = next
            next.prev = None
        elif next is None: # 尾部移除
            self.tail = prev
            prev.next = None
        else: # 中间移除
            prev.next = next
            next.prev = prev

        del current # 删除临时变量,减少引用计数,释放内存

    def iternodes(self, reverse=False):
        current = self.tail if reverse else self.head
        while current:
            yield current
            current = current.prev if reverse else current.next

8. 代码测试

ll.append(0).append(1).append(2)
ll.insert(2, 4)
ll.pop()
ll.remove(0)
for x in ll.iternodes(): # 倒序遍历
    print(x)
print('-'*30)
for x in ll.iternodes(True): # 正序遍历
    print(x)

# 执行结果
None <== 1 ==> 4
1 <== 4 ==> None
------------------------------
1 <== 4 ==> None
None <== 1 ==> 4

双向链表容器化

class Node:
    __slots__ = 'item next prev'.split()
    
    def __init__(self, item, next=None, prev=None):
        self.item = item
        self.next = next # Node instance
        self.prev = prev # Node instance

    def __repr__(self):
        return "{} <== {} ==> {}".format(
            self.prev.item if self.prev else None,
            self.item,
            self.next.item if self.next else None
        )

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0
    def append(self, value):
        node = Node(value) # 下一个是None的结点

        if self.tail is None: # empty
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
        self.tail = node
        self._size +=1
        return self

    def __add__(self, item):
        return self.append(item)

    def insert(self, index, value):
        if index >= len(self):
            self.append(value)
            return

        if index < -len(self):
            index = 0
        current = self[index]

        # 找到了,容器非空
        newnode = Node(value)
        prev = current.prev
        next = current
        # 开头插入
        if prev is None: # i==0  index==0  self.head==current
            self.head = newnode
        else: # 非开头
            newnode.prev = prev
            prev.next = newnode
        newnode.next = next
        next.prev = newnode
        self._size += 1

    def pop(self):
        if self.tail is None:
            raise Exception("empty")

        node = self.tail # 当前元素
        prev = node.prev # 前一个元素
        # only one
        if prev is None: # self.head.next is None
            self.head = None
            self.tail = None
        else:
            prev.next = None
            self.tail = prev

        value = node.item
        self._size -= 1
        return value

    def remove(self, index):
        if self.tail is None:
            raise Exception("empty")

        current = self[index]

        prev = current.prev
        next = current.next

        if prev is None and next is None: # 只有一个 # self.head == self.tail
            self.head = None
            self.tail = None
        elif prev is None: # 头部移除
            self.head = next
            next.prev = None
        elif next is None: # 尾部移除
            self.tail = prev
            prev.next = None
        else: # 中间移除
            prev.next = next
            next.prev = prev
        self._size -= 1
        del current # 删除临时变量,减少引用计数,释放内存

    def iternodes(self, reverse=False):
        current = self.tail if reverse else self.head
        while current:
            yield current
            current = current.prev if reverse else current.next

    # 容器
    def __len__(self):
        return self._size

    size = property(lambda self: self._size)

    def __getitem__(self, index):
        if index >= len(self) or index < -len(self):
            raise IndexError('out of index : {}'.format(index))

        reverse = True if index < 0 else False
        start = 1 if index < 0 else 0

        for i, node in enumerate(self.iternodes(reverse), start): # index >=0
            if i == abs(index):
                return node

    def __setitem__(self, index, value): # 改
        self[index].item = value

    # 此魔术方法可以不实现,但是要使用reversed内建函数,必须有__len__和__getitem__
    def __reversed__(self):
        # yield from self.iternodes(True)
        return self.iternodes(True)

    # def __iter__(self):
    #     return self.iternodes()

    __iter__ = iternodes

    def __contains__(self, item):
        current = self.head
        while current:
            if item == current.item:
                return True
            current = current.next
        return False

代码测试

ll = LinkedList()

ll.append(0)
ll + 1 + 2 + 3
ll.insert(2, 4)
ll.pop()
ll.remove(0)
ll[1] = 6

for x in ll.iternodes(): # 倒序遍历
    print(x)
print('-'*30)
for x in ll.iternodes(True): # 正序遍历
    print(x)

print(2 in ll)
print(len(ll),ll[1])

# 执行结果
None <== 1 ==> 6
1 <== 6 ==> 2
6 <== 2 ==> None
------------------------------
6 <== 2 ==> None
1 <== 6 ==> 2
None <== 1 ==> 6
True
3 1 <== 6 ==> 2
鹿夏
关注
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值