Python 实现链表实例代码

Python 实现链表是面试中常见的问题。下面就详细讲解一下 Python 实现链表的完整攻略。

基本概念

首先，了解一下链表的基本概念。链表是由一系列的节点组成，每个节点包含了两个指针，一个指向当前节点的下一个节点，另一个指向当前节点的前一个节点。在 Python 中，可以用字典来表示链表节点：

node = {'data': 1, 'next': None}

其中，data 表示节点存储的数据，next 表示指向下一个节点的指针，初始值设为 None。

创建链表

创建链表的时候，需要创建一个头节点，最初的时候，头节点的 next 指针应该为 None。

head = {'data': None, 'next': None}

然后在头节点之后加入第一个节点。

head['next'] = {'data': 1, 'next': None}

接着加入第二个节点。

head['next']['next'] = {'data': 2, 'next': None}

以此类推，代码如下：

head = {'data': None, 'next': None}
current = head

for i in range(1, 6):
    current['next'] = {'data': i, 'next': None}
    current = current['next']

完成之后，这个链表将包含五个节点，值分别为 1，2，3，4，5。

遍历链表

遍历链表需要从头节点开始，不断访问每一个节点，直到链表的末尾。代码如下：

current = head['next']
while current != None:
    print(current['data'])
    current = current['next']

这段代码会输出链表中每一个节点的值。

添加和删除节点

添加节点和删除节点是链表经常需要进行的操作。

添加节点需要在链表中找到合适的位置，然后将指针连接正确。

下面的例子展示了如何向链表中添加一个节点。

new_node = {'data': 3.5, 'next': None}

current = head['next']
prev = head

# 找到插入位置的前一个节点
while current != None and current['data'] < new_node['data']:
    prev = current
    current = current['next']

# 插入新节点
new_node['next'] = current
prev['next'] = new_node

这段代码会将节点 3 和 4 之间插入一个新节点。

删除节点需要在链表中找到要删除的节点，然后将指针连接正确。

下面的例子展示了如何从链表中删除一个节点。

target = 3

current = head['next']
prev = head

# 找到要删除的节点
while current != None and current['data'] != target:
    prev = current
    current = current['next']

# 删除节点
if current != None:
    prev['next'] = current['next']

这段代码会将节点 3 从链表中删除。